Introduction to Linked Lists

Linked lists are one of the fundamental data structures in computer science. They are dynamic collections of nodes, where each node contains a value and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements at any position in the list.

Basic Concepts

A linked list consists of two primary components:

1. Node: The basic unit of a linked list, containing:

   • A value (data)
   • A reference (link) to the next node

2. Head: The first node in the list, serving as the starting point for traversal

Types of Linked Lists

There are several types of linked lists, each with its own characteristics and use cases:

Singly Linked List

In a singly linked list, each node only points to the next node in the sequence.

# Example of a Singly Linked List Node in Python
class Node:
    def __init__(self, data):
        self.data = data  # Value of the node
        self.next = None  # Reference to the next node

# Example of a Singly Linked List
class LinkedList:
    def __init__(self):
        self.head = None  # Initialize the head to None (empty list)

    # Function to insert a new 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
        last_node = self.head
        while last_node.next:  # Traverse to the end of the list
            last_node = last_node.next
        last_node.next = new_node  # Link the new node at the end

    # Function to display the linked list
    def print_list(self):
        current_node = self.head
        while current_node:  # Traverse through the list and print each node
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

# Example usage
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()  # Output: 1 -> 2 -> 3 -> None

Key Points of a Singly Linked List:

• Dynamic Size: Singly linked lists can grow and shrink in size dynamically, making them more flexible than arrays.
• Efficient Insertions/Deletions: Insertions and deletions can be done efficiently, especially at the beginning and end of the list.
• Sequential Access: Each node can only be accessed sequentially, starting from the head.

---

Doubly Linked List

In a doubly linked list, each node has two references: one pointing to the next node and another pointing to the previous node. This allows for traversal in both directions.

# Example of a Doubly Linked List Node in Python
class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None  # Reference to the previous node
        self.next = None  # Reference to the next node

# Example of a Doubly Linked List
class DoublyLinkedList:
    def __init__(self):
        self.head = None

    # Function to insert a new node at the end
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
        new_node.prev = last_node  # Link the new node back to the last node

    # Function to display the linked list in forward direction
    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" <-> ")
            current_node = current_node.next
        print("None")

# Example usage
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.print_list()  # Output: 1 <-> 2 <-> 3 <-> None

Key Points of a Doubly Linked List:

• Bidirectional Traversal: Unlike singly linked lists, doubly linked lists can be traversed both forwards and backwards.
• Increased Memory Usage: Each node requires additional memory to store the reference to the previous node.
• Efficient Deletions: Deletions of nodes can be done more efficiently since the previous node is accessible without needing to traverse from the head.

---

Circular Linked List

In a circular linked list, the last node points back to the first node, forming a circular structure. Circular linked lists can be singly or doubly linked.

# Example of a Circular Singly Linked List Node in Python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Example of a Circular Singly Linked List
class CircularLinkedList:
    def __init__(self):
        self.head = None

    # Function to insert a new node at the end
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head  # Point to itself to make it circular
            return
        last_node = self.head
        while last_node.next != self.head:
            last_node = last_node.next
        last_node.next = new_node
        new_node.next = self.head  # Point the new node to the head

    # Function to display the linked list
    def print_list(self):
        if not self.head:
            return
        current_node = self.head
        while True:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
            if current_node == self.head:  # Stop when we reach the head again
                break
        print("(head)")
        
# Example usage
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.print_list()  # Output: 1 -> 2 -> 3 -> (head)

Key Points of a Circular Linked List:

• Circular Structure: The last node in the list points back to the head, creating a circular structure.
• Efficient Traversal: Useful for scenarios where the list needs to be traversed continuously, such as in round-robin scheduling.
• No Null End: There is no None at the end of the list, as the last node points back to the head.

---

Common Operations on Linked Lists

Insertion at the Beginning

def insert_at_beginning(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

Deletion from the End

def delete_from_end(self):
    if not self.head:
        return
    if not self.head.next:  # If there's only one element
        self.head = None
        return
    second_last = self.head
    while second_last.next.next:
        second_last = second_last.next
    second_last.next = None

Advantages of Linked Lists

• Dynamic Size: Unlike arrays, linked lists can grow or shrink dynamically, making them more flexible for memory management.
• Efficient Insertions/Deletions: Insertions and deletions are efficient, particularly at the beginning or middle of the list.

Disadvantages of Linked Lists

• Sequential Access: Linked lists only support sequential access, making it slower to access elements at specific positions compared to arrays.
• Memory Overhead: Each node in a linked list requires additional memory to store pointers to the next or previous node.

---

Linked lists are a foundational concept in data structures, and understanding their variations and operations is essential for developing efficient algorithms and systems. They are widely used in various real-world applications such as memory management, file systems, and dynamic data handling.