Python - Data Structures - Linked Lists

Linked Lists Data Structures in Python 

In Python, a linked list is a linear data structure that stores elements in a sequence, where each element is called a node and each node contains a link to the next node. While linked lists aren't supported natively by Python, they can be easily implemented.

A node contains two parts; A "data" and another "next", where data stores the actual value of the element. next stores the reference to the next node in sequence.

Types of Linked Lists

There are three types of linked lists:

1. Singly Linked List: In a singly linked list each node points to the next node, and the last node points to None.
2. Doubly Linked List: In a doubly linked list each node has two references, one to the next node and another to the previous node.
3. Circular Linked List: In a circular linked list the last node points back to the head node, forming a circle.

Advantages of Using Linked List

There are the following advantages of using a linked list:

• Dynamic Size
• Efficient Insertions & Deletion
• Better Memory Utilizations
• No Contiguous Memory Requirement
• Easy Implementations of Data Structure
• Infinite Expansion
• Efficient Handling of Frequent Changes
• Improved Performance for Sparse Data

Create a Singly Linked List

Below is an example of how to create and use a singly linked list:

class Node:
    def __init__(self, data):
        self.data = data  # The data part
        self.next = None  # The reference to the next node


class LinkedList:
    def __init__(self):
        # Initialize the linked list with an empty head
        self.head = None

    # Method to add a node at the end
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
         # Traverse to the last node
        while current.next:
            current = current.next
        current.next = new_node

    # Method to display the linked list
    def display(self):
        current = self.head
        # Traverse through the list
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    # Method to delete a node by value
    def delete(self, key):
        current = self.head

        # If the head node itself holds the key to be deleted
        if current and current.data == key:
            self.head = current.next  # Change head
            current = None
            return

        # Search for the key to be deleted, keep track of the previous node
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next

        # If the key was not present in the linked list
        if current is None:
            return

        # Unlink the node from the linked list
        prev.next = current.next
        current = None

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display()
ll.delete(20)
ll.display() 

Create a Doubly Linked List

Here is an implementation of a Doubly Linked List (DLL) in Python. In a DLL, each node has three parts: the data, a pointer to the previous node, and a pointer to the next node:

class Node:
    def __init__(self, data):
        # The data part
        self.data = data
        # Reference to the previous node
        self.prev = None
        # Reference to the next node
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    # Method to add a node at the end
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            # If the list is empty, make the new node the head
            self.head = new_node
            return
        current = self.head
        while current.next:  # Traverse to the last node
            current = current.next
        current.next = new_node
        new_node.prev = current 

    # Method to add a node at the beginning
    def prepend(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node 

    # Method to delete a node by value
    def delete(self, key):
        current = self.head
        while current:
            if current.data == key:  # Node to delete found
                if current.prev:  # If it's not the head node
                    current.prev.next = current.next
                else:  # If it's the head node
                    self.head = current.next
                if current.next:  # If it's not the last node
                    current.next.prev = current.prev
                current = None
                return
            current = current.next

    # Method to display the linked list from the beginning
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    # Method to display the linked list in reverse order
    def display_reverse(self):
        current = self.head
        if not current:
            print("None")
            return
        # Go to the last node
        while current.next:
            current = current.next
        # Traverse backward
        while current:
            print(current.data, end=" <-> ")
            current = current.prev
        print("None")

dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.display()
dll.display_reverse()
dll.prepend(5)
dll.display()
dll.delete(20)
dll.display()
dll.display_reverse() 

Create a Circular Linked List

A circular linked list (CLL) is a linked list in which the last node points back to the head node, forming a circle. Circular linked lists can be either singly or doubly linked:

class Node:
    def __init__(self, data):
        self.data = data  # The data part
        self.next = None  # The reference to the next node


class CircularLinkedList:
    def __init__(self):
        self.head = None  # Initialize the list with an empty head

    # Method to append a node to the list
    def append(self, data):
        new_node = Node(data)
        if not self.head:  # If the list is empty
            self.head = new_node
            new_node.next = self.head  # Point the new node to itself
        else:
            current = self.head
            while current.next != self.head:  # Traverse to the last node
                current = current.next
            current.next = new_node  # Set the last node's next to the new node
            new_node.next = self.head  # Point the new node's next to the head

    # Method to display the circular linked list
    def display(self):
        if not self.head:
            print("List is empty")
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:  # Stop when we come back to the head
                break
        print("(back to head)")

    # Method to delete a node by value
    def delete(self, key):
        if not self.head:
            print("List is empty")
            return

        current = self.head
        prev = None

        # Check if the head node is to be deleted
        if current.data == key:
            if current.next == self.head:  # If there's only one node
                self.head = None
                return
            # Otherwise, find the last node to update its next pointer
            while current.next != self.head:
                current = current.next
            current.next = self.head.next
            self.head = self.head.next
            return

        # Search for the node to delete
        prev = self.head
        current = self.head.next
        while current != self.head:
            if current.data == key:
                prev.next = current.next
                return
            prev = current
            current = current.next
        print(f"Node with value {key} not found")

    # Method to insert a node after a specific value
    def insert_after(self, target, data):
        if not self.head:
            print("List is empty")
            return
        current = self.head
        while True:
            if current.data == target:
                new_node = Node(data)
                new_node.next = current.next
                current.next = new_node
                return
            current = current.next
            if current == self.head:  # Stop if we've traversed the whole list
                break
        print(f"Node with value {target} not found")

cll = CircularLinkedList()
cll.append(10)
cll.append(20)
cll.append(30)
cll.display() 
cll.insert_after(20, 25)
cll.display()
cll.delete(10)
cll.display()
cll.delete(40)

Use Cases of Linked-List

There are the following use cases of the linked list:

• Dynamic Memory Allocation: Linked lists work well in situations where the amount of memory is changing or is unknown in advance because they can expand and contract at runtime.
• Use of Other Data Structures: Graphs, stacks, queues, and other more intricate data structures are all implemented using linked lists as their foundation.
• Executing Repeated Insertions and Deletions: These are the recommended options for applications that need regular insertions and deletions since they can be achieved more effectively than with array-based structures.