Linked Lists

Introduction

In the world of data structures, linked lists are fundamental building blocks that allow for efficient insertion and deletion operations. Unlike arrays, which provide fast access to elements by index but require shifting elements when inserting or deleting, linked lists offer a more flexible approach to managing collections of data.

Linked lists consist of nodes where each node contains data and a reference (or link) to the next node in the sequence. This structure allows for dynamic memory allocation and efficient traversal in both directions (for doubly linked lists).

Concept

Singly Linked List

A singly linked list is the simplest form of a linked list, where each node points only to the next node in the sequence. The last node points to null, indicating the end of the list.

Structure

• Node: Contains data and a reference to the next node.
• Head: Points to the first node in the list.
• Tail: Points to the last node in the list (optional for efficient appending).

Advantages

• Dynamic memory allocation.
• Efficient insertion and deletion at any position.

Disadvantages

• Sequential access only; random access is inefficient.
• Requires additional space for storing pointers.

Doubly Linked List

A doubly linked list extends the concept of a singly linked list by adding an extra reference in each node that points to the previous node. This allows traversal in both directions.

Structure

• Node: Contains data, a reference to the next node, and a reference to the previous node.
• Head: Points to the first node in the list.
• Tail: Points to the last node in the list (optional for efficient appending).

Advantages

• Bi-directional traversal.
• Efficient insertion and deletion at any position.

Disadvantages

• Requires more memory due to additional pointers.

Circular Linked List

A circular linked list is a variation where the last node points back to the head of the list, forming a circle. This structure can be either singly or doubly linked.

Structure

• Node: Similar to singly or doubly linked lists.
• Head: Points to the first node in the list.
• Tail: Points to the last node, which points back to the head.

Advantages

• No need to maintain a tail pointer (in singly circular lists).
• Useful for implementing circular queues and round-robin scheduling.

Disadvantages

• Traversal can be more complex as it requires checking for the loop condition.
• Insertion or deletion at the end of the list is slightly more complex.

Examples

Let's explore practical examples of each type of linked list using Python.

Singly Linked List Example

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Usage
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Output: 1 -> 2 -> 3 -> None

Doubly Linked List Example

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display_forward(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    def display_backward(self):
        current = self.head
        if not current:
            return
        while current.next:
            current = current.next
        while current:
            print(current.data, end=" <-> ")
            current = current.prev
        print("None")

# Usage
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display_forward()  # Output: 1 <-> 2 <-> 3 <-> None
dll.display_backward() # Output: 3 <-> 2 <-> 1 <-> None

Circular Linked List Example

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
            return
        last = self.head
        while last.next != self.head:
            last = last.next
        last.next = new_node
        new_node.next = self.head

    def display(self):
        current = self.head
        if not current:
            return
        print(current.data, end=" -> ")
        current = current.next
        while current != self.head:
            print(current.data, end=" -> ")
            current = current.next
        print("...")

# Usage
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.display()  # Output: 1 -> 2 -> 3 -> ...