10. Elementary Data Structures

Exercises

10.1-1

Available in the latest revision of the IM.

10.1-2

Illustration of stack operations PUSH(S, 4), PUSH(S, 1), PUSH(S, 3), POP(S), PUSH(S, 8), and POP(S), where items in red are returned from a POP function.

10.1-3

Available in the latest revision of the IM.

10.1-4

Illustration of queue operations ENQUEUE(Q, 4), ENQUEUE(Q, 1), ENQUEUE(Q, 3), DEQUEUE(Q), ENQUEUE(Q, 8), and DEQUEUE(Q), where items in red are returned from a DEQUEUE function and those in blue are garbage.

10.1-5

Available in the latest revision of the IM.

10.1-6

A detailed treatment of this topic is available here.

10.1-7

Available in the latest revision of the IM.

10.1-8

Available in the latest revision of the IM.

It is also possible to switch the running times by letting Push execute in $\Theta(n)$ time and Pop in $O(1)$. We need two labels for queues: primary and auxiliary.Suppose the former is $Q_1$ and the latter is $Q_2$ when a new element is pushed onto a stack. It should go into $Q_2$ and afterward the content of $Q_1$ needs to be poured into $Q_2$. Finally, the labels should be swapped. The Pop operation simply reads the next element from a primary queue.

10.2-1

Available in the latest revision of the IM.

10.2-2

Available in the latest revision of the IM.

10.2-3

Available in the latest revision of the IM.

The solution in the IM is wrong. After adding the new attribute L.tail, the Enqueue operation should be implemented by List-Insert(x, L.tail) and Dequeue by List-Delete(L, L.head). The proposed List-Delete(L, L.tail) takes $\Theta(n)$ in the worst case, since we need to find the predecessor of L.tail.

10.2-4

Available in the latest revision of the IM.

The solution in the IM only works when both $S_1$ and $S_2$ are nonempty.

Using a singly linked list, adorned with a tail pointer, is a much leaner data structure than a circular, doubly linked list with a sentinel.

10.2-5

Available in the latest revision of the IM.

★ 10.2-6

Available in the latest revision of the IM.

10.3-1

       15
       / \
      /   \
     /     \
    /       \
   17       20
   / \      /
 22  13    25
     / \     \
    12 28    33
             /
            14

10.3-2

Available in the latest revision of the IM.

10.3-3

Available in the latest revision of the IM.

10.3-4

Available in the latest revision of the IM.

★ 10.3-5

Available in the latest revision of the IM.

★ 10.3-6

Available in the latest revision of the IM.

Problems

10-1 Comparisons among lists

The starred items for insertion assume that we already know the positions of new nodes.

	unsorted, singly linked	sorted, singly linked	unsorted, doubly linked	sorted, doubly linked
Search	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$
Insert	$O(1)$	$\Theta(1)^*$	$O(1)$	$\Theta(1)^*$
Delete	$\Theta(n)$	$\Theta(n)$	$O(1)$	$O(1)$
Successor	$\Theta(n)$	$O(1)$	$\Theta(n)$	$O(1)$
Predecessor	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	$O(1)$
Minimum	$\Theta(n)$	$O(1)$	$\Theta(n)$	$O(1)$
Maximum	$\Theta(n)$	$\Theta(n)^*$	$\Theta(n)$	$O(1)$

If we adorn a sorted, singly linked list with a tail pointer, then finding the maximum takes $O(1)$ time.

10-2 Mergeable heaps using linked lists

I recommend reading the lecture notes about mergeable heaps. It introduces a binomial heap, as specific variant of mergeable heap, that also supports two additional operations: decreasing a key of some node and deleting a node. Essentially, the text follows Problem 19-2 from the 3rd edition of the book. For a deep dive into this topic, you might want to read the full Chapter 19 from the previous edition, which is freely downloadable from the book's official website.

There is a bug in the implementation of MergeTree. The first line should be changed to read as follows:

if T1.key > T2.key:

10-3 Searching a sorted compact list 🌟

This exercise introduces a methodologically valuable approach to algorithm analysis by constructing a functionally equivalent variant that is more conducive to formal examination. In particular, the revised algorithm separates the mechanisms of random jumps and linear search through the introduction of an additional parameter that governs the former. This structural decoupling substantially simplifies the associated mathematical analysis and provides a clearer framework for understanding the algorithm’s behaviour.

Available in the latest revision of the IM.