Overview

This chapter introduces the fundamental building blocks for representing dynamic sets using simple pointer-based data structures. It covers stacks, queues, linked lists, and rooted trees—the rudimentary structures upon which more complex data structures are built. The chapter also demonstrates how to synthesize objects and pointers from arrays, which is essential for languages or environments without native pointer support.

Key Concepts

• Dynamic sets: Collections of elements that support operations like INSERT, DELETE, and SEARCH. The data structures in this chapter provide different tradeoffs for these operations.
• Stacks (LIFO policy): The element removed by DELETE is always the most recently inserted element. Supported by PUSH (insert) and POP (delete) operations. Implemented using an array S[1..n] with a top attribute tracking the most recently inserted element. An empty stack has S.top = 0. Underflow occurs when popping an empty stack; overflow when the stack exceeds capacity.
• Queues (FIFO policy): The element removed by DELETE is the one that has been in the set the longest. Supported by ENQUEUE (insert at tail) and DEQUEUE (delete from head). Implemented using a circular array Q[1..n] with head and tail attributes that wrap around, enabling the queue to use all n − 1 available slots.
• Linked lists: Objects arranged in a linear order determined by pointers (not array indices). A doubly linked list stores key, next, and prev pointers in each node. Variations include singly linked, sorted/unsorted, and circular lists.
• Sentinels: Dummy objects (e.g., L.nil) that simplify boundary-condition handling. A sentinel turns a regular doubly linked list into a circular doubly linked list, eliminating special cases for head/tail operations. Sentinels rarely improve asymptotic bounds but simplify code and may reduce constant factors.
• Multiple-array representation of objects: Simulates objects using parallel arrays (e.g., key[], next[], prev[]) where a common index represents one object.
• Single-array representation of objects: Stores each object in a contiguous subarray, with offsets for each attribute. A pointer is simply the starting index of the subarray.
• Free lists: A singly linked list of unused object slots managed like a stack. ALLOCATE-OBJECT pops from the free list; FREE-OBJECT pushes onto it. Both run in O(1) time.
• Rooted trees: Represented using pointer-based nodes. Binary trees use p, left, and right attributes. Trees with unbounded branching use the left-child, right-sibling representation, which stores only left-child and right-sibling pointers per node, achieving O(n) space for any n-node tree.

Algorithms and Techniques

Stack Operations

• STACK-EMPTY(S): Returns TRUE if S.top == 0.
• PUSH(S, x): Increments S.top and stores x at the new top position.
• POP(S): Checks for underflow, decrements S.top, and returns the element that was at the top.

Queue Operations

• ENQUEUE(Q, x): Stores x at Q[Q.tail], then advances Q.tail circularly (wrapping from position n back to position 1).
• DEQUEUE(Q): Reads and returns Q[Q.head], then advances Q.head circularly.