top of page
Search

# 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.

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

# Function to initialize the Linked List object

def __init__(self):Â

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)

# 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Â

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

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

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

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.

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 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.