Types of Linked Lists

---

A linked list is a dynamic data structure where each element (node) contains data and a reference to the next node in the sequence. Linked lists are widely used in various algorithms and data manipulation tasks due to their flexibility and efficient memory usage.

---

Types of Linked Lists

There are three main types of linked lists:

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

Each type has its own unique properties and use cases, which we'll explore in detail.

---

1. Singly Linked List

A singly linked list is the simplest type of linked list. In a singly linked list, each node contains two parts:

• Data: The actual data stored in the node.
• Next: A reference (or pointer) to the next node in the list.

The list starts with a head pointer, which points to the first node. Each node points to the next node, and the last node points to None (null), indicating the end of the list.

Structure of a Singly Linked List:

• Head → Node 1 → Node 2 → Node 3 → None

Advantages:

• Memory efficient: Unlike arrays, linked lists do not require contiguous memory.
• Dynamic size: The size of a singly linked list can grow or shrink dynamically, as nodes can be added or removed easily.

Disadvantages:

• Traversal: To access an element, you have to traverse the list from the head to the desired position, which can be slower than array indexing.
• Single direction: You can only traverse the list in one direction (from head to tail).

Python Code Example (Singly Linked List):

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

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

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

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

# Example usage
ll = SinglyLinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
ll.traverse()  # Output: 10 -> 20 -> 30 -> None

---

2. Doubly Linked List

A doubly linked list is a more advanced version of the singly linked list. In this type of list, each node contains three parts:

• Data: The actual data stored in the node.
• Next: A reference to the next node in the list.
• Prev: A reference to the previous node in the list.

The head points to the first node, and the tail points to the last node. The last node's next pointer is None, and the first node’s prev pointer is None.

Structure of a Doubly Linked List:

• None ← Node 1 ⇔ Node 2 ⇔ Node 3 → None

Advantages:

• Two-way traversal: You can traverse the list in both directions (from head to tail or tail to head), making it more flexible.
• Efficient insertion/deletion: Insertion and deletion operations can be faster because you have direct access to the previous node, unlike singly linked lists where you need to traverse the list to find the previous node.

Disadvantages:

• More memory: Each node requires extra memory for the prev pointer, making it less memory-efficient than a singly linked list.
• Complexity: Managing both next and prev pointers can make implementation more complex.

Python Code Example (Doubly Linked List):

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

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

    def insert_at_end(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

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

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

# Example usage
dll = DoublyLinkedList()
dll.insert_at_end(10)
dll.insert_at_end(20)
dll.insert_at_end(30)
dll.traverse_forward()  # Output: 10 <-> 20 <-> 30 <-> None
dll.traverse_backward()  # Output: 30 <-> 20 <-> 10 <-> None

---

3. Circular Linked List

A circular linked list is a variation of the linked list in which the last node's next pointer points back to the head of the list, creating a circle. Circular linked lists can be either singly or doubly linked, but the key feature is that the last node points back to the first node.

Types of Circular Linked Lists:

• Singly Circular Linked List: The last node points to the head node, and each node only points to the next node.
• Doubly Circular Linked List: The last node points to the head, and the head's prev pointer points to the last node, creating a circular structure in both directions.

Structure of a Singly Circular Linked List:

• Node 1 → Node 2 → Node 3 → Node 1 (points back to the head)

Advantages:

• Efficient traversal: Once you reach the end, you can easily loop back to the beginning without checking for None.
• Memory efficiency: For circular implementations, once you reach the last node, you don't need to store an additional reference (like None in a singly linked list).

Disadvantages:

• Complexity: Managing the circular references can be tricky, especially when deleting or inserting nodes.
• Infinite loops: Without proper handling, circular linked lists can lead to infinite loops.

Python Code Example (Singly Circular Linked List):

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

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

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

    def traverse(self):
        current = self.head
        if not current:
            print("List is empty.")
            return
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("... (circular)")

# Example usage
cll = CircularLinkedList()
cll.insert_at_end(10)
cll.insert_at_end(20)
cll.insert_at_end(30)
cll.traverse()  # Output: 10 -> 20 -> 30 -> ... (circular)

 

---

---