Linked Lists

📖 Introduction

When I first encountered linked lists, they seemed like a solution in search of a problem. Why use pointers when arrays work fine? The answer became clear when I started working with dynamic data—undo systems, browser history, task schedulers—where frequent insertions and deletions matter more than random access.

Linked lists taught me to think about memory differently: not as contiguous blocks, but as connected nodes scattered throughout the heap. Mastering pointer manipulation here laid the foundation for understanding trees, graphs, and many system-level data structures.

---

🎯 What Is a Linked List?

A linked list is a linear data structure where elements are connected by pointers rather than stored contiguously.

Node Structure

from typing import Optional
from dataclasses import dataclass

@dataclass
class ListNode:
    """Singly linked list node."""
    val: int
    next: Optional['ListNode'] = None


@dataclass
class DoublyListNode:
    """Doubly linked list node."""
    val: int
    prev: Optional['DoublyListNode'] = None
    next: Optional['DoublyListNode'] = None

Visual Representation

---

📊 Array vs Linked List

Operation	Array	Linked List
Access by index	O(1)	O(n)
Search	O(n)	O(n)
Insert at beginning	O(n)	O(1)
Insert at end	O(1)*	O(n) or O(1)†
Insert in middle	O(n)	O(1)‡
Delete at beginning	O(n)	O(1)
Delete at end	O(1)	O(n) or O(1)†
Memory	Contiguous, cache-friendly	Scattered, pointer overhead

*Amortized for dynamic arrays †O(1) if tail pointer maintained ‡After finding position

# When to use linked lists
"""
✓ Frequent insertions/deletions at beginning
✓ Need to insert/delete in middle after traversal
✓ Memory allocation needs to be dynamic
✓ No random access needed
✓ Implementing stacks, queues, or deques

✗ Need random access
✗ Memory is limited (pointer overhead)
✗ Cache performance is critical
"""

---

🔧 Implementing Singly Linked List

from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: 'ListNode' = None):
        self.val = val
        self.next = next


class SinglyLinkedList:
    """
    Singly linked list implementation.
    """
    
    def __init__(self):
        self.head: Optional[ListNode] = None
        self.size = 0
    
    def __len__(self) -> int:
        return self.size
    
    def __str__(self) -> str:
        """String representation: 1 -> 2 -> 3 -> None"""
        values = []
        current = self.head
        while current:
            values.append(str(current.val))
            current = current.next
        return " -> ".join(values) + " -> None"
    
    def insert_at_head(self, val: int) -> None:
        """O(1) - Insert at beginning."""
        new_node = ListNode(val)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
    
    def insert_at_tail(self, val: int) -> None:
        """O(n) - Insert at end (no tail pointer)."""
        new_node = ListNode(val)
        
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        
        self.size += 1
    
    def insert_at_index(self, index: int, val: int) -> bool:
        """O(n) - Insert at specific index."""
        if index < 0 or index > self.size:
            return False
        
        if index == 0:
            self.insert_at_head(val)
            return True
        
        new_node = ListNode(val)
        current = self.head
        
        for _ in range(index - 1):
            current = current.next
        
        new_node.next = current.next
        current.next = new_node
        self.size += 1
        return True
    
    def delete_at_head(self) -> Optional[int]:
        """O(1) - Delete from beginning."""
        if not self.head:
            return None
        
        val = self.head.val
        self.head = self.head.next
        self.size -= 1
        return val
    
    def delete_at_tail(self) -> Optional[int]:
        """O(n) - Delete from end."""
        if not self.head:
            return None
        
        if not self.head.next:
            val = self.head.val
            self.head = None
            self.size -= 1
            return val
        
        current = self.head
        while current.next.next:
            current = current.next
        
        val = current.next.val
        current.next = None
        self.size -= 1
        return val
    
    def delete_value(self, val: int) -> bool:
        """O(n) - Delete first occurrence of value."""
        if not self.head:
            return False
        
        if self.head.val == val:
            self.head = self.head.next
            self.size -= 1
            return True
        
        current = self.head
        while current.next and current.next.val != val:
            current = current.next
        
        if current.next:
            current.next = current.next.next
            self.size -= 1
            return True
        
        return False
    
    def find(self, val: int) -> Optional[int]:
        """O(n) - Find index of value."""
        current = self.head
        index = 0
        
        while current:
            if current.val == val:
                return index
            current = current.next
            index += 1
        
        return None
    
    def get(self, index: int) -> Optional[int]:
        """O(n) - Get value at index."""
        if index < 0 or index >= self.size:
            return None
        
        current = self.head
        for _ in range(index):
            current = current.next
        
        return current.val


