Introduction

Linked List are composed of nodes and references / pointeres pointing form one node to the other,

Note: The last reference points to NULL
  • They can be used to implement several other data types:
    • Stack
    • Queues
  • Simple Linked list by themselves do not allow random access tot eh data, so we can not use indexes
  • Many basic operations such as obtaining the last node of the list or finding a node that contains a given data or locating the place where a neww node should be inserted - require sequential scanning of most or the list elements.

Advantages

  • Linked lists are dynamic data strucutes (arrays are not)
  • It can allocate the needed memory in run-time
  • very efficient if we want to manipulate the first elements
  • can store items with different sizes; an array assumes eveery element to be exactly the same.
  • It's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-createtd with it needs to grow.

Disadvantages

  • Waste memory because of the references
  • Nodes in a linkedlist must be read in order from the beginning as linked list have sequential access ( arrays items can be reached via indexes in O(1) time )
  • Difficulties arise in linked list when it comes ot reverse traveresing. Singly lined list are extermely diffcult to navigate backwards.
  • Solution: Doubly linkked list -> easier to read, but memory is wasted in allocating space ofr a back pointer.

Linked list VS Arrays

  1. Search

    • Search operation nyieldss the same result for both data structure
    • ArrayList search opoearations is pretty fast compared to the linkedlist search operation
    • we can use random access iwth arrays: getitem(int index) which is $O(1)$ time complexity
    • LinkedList perfomance is $O(N)$ time complexity
    • So the conclusion: Arrays list is better for this operation.
  2. Deletion

    • LinkedList remove operations takes $O(1)$ time if we remove items from the beginning and usually this is the case.
    • ArrayList: removing first element (so at the beginning ) takes $O(N)$ tiem, removing the last item takes $O(1)$ times
    • But on average: we have to reconstruct the array when reoving
    • So the conclusion: LinkedList is better for this operation
  3. Memory Management

    • Arrays do not need any extra memory
    • LinkedList on the other hand do need extra memory because of the references / pointers.
    • So in this aspect: arrays are better, they are memory friendly.

Singly Linked list

A Single node:

  • Contains data -> integer, double or custom data
  • contains a reference pointing to the next node in the linked list
class Node:
    def __init__(self, info, link=None):
        self.info = info
        self.link = link
first = Node(10)
print("Node Info:",first.info)
print("Node Link:",first.link)
Node Info: 10
Node Link: None

#collapse-hide
class LinkedList:
    
    def __init__(self):
        self.head = None
        self.size = 0
        
    def insertAtBeginning(self, info):
        self.size += 1
        newNode = Node(info)
        if self.head != None:
            newNode.link = self.head
            self.head = newNode
        else:
            self.head = newNode
            
    def insertAtEnd(self, info):
        self.size += 1
        newNode = Node(info)
        if self.head != None:
            current = self.head
            while current.link != None:
                current = current.link
            current.link = newNode
        else:
            self.head = newNode
                
    def insertAtIndex(self, index, info):
        newNode = Node(info)
        pass
    
    def deleteNode(self, element):
        if self.head == None:
            print("List empty")
        if self.head.info == element:
            temp = self.head
            self.head = temp.link
            temp = None
            return
        current = self.head
        while current.link != None:
            if current.link.info == element:
                temp = current.link
                current.link = temp.link
                temp = None
                return 
            current = current.link
        print("Element is not found in the list")
    
    def find(self, element):
        if self.head == None:
            print("List is Empty")
            return 
        current = self.head
        while current != None:
            if current.info == element:
                return True
            current = current.link
        return False
    
    def display(self):
        current = self.head
        while current != None:
            print(current.info)
            current = current.link
    
    def getSize(self):
        print(self.size)
            
    def getSizeWcount(self):
        size = 0
        current = self.head
        while current != None:
            size += 1
            current = current.link
        print(size)
ll = LinkedList()
ll.insertAtBeginning(10)
ll.insertAtBeginning(20)
ll.insertAtBeginning(30)
ll.display()

print("****") 

ll.insertAtEnd(1)
ll.insertAtEnd(2)
ll.insertAtEnd(3)
ll.display()
30
20
10
****
30
20
10
1
2
3
ll.getSize()
6
ll.deleteNode(30)
ll.display()
20
10
1
2
3
ll.find(30)
False

Singly Linked list operations

