Linked List - Easy Reference Guide

Everything has its own advantages and disadvantages and also every thing that is present will be used in some ways. I wanted to explain bit by bit about Linked List.

Linked Lists

A linked list is a linear data structure where each element is a separate object. Linked list elements are not stored at contiguous location; the elements are linked using pointers. Each node of a list is made up of two items - the data and a reference to the next node. The last node has a reference to null.



Creation of node in Linked List using Python


# Node class

class Node:

# Function to initialize the node object

def __init__(self, data):

self.data = data  # Assign data

self.next = None # Initialize next as null

# Linked List class

class LinkedList:

# Function to initialize the Linked List object

def __init__(self): 

self.head = None


Adding a node to the linked list can be done in 3 ways

  • At the front of the linked list

  • After a given node.

  • At the end of the linked list.

1) Add a node at the front: (A 4 steps process)

The new node is always added before the head of the given Linked List. And newly added node becomes the new head of the Linked List. For example if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25. Let us call the function that adds at the front of the list is push(). The push() must receive a pointer to the head pointer, because push must change the head pointer to point to the new node


# This function is in LinkedList class

# Function to insert a new node at the beginning

def push(self, new_data):

# 1 & 2: Allocate the Node &

#        Put in the data

    new_node = Node(new_data)

# 3. Make next of new Node as head

    new_node.next = self.head

# 4. Move the head to point to new Node 

self.head = new_node


2) Add a node after a given node: (5 steps process)

We are given pointer to a node, and the new node is inserted after the given node.



# Inserts a new node after the given prev_node.

def insertAfter(self, prev_node, new_data):

# 1. check if the given prev_node exists

if prev_node is None:

print "The given previous node must inLinkedList."

return

#  2. Create new node &

#  3. Put in the data

    new_node = Node(new_data)

# 4. Make next of new Node as next of prev_node 

    new_node.next = prev_node.next

# 5. make next of prev_node as new_node 

    prev_node.next = new_node

3)Add a node at the end: (6 steps process)

The new node is always added after the last node of the given Linked List. For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.

Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then change the next of last node to new node.



# This function is defined in Linked List class

# Appends a new node at the end.  This method is

#  defined inside LinkedList class shown above */

def append(self, new_data):

# 1. Create a new node

# 2. Put in the data

# 3. Set next as None

   new_node = Node(new_data)

# 4. If the Linked List is empty, then make the

#    new node as head

if self.head is None:

self.head = new_node

return

# 5. Else traverse till the last node

   last = self.head

while (last.next):

       last = last.next

# 6. Change the next of last node

   last.next = new_node

Implementation of Linked List methodologies:

We can implement the linked list using 2 types of data structures

1)Queue - This uses First in First Out mechanism(FIFO)

2)Stack - This uses Last in First Out(LIFO) or First In Last Out(FILO)

Queue - This uses First in First Out mechanism(FIFO)



Operations associated with queue are:

  • Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition

  • Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition

  • Front: Get the front item from queue

  • Rear: Get the last item from queue

Stack - This uses Last in First Out(LIFO) or First In Last Out(FILO)

A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added at one end and an element is removed from that end only. The insert and delete operations are often called push and pop.


The functions associated with stack are:

  • empty() – Returns whether the stack is empty

  • size() – Returns the size of the stack

  • top() – Returns a reference to the top most element of the stack

  • push(g) – Adds the element ‘g’ at the top of the stack

  • pop() – Deletes the top most element of the stack

Types of Linked Lists

  • Singly Linked List

  • Circular Linked List

  • Doubly Linked List

Singly Linked List

Singly Linked Lists are a type of data structure. ... A linked list, in its simplest form, in a collection of nodes that collectively form linear sequence. In a singly linked list, each node stores a reference to an object that is an element of the sequence, as well as a reference to the next node of the list.


Circular Linked List

A circular linked list is a sequence of elements in which every element has a link to its next element in the sequence and the last element has a link to the first element. That means circular linked list is similar to the single linked list except that the last node points to the first node in the list.


Doubly linked list

Doubly linked list is a type of linked list in which each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list.



34 views0 comments

Recent Posts

See All

Headless Browser in Python

What is a headless browser? A headless browser can access any website but unlike normal browsers (which you currently use) nothing will appear on the screen. Everything is done on the backend side inv