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 = None

• The 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 = None

• We 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 -1

Circular 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

• 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

Top 20 Linked List Coding Problems from Technical InterviewsMedium