LinkedList
Singly LinkedList
What is it?
LinkedList is like a game of treasure-hunt where each point contains the clue for the next point
We need to start somewhere for the next point (node), therefore we are given with first node call head
A node contains 2 information (a node is a class object, from an implementation point of view):
value of the current node
pointing to the second node (address or class object)
# Here is how a single node for single LinkedList is defined, Node object (class)
class Node:
def __init__(self, data):
self.data = data
self.next = NoneThe power of LinkedList comes from, ability to break the chain and rejoin it
Hence, unlike a list. we don't need to shift all the items after insertion, rather we can insert anywhere
Here is a disadvantage as well, index access is not efficient; we need to iterate from head till we reach the index to access it. Arbitrary access needs iteration from head to the point/index
Various Operations
Operation
Worst case
Average case
Search
O(n)
O(n)
Insert at the start
O(1)
O(1)
Deletion at the end
O(1)
O(1)
Implementation
Different Operations:
Insertion: at the start, in the end, in the middle
Traversing (accessing all the elements or search for a specific number)
Deletion: starting node
Delete key: find the key in LinkedList and delete the first found
Display: display the LinkedList
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self, head=None):
self.head = head
def insertion(self, data):
new_node = Node(data)
if self.head == None:
self.head = new_node
else:
next_node = self.head
self.head = new_node
self.head.next = next_node
return True
def deletion(self):
if self.head:
self.head = self.head.next
return -1
else:
return 'empty'
def display(self):
this_node = self.head
while this_node:
print(this_node.data, end = ' -> ')
this_node = this_node.next
print()
def search(self, data):
this_node = self.head
count = 0
while this_node:
if this_node.data == data:
return count
else:
count+=1
this_node = this_node.next
return -1
def delete_key(self, data):
this_node = self.head
if not this_node:
return False
if this_node.data == data:
self.head = this_node.next
return True
prev_node = this_node
this_node = this_node.next
while this_node:
if this_node.data == data:
if this_node.next:
prev_node.next = this_node.next
else:
prev_node.next = None
return True
prev_node = this_node
this_node = this_node.next
return False
Doubly LinkedList
what is it?
In doubly LinkedList, we can move in either direction
A node has three parts in a doubly LinkedList
Data for the node
pointer to the next node
pointer to the previous node
# Here is how a single node for doubly LinkedList is defined, Node object (class)
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = NoneWe are given with start and end node in the case of LinkedList
We can travel in both forward or backward direction
Time complexity point of view: No difference if adding and deleting from start or end
Implementation
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self, head = None, tail = None):
self.head = head
self.tail = tail
def head_insertion(self, data):
new_node = Node(data)
if self.head:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
else:
self.head = new_node
self.tail = new_node
def tail_insertion(self, data):
new_node = Node(data)
if self.tail:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
else:
self.head = new_node
self.tail = new_node
def head_deletion(self):
if self.head == self.tail:
self.head = None
self.tail = None
elif self.head:
self.head = self.head.next
self.head.prev = None
def tail_deletion(self):
if self.tail == self.head:
self.head = None
self.tail = None
elif self.tail:
self.tail = self.tail.prev
self.tail.next = None
def key_deletion(self, data):
this_node = self.head
if not this_node:
return False
if this_node.data == data:
if this_node.next:
self.head = this_node.next
self.head.prev = None
else:
self.head = None
self.tail = None
return True
prev_node = this_node
this_node = this_node.next
while this_node:
if this_node.data == data:
if this_node.next:
this_node.next.prev = prev_node
prev_node.next = this_node.next
else:
prev_node.next = None
self.tail = prev_node
return True
prev_node = this_node
this_node = this_node.next
return False
def display(self):
this_node = self.head
while this_node:
print(this_node.data, end= ' -> ')
this_node = this_node.next
print()
def search(self, data):
this_node = self.head
count = 0
while this_node:
if this_node.data == data:
return count
else:
count+=1
this_node = this_node.next
return -1Circular LinkedList
What is it?
A circular LinkedList is a variation of a linked list in which the last element is linked to the first element. This forms a circular loop
It can be implemented using singly LinkedList or doubly LinkedList
for a singly LinkedList, the next pointer of the last item points to the first item
In the doubly LinkedList, prev pointer of the first item points to the last item as well
The NULL assignment is not required because a node always points to another node.
The starting point can be set to any node.
Traversal from the first node to the last node is quick
Implementation
Circular LinkedList using Singly LinkedList
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class CircularSinglyLinkedList:
def __init__(self, last=None):
self.last = last
def insertion(self, data):
new_node = Node(data)
if not self.last:
self.last = new_node
self.last.next = self.last
else:
new_node.next = self.last.next
self.last.next = new_node
def deletion(self):
if not self.last:
return True
elif self.last and not self.last.next:
self.last = None
return True
elif self.last and self.last.next:
self.last.next = self.last.next.next
return True
else:
return False
def display(self):
this_node = self.last
if self.last:
this_node = this_node.next
while this_node != self.last:
print(this_node.data, end = ' -> ')
this_node = this_node.next
print(this_node.data)Circular LinkedList using Doubly LinkedList
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class CircularDoublyLinkedList:
def __init__(self, head=None):
self.head = head
def head_insertion(self, data):
new_node = Node(data)
if not self.head:
new_node.prev = new_node
new_node.next = new_node
self.head = new_node
else:
temp = self.head
new_node.next = self.head
new_node.prev = self.head.prev
self.head.prev = new_node
new_node.prev.next = new_node
self.head = new_node
def head_deletion(self):
if not self.head or not self.head.next:
self.head = None
return True
else:
self.head.prev.next = self.head.next
self.head.next.prev = self.head.prev
self.head = self.head.next
return True
def display(self):
this_node = self.head
if this_node:
print(this_node.data, end = ' -> ')
this_node = this_node.next
while this_node != self.head:
print(this_node.data, end = ' -> ')
this_node = this_node.next
print()LinkedList Data Structure Uses
Implemented in the queue - regular queue - implementation using LinkedList
Dynamic memory allocation -
In undo functionality, it is more like a use case of queue using LinkedList
In Hash tables - When there is a collision of hash (two different values have the same hash then they are arranged as LinkedList within a hash)
In Tree -
In Graphs -
Miscellaneous
Difference Between the Array and LinkedList?
Reference for Further Reading
Last updated
Was this helpful?