Chapter 15 Key Takeaways: Dynamic Data Structures

Core Concepts

  1. Linked lists grow and shrink at runtime. Unlike arrays, which have a fixed size declared at compile time, linked lists allocate each node individually on the heap. There is no wasted space and no artificial capacity limit.

  2. A singly-linked list is a chain of nodes connected by Next pointers. The list is accessed through a Head pointer. Insertion at the head is O(1). Searching and deletion by value are O(n). Adding a tail pointer makes insertion at the tail O(1) as well.

  3. A doubly-linked list adds a Prev pointer to each node. This enables bidirectional traversal and simplifies deletion when you already have a pointer to the target node. The cost is one extra pointer per node.

  4. A stack enforces Last In, First Out (LIFO) access. The only operations are Push (add to top), Pop (remove from top), Peek (view top without removing), and IsEmpty. All are O(1). Stacks are implemented as linked lists where all operations occur at the head.

  5. A queue enforces First In, First Out (FIFO) access. The operations are Enqueue (add to rear), Dequeue (remove from front), Front (view front without removing), and IsEmpty. All are O(1) when using a linked list with both Front and Rear pointers.

  6. Circular lists and deques extend the basic structures. A circular list has no nil — the last node points back to the first. A deque supports insertion and removal at both ends, generalizing both stacks and queues.

Design Decisions

  1. Choose arrays for random access and cache performance. Choose linked lists for dynamic sizing and frequent insertions/deletions. Choose stacks for LIFO problems (undo, backtracking, expression evaluation). Choose queues for FIFO problems (scheduling, buffering, BFS).

  2. The Head pointer must be a var parameter in any procedure that might change it (insert at head, delete head, free list). Forgetting var is the most common linked-list bug.

  3. Every New must have a matching Dispose. Failing to dispose a node leaks memory. Accessing a node after disposing it creates a dangling pointer. Both are serious bugs that may not crash immediately but will cause problems eventually.

Patterns to Remember

  1. Traversal pattern: Current := Head; while Current <> nil do begin { process } Current := Current^.Next; end;

  2. Delete pattern: Save node in Temp, update links to bypass it, then Dispose(Temp). Never dispose before updating links.

  3. Free-entire-list pattern: while Head <> nil do begin Temp := Head; Head := Head^.Next; Dispose(Temp); end;

  4. Undo pattern: Push the inverse of each action onto a stack. To undo, pop and execute the inverse.

PennyWise Progress

  1. PennyWise now uses a linked list for expenses — no fixed capacity, no wasted memory, O(1) insertion.

  2. PennyWise now supports multi-level undo — each expense addition is recorded on a stack. Undoing pops the stack and removes the matching expense from the list.

Looking Ahead

In Chapter 16, we build on linked structures to create trees — hierarchical data structures where each node can have multiple children. Binary search trees combine the dynamic flexibility of linked lists with the fast lookup of sorted arrays, achieving O(log n) search.