[DS2] Linked List

1. What is Linked List?

1.1 Definition

A linked list is a linear data structure that includes a series of connected nodes. Here, each node stores the data and the address of the next node.

 

Starting point of linked list have a special name called HEAD. Also, the last node in the linked list can be identified because its next portion points to NULL.

 

Linked lists can be of multiple types : singly, doubly, and circular linked list.

 

1.2 Representation

Each node consists :

• A data item
• An address of another node

Each struct node has a data item and a pointer to another struct node.

1.3 Implementation Linked List

class Node: 
    def __init__(self, item):
        self.item = item
        self.next = None 
        
class LinkedList: 
    def __init__(self):
        self.head = None

 

2. Linked List Operations

• Traversal : access each element of the linked list
• Insertion : adds a new element to the linked list
• Deletion : removes the existing elements
• Search : find a node in the linked list
• Sort : sort the node of the linked list

 

2.1 Traversal a Linked List

Displaying the contents of a linked list is moving the temp node to the next one and display its contents.

 

2.2 Insert elements to a Linked List

1. Insert at the beginning
   1. Allocate memory for new node
   2. Store data
   3. Change next of new node to point to head
   4. Change head to point to recently created node
2. Insert at the End
   1. Allocate memory for new node
   2. Store data
   3. Traerse to last node
   4. Change next of last node to recently created node
3. Insert at the Middle
   1. Allocate memory and store data for new node
   2. Traverse to node just for the required position of new node
   3. Change next pointers to include new node in between

 

2.3 Delete from a Linked List

1. Delete from beginning
   1. Point head to the second node
2. Delete from end
   1. Traverse to second last element
   2. Change its next pointer to null
3. Delete from middle
   1. Traverse to element before the element to be deleted
   2. Change next pointers to exclude the node from the chain

 

2.4 Search an Element on a Linked List

1. Make head as the current node
2. Run a loop until the current node is None because the last element points to None.
3. In each iteration, check if the key of the node is equal to item. If it the key matches the item, return Ture otherwise return False.

 

2.5 Sort Elements of a Linked List

1. Make the head as the current node and create another node node index for later use.
2. If head is null, return.
3. Else, run a loop till the last node.
4. In each iteration, follow the following step 5 - 6.
5. Store the next node of current in index.
6. Check if the data of the current node is greater than the next node. If it is greater, swap current and index.

 

2.6 Operation implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None 
        
class LinkedList: 
    def __init__(self): 
        self.head = None 
        
    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node 
        
    def insertAfter(self, prev_node, new_data):
        if prev_node is None : 
            print("The given previous node must inLinkedList.")
            return
            
        new_node = Node(new_data)
        new_node.next = prev_node.next
        prev_node.next = new_node
        
    def insertAtEnd(self, new_data): 
        new_node = Node(new_data)
        
        if self.head is None : 
            self.head = new_node 
            return 
            
        last = self.head
        while (last.next):
            last = last.next
        last.next = new_node 
        
    def deleteNode(self, position):
        if self.head is None:
            return
        temp = self.head 
        if position == 0 : 
            self.head = temp.next 
            temp = None 
            return 
        
        # Find the key to be deleted
        for i in range(position - 1):
            temp = temp.next
            if temp is None: 
                break 
                
        if temp is None : return
        if temp.next is None : return 
        next = temp.next.next 
        temp.next = None 
        temp.next = next 
        
     def search(self, key):
        current = self.head

        while current is not None:
            if current.data == key:
                return True
            current = current.next
            
        return False
        
    def sortLinkedList(self, head): 
        current = head 
        index = Node(None) 
        
        if head is None : return 
        else : 
            while current is not None : 
                index = current.next 
                while index is not None : 
                    if current.data > index.data: 
                        current.data, index.data = index.data, current.data
                    index = index.next 
                current = current.next 
        
     def printList(self):
        temp = self.head
        while (temp):
            print(str(temp.data) + " ", end="")
            temp = temp.next

3. Source

https://www.programiz.com/dsa/linked-list-operations

Linked List Operations: Traverse, Insert and Delete