Linked List Data Structure  – Implementation

Linked List Definition 

A linked list, like a regular python list, is an ordered collection of elements. It is a linear data structure. Unlike an array, the elements are not stored at a contiguous location in memory.  They link to the list using pointers.  As a common convention, the elements are called nodes, and each node is linked to the next one. The first node in the list is the Head and the last node linked to none

Each node stores the data and the reference to the next node. There are single and double-linked lists.  In a single linked list, the nodes are linked in one direction. On the other hand, in a double-linked list, the nodes are linked in both directions. 

List vs Liked list 

Regular list (array)

1. Elements are stored in contiguous memory locations
2. Element stored using an index which allows faster access
3. An array uses static memory allocation. To add more elements, the list needs to be recreated 
4. Direct or random access method
5. Binary or linear search

Linked list:

1. Elements are not stored in a contiguous memory location 
2. The elements also store a reference to the next node 
3. Linked lists use dynamic memory allocation, meaning memory can be allocated at run time
4. The maximum size depends on the heap
5. Sequential access
6. Linear search

Linked List use cases.

A linked list has several used cases in real-world scenarios, for example, they can be used to implement queues, stacks, graphs or to implement more complex tasks such as lifecycle management.

Linked List Implementation

Create a node class to hold data and reference to the next node.

# create a Node class to hold the data and reference to next node

class Node():
    def __init__(self, data =None) -> None:
        self.data = data
        self.next= None
        
    def __repr__(self) -> str:
        return self.data

Now create the linked list class with the possibility to create a linked list from the list of elements at once.

# create the Linked List class     
class Linked_list():
    def __init__(self, list_data=None) -> None:        
        self.head= None
        if list_data:
           node= Node(list_data.pop(0))
           self.head=node
           for item in list_data:
               node.next =Node(item)
               node = node.next

Create a print method to print the element in the list.

# printing the elements in the list
    def Print_elements(self):
        node = self.head
        list_of_nodes = []
        while node:
            list_of_nodes.append(node.data)
            node = node.next        
        return list_of_nodes

Create an iterator to traverse the linked list.

# create a interation 
    def __iter__(self):
        node = self.head
        while node is not None:
            yield node
            node = node.next

Add a new node at the beginning of the list

# inserting a node  at the begining of the list
    def insert_at_start(self, data):
        node = Node(data)
        node.next=self.head
        self.head= node

Add a new node at the end of the list.

 #inserting a node at the end of the list
    def insert_at_end(self, data):
        node = Node(data)
        if self.head is None:
            self.head =node
            return
        for current_node in self:
            pass
        current_node.next= node
        

Now let’s insert a new node after an existing node in the list

#inserting a new node after an existing node   
    def insert_after_node(self, target, data):
        new_node= Node(data)
        if self.head is None:
            raise Exception( ' Sorry the list is empty')
        for node in self:
            if node.data == target:
                new_node.next = node.next
                node.next= new_node
                return
        raise Exception( f" Sorry no Node  with data {target} is found")

Inserting a new node before an existing node in the list

#inserting a new node  before an existing node
    def insert_before_node(self, target, data):
        new_node= Node(data)
        if self.head is None:
            raise Exception( ' Sorry the list is empty')
        if self.head.data == target:
            return self.insert_at_start(new_node)
        prev_node =self.head
        for node in self:
            if node.data == target:
                prev_node.next = new_node
                new_node.next = node
                return
            prev_node = node
        raise Exception( f" Sorry no Node  with data {target} is found")

Deleting a node in the list

#deleting a node in the list
    def delete(self, target):
        if self.head is None:
            raise Exception( ' Sorry the list is empty')
        if self.head.data == target:
            self.head = self.head.next
            return
        prev_node = self.head
        for node in self:
            if node.data == target:
                prev_node.next =node.next
                return
            prev_node = node
        raise Exception( f" Sorry no Node  with data {target} is found")