considering only Worst Cases

  • insertAtBeginning() : $O(1)$
  • insertAtEnd() : $O(n)$
  • deleteNode() : $O(1)$
  • display() : $O(1)$
  • find() : $O(n)$
  • getSize() : $O(1)$
  • getSizeWcount() : $O(n)$

Doubly Linked list

Doubly linked list are composed of nodes and references / pointeres pointing from one node to the other.

Note: The last and first references are pointing to NULL

Advantages

  • A doubly linked list can be traversesd both directions: forward and backward.
  • The remove operation is more efficient if the node is given

For linked list we need the previous node as well. To find it usually we need to traverses the whole list.

  • To remvoe a node from singly linked list -> we need the node + Predecessor
  • To remove a node from doubly linked lsit -> we need the node .

A Single node:

  • Contains data -> integer, double or custom object
  • contains a reference pointing to the next node in the linked list
  • contains a reference pointing to the previous node in the linked list
class Node:
    def __init__(self, info, prev=None, next=None):
        self.info = info
        self.prev = prev
        self.next = next 
first = Node(10)
print("Node Info:",first.info)
print("Node prev:",first.prev)
print("Node next:",first.next)
Node Info: 10
Node prev: None
Node next: None

#collapse-hide
class LinkedList:
    
    def __init__(self):
        self.head = None
    
    def insertAtBeginning(self, element):
        newNode = Node(element)
        if self.head == None:
            self.head = newNode
        else:
            newNode.next = self.head 
            self.head.prev = newNode
            self.head = newNode
    
    def insertAtEnd(self, element):
        newNode = Node(element)
        if self.head == None:
            self.head = newNode
        else:
            current = self.head
            while current.next != None:
                current = current.next
            current.next = newNode
            newNode.prev = current
    
    def deleteNode(self, element):
        if self.head == None:
            print("Empty List")
        # Delete Node in the beginning
        if self.head.next == None:
            if self.head.info == element:
                temp = self.head
                self.head = None
                temp = None
                return 
            else:
                print("Not Found")
                
        # Delete Node in between 
        temp = self.head.next
        while temp.next != None:
            if temp.info == element:
                temp.prev.next = temp.next
                temp.next.prev = temp.prev
                temp = None
                return
            temp = temp.next
        
        # Delete Node in the last
        if temp.info == element:
            temp.prev.next = None
            temp = None 
    
    def display(self):
        if self.head == None:
            print("Empty List")
        else:
            current = self.head
            while current != None:
                print(current.info)
                current = current.next
dll = LinkedList()
dll.insertAtBeginning(10)
dll.insertAtBeginning(20)
dll.insertAtBeginning(30)
dll.display()

print("*******")

dll.insertAtEnd(1)
dll.insertAtEnd(2)
dll.insertAtEnd(3)
dll.display()
dll.deleteNode(10)
dll.display()
30
20
1
2
3

Doubly Linked list operations

considering only Worst Cases

  • insertAtBeginning() : $O(1)$
  • insertAtEnd() : $O(n)$
  • deleteNode() : $O(1)$
  • display() : $O(1)$

Twin

#collapse-hide
import sys
class node: 

    def __init__(self, info): 
        self.info = info  
        self.prev = None
        self.next = None 

class LinkedList: 

    def __init__(self): 
        self.head = None


    def display(self):
        temp = self.head 
        while (temp): 
            print( temp.info) 
            temp = temp.next
    
    def insert_at_beg(self,data):
        self.temp = node(data)
        if self.head is None:
            self.head = self.temp
            return
        self.temp.next=self.head
        self.head.prev=self.temp
        self.head= self.temp
        
    def insert_at_end(self,data):
        self.temp = node(data)
        if self.head is None:
            self.head = self.temp
            return
        self.p=self.head
        while(self.p.next):
            self.p=self.p.next
        self.p.next=self.temp
        self.temp.prev=self.p
        
    def insert_after_given_node(self,data,item):
        self.p=self.head
        while self.p is not None:
            if(self.p.info==item):
                self.temp=node(data)
                self.temp.prev=self.p
                self.temp.next=self.p.next
                if (self.p.next):
                    self.p.next.prev=self.temp
                self.p.next=self.temp
                return
            self.p=self.p.next
    def delete(self,data):
        if self.head is None:
            print("List is empty")
            return
        if self.head.next is None:
            if self.head.info==data:
                self.temp=self.head;
                self.head=None
                return
            
            else:
                print("element not found")
                return
        if self.head.info==data:
            self.temp=self.head
            self.head=self.head.next
            self.head.prev=None
            return
        self.temp=self.head
        while self.temp.next is not None:
            if self.temp.info==data:
                self.temp.prev.next=self.temp.next
                self.temp.next.prev=self.temp.prev
                return
            self.temp=self.temp.next
        if(self.temp.info==data):
            self.temp.prev.next=None;
            return 
        print("element not found")
    
    def reverse(self):
        self.p1=self.head
        self.p2=self.p1.next
        self.p1.next=None
        self.p1.prev=self.p2
        while self.p2 is not None:
            self.p2.prev=self.p2.next
            self.p2.next=self.p1
            self.p1=self.p2
            self.p2=self.p2.prev
        self.head=self.p1
        print("List reversed\n")
                
