Chapter 2: Arrays and Linked Lists

Vol 2: Algorithm Forest Adventure · Station 2

---

Metadata Card

Attribute	Value
Chapter	Vol 2 · Chapter 2
Difficulty	(Foundation)
Prerequisites	Basic programming (variables, loops, functions)
Core Skills	Array/linked list operations, cache locality awareness, sentinel nodes
Keywords	Static Array Dynamic Array Singly Linked List Doubly Linked List Circular Linked List Cache Locality

---

Your Progress

Walking along the forest path, you suddenly face two forks — one straight and wide (array), one winding but flexible (linked list). Which path should you take?

---

Breakthrough · Origins

Array: Contiguous Memory Block

Why is random access O(1)? Because arr[k] = base address + k × element size. This is one multiplication + one addition machine instruction.

Dynamic Array (Python List)

import sys
arr = []
print(f"Initial capacity ≈ {sys.getsizeof(arr)} bytes")
for i in range(10):
    arr.append(i)
    print(f"len={len(arr)} size={sys.getsizeof(arr)}")

Singly Linked List

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

def get_kth(head: ListNode, k: int) -> ListNode:
    for _ in range(k):
        if not head:
            raise IndexError("k out of bounds")
        head = head.next
    return head

def insert_after(prev: ListNode, val: int):
    new_node = ListNode(val)
    new_node.next = prev.next
    prev.next = new_node

def reverse(head: ListNode) -> ListNode:
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev

Complexity Comparison

Operation	Array	Linked List
Random access	O(1)	O(n)
Insert at end	O(1) (amortized)	O(n) (no tail ptr) / O(1) (with tail ptr)
Insert in middle	O(n)	O(1) (if at position)
Delete at position	O(n)	O(1) (if at position)

Cache Locality (Brief)

Arrays store data contiguously → CPU prefetches nearby data → cache hits. Linked list nodes are scattered → each access likely causes a cache miss. In practice: arrays can be 10-100× faster than linked lists for sequential access.

---

Verification Checklist

• [ ] Can draw the memory structure of arrays and linked lists
• [ ] Can hand-write linked list node insertion and deletion
• [ ] Can explain "dynamic array append is amortized O(1)"
• [ ] Can explain why cache locality matters

---

Traveler's Notes

• Arrays are your most basic tool. 95% of the time, dynamic arrays are sufficient.
• Use linked lists when you frequently insert in the middle with many elements.
• High-frequency linked list operations: reverse, merge, detect cycle, find midpoint.

---

→ Next Stop Preview

Chapter 3: Stacks, Queues, and Deques — "Controlling the order of operations."