Linked Lists

Introduction

Linked lists store elements in nodes scattered throughout memory, with each node pointing to the next. Unlike arrays, they sacrifice random access for efficient insertion and deletion anywhere in the list.

Learning Objectives

By the end of this reading, you will be able to:

• Implement singly and doubly linked lists
• Understand the tradeoffs between arrays and linked lists
• Perform common linked list operations
• Recognize when linked lists are appropriate

1. What is a Linked List?

A linked list is a sequence of nodes where each node contains:

1. Data: The value stored
2. Pointer(s): Reference(s) to other node(s)

Visual Representation

Singly Linked List:
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ data: 10  │    │ data: 20  │    │ data: 30  │    │ data: 40  │
│ next: ────┼───→│ next: ────┼───→│ next: ────┼───→│ next: None│
└───────────┘    └───────────┘    └───────────┘    └───────────┘
      ↑
     head

Doubly Linked List:
         ┌───────────────┐    ┌───────────────┐    ┌───────────────┐
         │ prev: None    │←───│ prev: ────────│←───│ prev: ────────│
         │ data: 10      │    │ data: 20      │    │ data: 30      │
         │ next: ────────│───→│ next: ────────│───→│ next: None    │
         └───────────────┘    └───────────────┘    └───────────────┘
               ↑                                         ↑
              head                                      tail

Key Differences from Arrays

2. Singly Linked List Implementation

Node Class

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

Linked List Class