# Usage example
ll = SinglyLinkedList()
ll.insert_at_head(3)
ll.insert_at_head(2)
ll.insert_at_head(1)
print(ll)  # 1 -> 2 -> 3 -> None

ll.insert_at_tail(4)
print(ll)  # 1 -> 2 -> 3 -> 4 -> None

ll.insert_at_index(2, 99)
print(ll)  # 1 -> 2 -> 99 -> 3 -> 4 -> None

---

🔧 Implementing Doubly Linked List

from typing import Optional

class DoublyListNode:
    def __init__(self, val: int = 0):
        self.val = val
        self.prev: Optional['DoublyListNode'] = None
        self.next: Optional['DoublyListNode'] = None


class DoublyLinkedList:
    """
    Doubly linked list with head and tail pointers.
    O(1) operations at both ends.
    """
    
    def __init__(self):
        # Sentinel nodes simplify edge cases
        self.head = DoublyListNode(0)  # Dummy head
        self.tail = DoublyListNode(0)  # Dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
    
    def __len__(self) -> int:
        return self.size
    
    def __str__(self) -> str:
        values = []
        current = self.head.next
        while current != self.tail:
            values.append(str(current.val))
            current = current.next
        return " <-> ".join(values) if values else "Empty"
    
    def _insert_between(
        self,
        val: int,
        predecessor: DoublyListNode,
        successor: DoublyListNode
    ) -> DoublyListNode:
        """Helper: Insert node between two nodes."""
        new_node = DoublyListNode(val)
        new_node.prev = predecessor
        new_node.next = successor
        predecessor.next = new_node
        successor.prev = new_node
        self.size += 1
        return new_node
    
    def _delete_node(self, node: DoublyListNode) -> int:
        """Helper: Delete a specific node."""
        predecessor = node.prev
        successor = node.next
        predecessor.next = successor
        successor.prev = predecessor
        self.size -= 1
        return node.val
    
    def insert_at_head(self, val: int) -> None:
        """O(1) - Insert at beginning."""
        self._insert_between(val, self.head, self.head.next)
    
    def insert_at_tail(self, val: int) -> None:
        """O(1) - Insert at end."""
        self._insert_between(val, self.tail.prev, self.tail)
    
    def delete_at_head(self) -> Optional[int]:
        """O(1) - Delete from beginning."""
        if self.size == 0:
            return None
        return self._delete_node(self.head.next)
    
    def delete_at_tail(self) -> Optional[int]:
        """O(1) - Delete from end."""
        if self.size == 0:
            return None
        return self._delete_node(self.tail.prev)
    
    def get_head(self) -> Optional[int]:
        """O(1) - Peek at head."""
        if self.size == 0:
            return None
        return self.head.next.val
    
    def get_tail(self) -> Optional[int]:
        """O(1) - Peek at tail."""
        if self.size == 0:
            return None
        return self.tail.prev.val


# Usage example
dll = DoublyLinkedList()
dll.insert_at_tail(1)
dll.insert_at_tail(2)
dll.insert_at_tail(3)
print(dll)  # 1 <-> 2 <-> 3

dll.insert_at_head(0)
print(dll)  # 0 <-> 1 <-> 2 <-> 3

dll.delete_at_tail()
print(dll)  # 0 <-> 1 <-> 2

---

🏃 Fast and Slow Pointers

Floyd's cycle detection algorithm uses two pointers moving at different speeds.

Detecting Cycles

def has_cycle(head: Optional[ListNode]) -> bool:
    """
    Detect if linked list has a cycle.
    Time: O(n), Space: O(1)
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False


def find_cycle_start(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    Find the node where cycle begins.
    Time: O(n), Space: O(1)
    """
    if not head or not head.next:
        return None
    
    slow = fast = head
    
    # Phase 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            break
    else:
        return None  # No cycle
    
    # Phase 2: Find cycle start
    # Reset slow to head, move both at same speed
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

Finding Middle Element

