B4.1.2 Evaluate linked lists. (HL only)

The big idea

A linked list is a data structure where elements (called nodes) are connected by references (or “links”), rather than being stored in a continuous block of memory like an array.

Each node contains:

• Data – the value stored in the node.
• Pointer(s) – reference(s) to the next node, and sometimes to the previous node.

Linked lists allow efficient insertion and deletion without shifting elements, but accessing elements requires traversal from the start.

 

1. Types of linked lists

Singly Linked List

• Each node has data and a pointer to the next node.
• Last node’s next pointer is None.

Structure:

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

 

Doubly Linked List

• Each node has data, a pointer to the next node, and a pointer to the previous node.
• Allows traversal in both directions.

Structure:

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

 

Circular Linked List

• Similar to singly or doubly, but the last node’s pointer links back to the first node.
• No None termination; traversal continues in a loop.

Structure (singly circular):

[Data|Next] → [Data|Next] → [Data|Next] ↺

 

2. Basic operations

a) Insertion (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 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

 

b) Deletion

    def delete(self, key):
        current = self.head
        # If head node holds the key
        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:  # Key found
            prev.next = current.next

 

c) Traversal

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

 

d) Search

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

 

3. Advantages and disadvantages

Aspect	Linked List	Array
Memory allocation	Dynamic — can grow/shrink as needed.	Fixed size (unless resized).
Insertion/deletion	O(1) if position is known (just change pointers).	O(n) because shifting elements is required.
Access time	O(n) — must traverse from start.	O(1) — direct index access.
Memory usage	Higher (stores extra pointer(s) for each node).	Lower (only stores data).
Cache friendliness	Poor — nodes may be scattered in memory.	Good — contiguous memory improves CPU cache performance.
Reordering elements	Easy — just change pointers.	Costly — requires moving data.

 

4. When to choose linked lists over arrays

• When frequent insertions/deletions occur, especially in the middle of the collection.
• When the size of the data changes frequently and unpredictably.
• When you don’t need fast random access by index.

 

5. Performance summary

Operation	Singly/Doubly LL (avg case)	Array (avg case)
Access by index	O(n)	O(1)
Search	O(n)	O(n)
Insert at start	O(1)	O(n)
Insert at end	O(1) with tail pointer, else O(n)	O(1) amortized (dynamic array)
Delete at start	O(1)	O(n)
Delete at end	O(n)	O(1) amortized