if __name__=='__main__': 

    llist = LinkedList() 
    while(1):
        print("1.Display\n")
        print("2.Insert new node at the beginning\n")
        print("3.Insert new node at the end\n")
        print("4.Insert new node after the given node\n")
        print("5.Delete node\n")
        print("6.Reverse list\n")
        print("7.Quit\n\n")
        print("Enter your choice : ")
        choice=int(input())
        if(choice==1):
            llist.display()
        elif(choice==2):
            value=int(input())
            llist.insert_at_beg(value)
        elif(choice==3):
            value=int(input())
            llist.insert_at_end(value)
        elif(choice==4):
            print("enter the value")
            value=int(input())
            print("Enter the element after which to insert : ")
            item=int(input())
            llist.insert_after_given_node(value,item)
        elif(choice==5):
            value=int(input())
            llist.delete(value) 
        elif(choice==6):
            llist.reverse() 
        else:
            sys.exit(0)
1.Display

2.Insert new node at the beginning

3.Insert new node at the end

4.Insert new node after the given node

5.Delete node

6.Reverse list

7.Quit


Enter your choice : 
2
10
1.Display

2.Insert new node at the beginning

3.Insert new node at the end

4.Insert new node after the given node

5.Delete node

6.Reverse list

7.Quit


Enter your choice : 
2
20
1.Display

2.Insert new node at the beginning

3.Insert new node at the end

4.Insert new node after the given node

5.Delete node

6.Reverse list

7.Quit


Enter your choice : 
2
30
1.Display

2.Insert new node at the beginning

3.Insert new node at the end

4.Insert new node after the given node

5.Delete node

6.Reverse list

7.Quit


Enter your choice : 
5
10
1.Display

2.Insert new node at the beginning

3.Insert new node at the end

4.Insert new node after the given node

5.Delete node

6.Reverse list

7.Quit


Enter your choice : 
6
List reversed

1.Display

2.Insert new node at the beginning

3.Insert new node at the end

4.Insert new node after the given node

5.Delete node

6.Reverse list

7.Quit


Enter your choice : 
1
20
30
1.Display

2.Insert new node at the beginning

3.Insert new node at the end

4.Insert new node after the given node

5.Delete node

6.Reverse list

7.Quit


Enter your choice : 
7
An exception has occurred, use %tb to see the full traceback.

SystemExit: 0

Circular Linked list

Circular Single Linked list

class Node:
    def __init__(self, info, next=None):
        self.info = info
        self.next = None
first = Node(10)
print("Node Info:",first.info)
print("Node next:",first.next)
Node Info: 10
Node next: None

#collapse-hide

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insertAtBeginning(self, element):
        newNode = Node(element)
        if self.head == None:
            self.head = newNode
            self.head.next = self.head
        else:
            current = self.head
            while(current.next != self.head):
                current = current.next
            current.next = newNode
            newNode.next = self.head
            self.head = newNode
            
    def insertAtEnd(self, element):
        newNode = Node(element)
        if self.head == None:
            self.head = newNode
            self.head.next = self.head
        else:
            current = self.head
            while(current.next != self.head):
                current = current.next
            current.next = newNode
            newNode.next = self.head
    
    def display(self):
        current = self.head
        while current.next != self.head:
            print(current.info)
            current = current.next
        print(current.info)
csll = LinkedList()
csll.insertAtBeginning(10)
csll.insertAtBeginning(20)
csll.insertAtBeginning(30)
csll.display()

print("*******")

csll.insertAtEnd(1)
csll.insertAtEnd(2)
csll.insertAtEnd(3)
csll.display()
30
20
10
*******
30
20
10
1
2
3

Circular Singly Linked list operations

considering only Worst Cases

  • insertAtBeginning() : $O(n)$
  • insertAtEnd() : $O(n)$
  • display() : $O(n)$