def find_middle(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    Find middle node of linked list.
    For even length, returns second middle.
    Time: O(n), Space: O(1)
    """
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow


def find_first_middle(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    Find middle node; for even length, returns first middle.
    """
    slow = fast = head
    
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow

Nth Node From End

def nth_from_end(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    """
    Find nth node from end.
    Time: O(n), Space: O(1)
    """
    fast = head
    
    # Move fast n steps ahead
    for _ in range(n):
        if not fast:
            return None
        fast = fast.next
    
    slow = head
    
    # Move both until fast reaches end
    while fast:
        slow = slow.next
        fast = fast.next
    
    return slow


def remove_nth_from_end(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    """
    Remove nth node from end and return new head.
    """
    dummy = ListNode(0)
    dummy.next = head
    
    fast = dummy
    slow = dummy
    
    # Move fast n+1 steps ahead
    for _ in range(n + 1):
        fast = fast.next
    
    # Move both until fast reaches end
    while fast:
        slow = slow.next
        fast = fast.next
    
    # Remove the node
    slow.next = slow.next.next
    
    return dummy.next

---

🔄 Common Linked List Operations

Reversing a Linked List

def reverse_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    Reverse linked list iteratively.
    Time: O(n), Space: O(1)
    """
    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


def reverse_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    Reverse linked list recursively.
    Time: O(n), Space: O(n) for call stack
    """
    # Base case: empty or single node
    if not head or not head.next:
        return head
    
    # Recursively reverse the rest
    new_head = reverse_recursive(head.next)
    
    # Reverse current pointer
    head.next.next = head
    head.next = None
    
    return new_head


def reverse_between(
    head: Optional[ListNode],
    left: int,
    right: int
) -> Optional[ListNode]:
    """
    Reverse portion of list from position left to right.
    Positions are 1-indexed.
    """
    if not head or left == right:
        return head
    
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    
    # Move to node before reversal starts
    for _ in range(left - 1):
        prev = prev.next
    
    # Reverse from left to right
    current = prev.next
    for _ in range(right - left):
        next_node = current.next
        current.next = next_node.next
        next_node.next = prev.next
        prev.next = next_node
    
    return dummy.next

Merging Two Sorted Lists

def merge_sorted_lists(
    l1: Optional[ListNode],
    l2: Optional[ListNode]
) -> Optional[ListNode]:
    """
    Merge two sorted linked lists.
    Time: O(n + m), Space: O(1)
    """
    dummy = ListNode(0)
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    # Attach remaining nodes
    current.next = l1 if l1 else l2
    
    return dummy.next


def merge_k_sorted_lists(lists: list) -> Optional[ListNode]:
    """
    Merge k sorted linked lists.
    Time: O(N log k) where N is total nodes, k is number of lists
    """
    import heapq
    
    # Handle ListNode comparison
    class NodeWrapper:
        def __init__(self, node):
            self.node = node
        
        def __lt__(self, other):
            return self.node.val < other.node.val
    
    dummy = ListNode(0)
    current = dummy
    heap = []
    
    # Initialize heap with first node of each list
    for l in lists:
        if l:
            heapq.heappush(heap, NodeWrapper(l))
    
    while heap:
        wrapper = heapq.heappop(heap)
        node = wrapper.node
        current.next = node
        current = current.next
        
        if node.next:
            heapq.heappush(heap, NodeWrapper(node.next))
    
    return dummy.next

Checking Palindrome

def is_palindrome(head: Optional[ListNode]) -> bool:
    """
    Check if linked list is palindrome.
    Time: O(n), Space: O(1)
    """
    if not head or not head.next:
        return True
    
    # Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse second half
    second_half = reverse_iterative(slow.next)
    
    # Compare halves
    first_half = head
    is_pal = True
    
    while second_half:
        if first_half.val != second_half.val:
            is_pal = False
            break
        first_half = first_half.next
        second_half = second_half.next
    
    # Restore list (optional)
    slow.next = reverse_iterative(slow.next)
    
    return is_pal

---

🎯 Advanced Linked List Problems

Add Two Numbers

def add_two_numbers(
    l1: Optional[ListNode],
    l2: Optional[ListNode]
) -> Optional[ListNode]:
    """
    Add two numbers represented as reversed linked lists.
    342 + 465 = 807 → (2->4->3) + (5->6->4) = (7->0->8)
    Time: O(max(m, n)), Space: O(max(m, n))
    """
    dummy = ListNode(0)
    current = dummy
    carry = 0
    
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        
        total = val1 + val2 + carry
        carry = total // 10
        
        current.next = ListNode(total % 10)
        current = current.next
        
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    
    return dummy.next

Intersection of Two Lists

def get_intersection_node(
    headA: Optional[ListNode],
    headB: Optional[ListNode]
) -> Optional[ListNode]:
    """
    Find intersection node of two linked lists.
    Time: O(m + n), Space: O(1)
    """
    if not headA or not headB:
        return None
    
    ptrA, ptrB = headA, headB
    
    # When reaching end, switch to other list's head
    # Both pointers travel same total distance
    while ptrA != ptrB:
        ptrA = ptrA.next if ptrA else headB
        ptrB = ptrB.next if ptrB else headA
    
    return ptrA  # Either intersection or None

Flatten Multilevel List

class MultilevelNode:
    def __init__(self, val: int):
        self.val = val
        self.prev = None
        self.next = None
        self.child = None


def flatten_multilevel(head: Optional[MultilevelNode]) -> Optional[MultilevelNode]:
    """
    Flatten multilevel doubly linked list.
    Child nodes are inserted between current and next.
    """
    if not head:
        return None
    
    current = head
    
    while current:
        if current.child:
            # Find tail of child list
            child_tail = current.child
            while child_tail.next:
                child_tail = child_tail.next
            
            # Connect child tail to current's next
            child_tail.next = current.next
            if current.next:
                current.next.prev = child_tail
            
            # Connect current to child
            current.next = current.child
            current.child.prev = current
            current.child = None
        
        current = current.next
    
    return head

Copy List with Random Pointer

class RandomListNode:
    def __init__(self, val: int):
        self.val = val
        self.next = None
        self.random = None


def copy_random_list(head: Optional[RandomListNode]) -> Optional[RandomListNode]:
    """
    Deep copy list with random pointers.
    Time: O(n), Space: O(n)
    """
    if not head:
        return None
    
    # Step 1: Create copies interleaved with originals
    current = head
    while current:
        copy = RandomListNode(current.val)
        copy.next = current.next
        current.next = copy
        current = copy.next
    
    # Step 2: Set random pointers for copies
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next
    
    # Step 3: Separate original and copy lists
    dummy = RandomListNode(0)
    copy_current = dummy
    current = head
    
    while current:
        copy_current.next = current.next
        copy_current = copy_current.next
        current.next = current.next.next
        current = current.next
    
    return dummy.next

---

📝 Practice Exercises

Exercise 1: Reorder List

def reorder_list(head: Optional[ListNode]) -> None:
    """
    Reorder: L0 → L1 → ... → Ln-1 → Ln
    To: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...
    
    Modify in-place.
    """
    # Hint: Find middle, reverse second half, merge
    pass

Solution

def reorder_list(head: Optional[ListNode]) -> None:
    if not head or not head.next:
        return
    
    # Find middle
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse second half
    second = slow.next
    slow.next = None
    prev = None
    
    while second:
        next_node = second.next
        second.next = prev
        prev = second
        second = next_node
    
    second = prev
    
    # Merge two halves
    first = head
    while second:
        first_next = first.next
        second_next = second.next
        
        first.next = second
        second.next = first_next
        
        first = first_next
        second = second_next

Exercise 2: Rotate List

def rotate_right(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    """
    Rotate list to the right by k places.
    Example: [1, 2, 3, 4, 5], k=2 → [4, 5, 1, 2, 3]
    """
    pass

Solution

def rotate_right(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    if not head or not head.next or k == 0:
        return head
    
    # Find length and connect tail to head (make circular)
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1
    
    tail.next = head  # Make circular
    
    # Find new tail position
    k = k % length
    steps_to_new_tail = length - k
    
    new_tail = head
    for _ in range(steps_to_new_tail - 1):
        new_tail = new_tail.next
    
    new_head = new_tail.next
    new_tail.next = None
    
    return new_head

Exercise 3: Partition List

def partition(head: Optional[ListNode], x: int) -> Optional[ListNode]:
    """
    Partition list so nodes < x come before nodes >= x.
    Preserve relative order within each partition.
    """
    pass

Solution

def partition(head: Optional[ListNode], x: int) -> Optional[ListNode]:
    # Create two dummy heads
    less_head = ListNode(0)
    greater_head = ListNode(0)
    
    less = less_head
    greater = greater_head
    
    while head:
        if head.val < x:
            less.next = head
            less = less.next
        else:
            greater.next = head
            greater = greater.next
        head = head.next
    
    # Connect the two partitions
    greater.next = None  # Important: avoid cycle
    less.next = greater_head.next
    
    return less_head.next

---

🔑 Key Takeaways

1. Linked lists excel at O(1) insertions/deletions with known positions

2. Dummy nodes simplify edge cases (empty list, single node)

3. Two pointers solve many problems efficiently

4. Fast/slow pointers detect cycles and find midpoints

5. Reversing is a fundamental operation—know both iterative and recursive

6. Draw diagrams when manipulating pointers—it prevents errors

---

🚀 What's Next?

In the next article, we'll explore stacks and queues:

• LIFO and FIFO principles

• Implementation using arrays and linked lists

• Monotonic stacks

• Priority queues with heaps

Next: Article 6 - Stacks and Queues

---

📚 References

• CLRS Chapter 10: Elementary Data Structures

• LeetCode Linked List problems

• "Cracking the Coding Interview" - Linked Lists chapter