class LinkedList:
    def __init__(self):
        self.head = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self.head is None

    def prepend(self, data):
        """Add to beginning: O(1)"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self._size += 1

    def append(self, data):
        """Add to end: O(n) without tail pointer"""
        new_node = Node(data)
        self._size += 1

        if self.head is None:
            self.head = new_node
            return

        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def insert_after(self, prev_node, data):
        """Insert after a given node: O(1)"""
        if prev_node is None:
            raise ValueError("Previous node cannot be None")

        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node
        self._size += 1

    def delete_value(self, data):
        """Delete first occurrence of value: O(n)"""
        if self.head is None:
            return False

        # Special case: delete head
        if self.head.data == data:
            self.head = self.head.next
            self._size -= 1
            return True

        # Find node before the one to delete
        current = self.head
        while current.next and current.next.data != data:
            current = current.next

        if current.next:  # Found it
            current.next = current.next.next
            self._size -= 1
            return True

        return False  # Not found

    def search(self, data):
        """Find node with value: O(n)"""
        current = self.head
        while current:
            if current.data == data:
                return current
            current = current.next
        return None

    def get(self, index):
        """Access by index: O(n)"""
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")

        current = self.head
        for _ in range(index):
            current = current.next
        return current.data

    def __str__(self):
        values = []
        current = self.head
        while current:
            values.append(str(current.data))
            current = current.next
        return " -> ".join(values) + " -> None"

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

Usage

lst = LinkedList()
lst.append(10)
lst.append(20)
lst.append(30)
lst.prepend(5)

print(lst)  # 5 -> 10 -> 20 -> 30 -> None

lst.delete_value(20)
print(lst)  # 5 -> 10 -> 30 -> None

for value in lst:
    print(value)

3. Optimized Singly Linked List with Tail

class LinkedListWithTail:
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

    def append(self, data):
        """Add to end: O(1) with tail pointer"""
        new_node = Node(data)
        self._size += 1

        if self.head is None:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def prepend(self, data):
        """Add to beginning: O(1)"""
        new_node = Node(data)
        self._size += 1

        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def pop_front(self):
        """Remove from beginning: O(1)"""
        if self.head is None:
            raise IndexError("Pop from empty list")

        data = self.head.data
        self.head = self.head.next
        self._size -= 1

        if self.head is None:
            self.tail = None

        return data

    # pop_back is still O(n) - need doubly linked for O(1)

4. Doubly Linked List

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


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

    def __len__(self):
        return self._size

    def append(self, data):
        """Add to end: O(1)"""
        new_node = DNode(data)
        self._size += 1

        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def prepend(self, data):
        """Add to beginning: O(1)"""
        new_node = DNode(data)
        self._size += 1

        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def delete_node(self, node):
        """Delete specific node: O(1)"""
        if node is None:
            return

        self._size -= 1

        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next

        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

    def pop_back(self):
        """Remove from end: O(1)"""
        if self.tail is None:
            raise IndexError("Pop from empty list")

        data = self.tail.data
        self.delete_node(self.tail)
        return data

    def pop_front(self):
        """Remove from beginning: O(1)"""
        if self.head is None:
            raise IndexError("Pop from empty list")

        data = self.head.data
        self.delete_node(self.head)
        return data

    def __str__(self):
        values = []
        current = self.head
        while current:
            values.append(str(current.data))
            current = current.next
        return " <-> ".join(values)

    def __reversed__(self):
        current = self.tail
        while current:
            yield current.data
            current = current.prev

5. Sentinel Nodes (Dummy Nodes)

Sentinel nodes simplify edge cases by eliminating null checks.

class SentinelLinkedList:
    def __init__(self):
        # Dummy head and tail nodes
        self.head = DNode(None)  # Sentinel head
        self.tail = DNode(None)  # Sentinel tail
        self.head.next = self.tail
        self.tail.prev = self.head
        self._size = 0

    def append(self, data):
        """No special case for empty list!"""
        new_node = DNode(data)
        new_node.prev = self.tail.prev
        new_node.next = self.tail
        self.tail.prev.next = new_node
        self.tail.prev = new_node
        self._size += 1

    def prepend(self, data):
        new_node = DNode(data)
        new_node.prev = self.head
        new_node.next = self.head.next
        self.head.next.prev = new_node
        self.head.next = new_node
        self._size += 1

    def delete_node(self, node):
        """Works for any non-sentinel node"""
        node.prev.next = node.next
        node.next.prev = node.prev
        self._size -= 1

6. Common Linked List Problems

Reverse a Linked List

def reverse(head):
    prev = None
    current = head

    while current:
        next_node = current.next  # Save next
        current.next = prev       # Reverse pointer
        prev = current            # Move prev forward
        current = next_node       # Move current forward

    return prev  # New head

Detect Cycle (Floyd's Algorithm)

def has_cycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

Find Cycle Start

def find_cycle_start(head):
    slow = fast = head

    # Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle

    # Find start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow

Find Middle Element

def find_middle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow  # Middle (or second middle if even length)

Merge Two Sorted Lists

def merge_sorted(l1, l2):
    dummy = Node(0)
    tail = dummy

    while l1 and l2:
        if l1.data <= l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 or l2
    return dummy.next

Check if Palindrome

def is_palindrome(head):
    # Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    prev = None
    while slow:
        next_node = slow.next
        slow.next = prev
        prev = slow
        slow = next_node

    # Compare halves
    left, right = head, prev
    while right:
        if left.data != right.data:
            return False
        left = left.next
        right = right.next

    return True

Remove Nth Node from End

def remove_nth_from_end(head, n):
    dummy = Node(0)
    dummy.next = head
    first = second = dummy

    # Advance first n+1 steps
    for _ in range(n + 1):
        first = first.next

    # Move both until first reaches end
    while first:
        first = first.next
        second = second.next

    # Remove the node
    second.next = second.next.next

    return dummy.next

7. Circular Linked List

The last node points back to the first.

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

    def append(self, data):
        new_node = Node(data)
        self._size += 1

        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def __iter__(self):
        if self.head is None:
            return

        current = self.head
        while True:
            yield current.data
            current = current.next
            if current == self.head:
                break

Use cases:

• Round-robin scheduling
• Circular buffers
• Multiplayer game turns

8. Complexity Summary

*Need to find previous node first

9. When to Use Linked Lists

Use Linked Lists When:

• Frequent insertions/deletions at beginning
• You already have reference to the node to delete (doubly)
• You don't know size in advance and it changes frequently
• Memory fragmentation is a concern

Prefer Arrays When:

• You need random access by index
• Cache performance matters
• Memory overhead should be minimized
• The collection rarely changes

Real-World Uses:

• Implementing stacks and queues
• Undo functionality (doubly linked)
• Browser history (doubly linked)
• Music playlist (circular doubly linked)
• Memory allocators (free lists)

Exercises

Basic

1. Implement count_nodes() that counts nodes iteratively.

2. Implement delete_at(index) that removes the node at a given position.

3. Write a function to print a linked list in reverse using recursion.

Intermediate

4. Implement remove_duplicates(head) for a sorted linked list.

5. Given two linked lists representing numbers (digits in reverse), add them:

2 -> 4 -> 3  (342)
5 -> 6 -> 4  (465)
Result: 7 -> 0 -> 8  (807)

6. Implement a method to split a linked list into two halves.

Advanced

7. Flatten a multilevel doubly linked list (nodes can have child pointers to sub-lists).

8. Implement LRU Cache using a doubly linked list and hash map.

9. Clone a linked list with random pointers (each node has an additional pointer to any node or null).

Summary

• Linked lists store nodes with data and pointers to other nodes
• Singly linked: one pointer (next)
• Doubly linked: two pointers (prev, next)
• O(1) insertion/deletion when you have the node reference
• O(n) access by index - must traverse
• Use sentinel nodes to simplify edge cases
• Choose based on operation frequency: frequent insertion/deletion vs frequent random access

Next Reading

Stacks and Queues →