Linked List

Back to Index

A sequence of nodes where each node holds a value and a pointer to the next node. No random access.

Properties

• Access by index: O(n)
• Insert/delete at head: O(1)
• Insert/delete at arbitrary position (given pointer): O(1)
• Search: O(n)
• No built-in in Python — defined via class

Node Definition

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

Common Techniques

Dummy Head

Eliminates edge cases when the head itself might be modified.

dummy = ListNode(0)
dummy.next = head
curr = dummy
# ... manipulate list ...
return dummy.next

Fast / Slow Pointers (Two Pointers)

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow is at middle; if fast is None, no cycle

Reverse a Linked List

prev, curr = None, head
while curr:
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt
return prev

Key Insight

Always draw out pointer reassignments before coding - order of operations matters and is easy to get wrong.

---

Problems Using This Data Structure