> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-iii-data-structures/10.-elementary-data-structures.md). # 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](https://www.happycoders.eu/algorithms/implement-deque-using-array/). ### 10.1-7 **Available in the latest revision of the IM.** ### 10.1-8 **Available in the latest revision of the IM.** {% hint style="info" %} 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. {% endhint %} ### 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.** {% hint style="danger" %} 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`. {% endhint %} ### 10.2-4 **Available in the latest revision of the IM.** {% hint style="warning" %} 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. {% endhint %} ### 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 linkedsorted, singly linkedunsorted, doubly linkedsorted, doubly linked
Search\Theta(n)\Theta(n)\Theta(n)\Theta(n)
InsertO(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)
{% hint style="info" %} If we adorn a sorted, singly linked list with a *tail* pointer, then finding the maximum takes $$O(1)$$ time. {% endhint %} ### 10-2 Mergeable heaps using linked lists I recommend reading the [lecture notes](https://cse.sc.edu/~fenner/csce750/notes/notes-mergeable-heaps.pdf) 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. {% hint style="danger" %} There is a bug in the implementation of `MergeTree`. The first line should be changed to read as follows: 
if T1.key > T2.key:
{% endhint %} ### 10-3 Searching a sorted compact list 🌟 {% hint style="success" %} 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. {% endhint %} **Available in the latest revision of the IM.**