Chapter 10: Elementary Data Structures

This chapter examines the representation of dynamic sets using simple data structures that use pointers. We cover the rudimentary structures: stacks, queues, linked lists, and rooted trees, and show ways to synthesize objects and pointers from arrays.

---

10.1 Stacks and Queues

Stacks and queues are dynamic sets in which the element removed by the DELETE operation is prespecified.

• A stack implements a last-in, first-out (LIFO) policy — the element deleted is the one most recently inserted.
• A queue implements a first-in, first-out (FIFO) policy — the element deleted is the one that has been in the set the longest.

Stacks

• The INSERT operation on a stack is called PUSH.
• The DELETE operation (takes no element argument) is called POP.
• Only the top element is accessible — plates are popped in reverse order of how they were pushed.

Array implementation: A stack of at most n elements uses an array S[1..n] with an attribute S.top indexing the most recently inserted element.

• The stack consists of elements S[1..S.top], where S[1] is the bottom and S[S.top] is the top.
• When S.top = 0, the stack is empty.
• Underflow: attempting to pop an empty stack.
• Overflow: when S.top exceeds n.

Operations:

STACK-EMPTY(S)
1  if S.top == 0
2      return TRUE
3  else return FALSE

PUSH(S, x)
1  S.top = S.top + 1
2  S[S.top] = x

POP(S)
1  if STACK-EMPTY(S)
2      error "underflow"
3  else S.top = S.top - 1
4      return S[S.top + 1]

• Each operation runs in O(1) time.

Queues

• The INSERT operation is called ENQUEUE.
• The DELETE operation is called DEQUEUE (takes no element argument).
• The queue has a head (front) and a tail (back).
• Elements are enqueued at the tail and dequeued from the head.

Circular array implementation: A queue of at most n − 1 elements uses an array Q[1..n].

• Q.head indexes the head of the queue.
• Q.tail indexes the next location where a new element will be inserted.
• Elements reside in locations Q.head, Q.head + 1, ..., Q.tail − 1, wrapping around circularly (location 1 follows location n).
• Empty when Q.head == Q.tail. Initially Q.head = Q.tail = 1.
• Full when Q.head == Q.tail + 1, or both Q.head == 1 and Q.tail == Q.length.
• Underflow: dequeue from empty queue. Overflow: enqueue into full queue.

Operations:

ENQUEUE(Q, x)
1  Q[Q.tail] = x
2  if Q.tail == Q.length
3      Q.tail = 1
4  else Q.tail = Q.tail + 1

DEQUEUE(Q)
1  x = Q[Q.head]
2  if Q.head == Q.length
3      Q.head = 1
4  else Q.head = Q.head + 1
5  return x

• Each operation runs in O(1) time.

---

10.2 Linked Lists

A linked list is a data structure in which objects are arranged in a linear order determined by a pointer in each object (not by array indices). Linked lists provide a simple, flexible representation for dynamic sets.

Structure of a Doubly Linked List

Each element of a doubly linked list L is an object with:

• A key attribute
• A next pointer — points to the successor
• A prev pointer — points to the predecessor

Key properties:

• If x.prev == NIL, then x is the head (first element).
• If x.next == NIL, then x is the tail (last element).
• L.head points to the first element. If L.head == NIL, the list is empty.

Variations of Linked Lists

Searching a Linked List

LIST-SEARCH finds the first element with key k via linear search:

LIST-SEARCH(L, k)
1  x = L.head
2  while x ≠ NIL and x.key ≠ k
3      x = x.next
4  return x

• Worst-case time: Θ(n) — may search the entire list.

Inserting into a Linked List

LIST-INSERT splices element x onto the front of the list:

LIST-INSERT(L, x)
1  x.next = L.head
2  if L.head ≠ NIL
3      L.head.prev = x
4  L.head = x
5  x.prev = NIL

• Running time: O(1).

Deleting from a Linked List

LIST-DELETE removes element x by updating pointers:

LIST-DELETE(L, x)
1  if x.prev ≠ NIL
2      x.prev.next = x.next
3  else L.head = x.next
4  if x.next ≠ NIL
5      x.next.prev = x.prev

• Running time: O(1) given a pointer to x.
• To delete by key, must first call LIST-SEARCH → Θ(n) worst case.

Sentinels

A sentinel is a dummy object that simplifies boundary conditions.

