B4.1.3 Construct and apply linked lists: singly, doubly and circular. (HL only)

The big idea

A linked list is a sequence of nodes connected by pointers (references), where each node contains data and links to other nodes.
Unlike arrays, linked lists do not store elements in contiguous memory. Instead, they link nodes dynamically at runtime.

This design:

• Allows dynamic memory allocation (size can grow/shrink easily).
• Makes insertion and deletion efficient (no shifting of elements).
• Trades off fast random access — traversal is required to find elements.

There are three main types of linked lists:

1. Singly Linked List – links forward only.
2. Doubly Linked List – links forward and backward.
3. Circular Linked List – last node links back to the first.

 

1. Singly Linked List

Structure:

[Data|Next] → [Data|Next] → [Data|Next] → None

Python implementation:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class SinglyLinkedList:
    def __init__(self):
        self.head = None
    # Insertion at end
    def insert(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
    # Deletion by value
    def delete(self, key):
        current = self.head
        if current and current.data == key:
            self.head = current.next
            return
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        if current:
            prev.next = current.next
    # Traversal
    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")
    # Search
    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

 

2. Doubly Linked List

Structure:

None ← [Prev|Data|Next] ↔ [Prev|Data|Next] ↔ [Prev|Data|Next] → None

Python implementation:

class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None
class DoublyLinkedList:
    def __init__(self):
        self.head = None
    def insert(self, data):
        new_node = DNode(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.prev = current
    def delete(self, key):
        current = self.head
        while current and current.data != key:
            current = current.next
        if not current:
            return
        if current.prev:
            current.prev.next = current.next
        if current.next:
            current.next.prev = current.prev
        if current == self.head:
            self.head = current.next
    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")
    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

 

3. Circular Linked List

Structure (singly circular):

[Data|Next] → [Data|Next] → [Data|Next]
       ↑                              ↓
       └──────────────────────────────┘

Python implementation:

class CNode:
    def __init__(self, data):
        self.data = data
        self.next = None
class CircularLinkedList:
    def __init__(self):
        self.head = None
    def insert(self, data):
        new_node = CNode(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 delete(self, key):
        if not self.head:
            return
        current = self.head
        prev = None
        while True:
            if current.data == key:
                if prev:
                    prev.next = current.next
                else:
                    tail = self.head
                    while tail.next != self.head:
                        tail = tail.next
                    self.head = current.next
                    tail.next = self.head
                return
            prev = current
            current = current.next
            if current == self.head:
                break
    def traverse(self):
        if not self.head:
            print("Empty list")
            return
        current = self.head
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("(back to head)")
    def search(self, key):
        if not self.head:
            return False
        current = self.head
        while True:
            if current.data == key:
                return True
            current = current.next
            if current == self.head:
                break
        return False

 

Summary table of operations

Operation	Singly LL	Doubly LL	Circular LL
Insertion	O(1) at head, O(n) at tail	O(1) at head, O(n) at tail	Similar to singly, but wrap-around
Deletion	O(1) at head, O(n) elsewhere	O(1) at head, O(n) elsewhere	Similar to singly, with wrap-around
Traversal	Forward only	Forward/backward	Continuous loop possible
Search	O(n)	O(n)	O(n)