• We add an object L.nil that represents NIL and has all attributes of other list objects.
• This transforms the list into a circular, doubly linked list with a sentinel.
• L.nil lies between the head and tail:
  • L.nil.next → head of the list
  • L.nil.prev → tail of the list
• The attribute L.head is eliminated; use L.nil.next instead.
• An empty list: both L.nil.next and L.nil.prev point to L.nil.

Simplified operations with sentinel:

LIST-SEARCH'(L, k)
1  x = L.nil.next
2  while x ≠ L.nil and x.key ≠ k
3      x = x.next
4  return x

LIST-INSERT'(L, x)
1  x.next = L.nil.next
2  L.nil.next.prev = x
3  L.nil.next = x
4  x.prev = L.nil

LIST-DELETE'(L, x)
1  x.prev.next = x.next
2  x.next.prev = x.prev

Key points about sentinels:

• Rarely reduce asymptotic time bounds, but can reduce constant factors.
• Main benefit is clarity of code — eliminates boundary condition checks.
• Use judiciously — many small lists with sentinels can waste significant memory.

---

10.3 Implementing Pointers and Objects

How do we implement pointers and objects in languages that do not provide them? We can synthesize objects and pointers from arrays and array indices.

Multiple-Array Representation

Use a separate array for each attribute:

• key[x] — holds the key value
• next[x] — holds the index of the next element
• prev[x] — holds the index of the previous element

A pointer x is simply a common index into all three arrays. A variable L holds the index of the head.

Example: If key[5] = 16, next[5] = 2, and key[2] = 4, then the object with key 4 follows the object with key 16 in the list.

NIL is represented by an integer that cannot be a valid index (e.g., 0 or −1).

Single-Array Representation

Store all attributes of an object in a contiguous subarray:

• An object occupies A[j..k].
• Each attribute corresponds to an offset from the base index j.
• A pointer to the object is the index j.

Example with offsets: key = 0, next = 1, prev = 2:

• To read i.prev, access A[i + 2].

Advantages:

• Flexible — permits objects of different lengths in the same array.

Disadvantage:

• Managing heterogeneous collections is more complex.

For homogeneous elements (same attributes), the multiple-array representation is generally sufficient.

Allocating and Freeing Objects

To manage storage of unused objects, maintain a free list — a singly linked list of available objects using the next array.

• The head of the free list is held in a global variable free.
• The free list acts like a stack: the next object allocated is the last one freed.
• The free list may be intertwined with the actual linked list in the same arrays.

ALLOCATE-OBJECT()
1  if free == NIL
2      error "out of space"
3  else x = free
4      free = x.next
5      return x

FREE-OBJECT(x)
1  x.next = free
2  free = x

• Both operations run in O(1) time.
• A single free list can service multiple linked lists stored in the same arrays.
• Any attribute can serve as the next pointer in the free list for homogeneous collections.

---

10.4 Representing Rooted Trees

The methods for representing lists extend to any homogeneous data structure. Each node of a tree is represented by an object containing a key attribute and pointers to other nodes.

Binary Trees

Each node x has three pointer attributes:

• x.p — pointer to the parent
• x.left — pointer to the left child
• x.right — pointer to the right child

Key properties:

• If x.p == NIL, then x is the root.
• If x.left == NIL, the node has no left child (similarly for right).
• T.root points to the root of tree T. If T.root == NIL, the tree is empty.

Rooted Trees with Unbounded Branching

For trees where each node has at most k children, we can use child1, child2, ..., childk pointers. However, this fails when:

• The number of children is unbounded (don't know how many pointers to allocate).
• k is large but most nodes have few children → wastes memory.

Left-Child, Right-Sibling Representation

A clever scheme using only O(n) space for any n-node rooted tree:

Each node x has:

1. x.p — pointer to the parent
2. x.left-child — pointer to the leftmost child of x
3. x.right-sibling — pointer to the sibling immediately to the right of x

Rules:

• If x has no children: x.left-child == NIL
• If x is the rightmost child of its parent: x.right-sibling == NIL
• T.root points to the root of the tree.

This representation can handle arbitrary numbers of children per node with only 3 pointers per node (including parent).

Other Tree Representations

Different applications call for different representations:

• Heap (Chapter 6): complete binary tree stored in a single array with an index to the last node.
• Disjoint-set forests (Chapter 21): only parent pointers (no child pointers), since traversal is only toward the root.

The best scheme depends on the application.

---

Summary of Running Times