3.4 Discussion and Exercises

Both singly-linked and doubly-linked lists are folklore, having been used in programs for over 40 years. They are discussed, for example, by Knuth [39, Sections 2.2.3-2.2.5]. Even the $\mathtt{SEList}$ data structure seems to be a well-known data structures exercise.

Exercise 3..1   Why is it not possible, in an $\mathtt{SLList}$ to use a dummy node to avoid all the special cases that occur in the operations $\mathtt{push(x)}$, $\mathtt{pop()}$, $\mathtt{add(x)}$, and $\mathtt{remove()}$?

Exercise 3..2   Describe and implement the $\mathtt{List}$ operations $\mathtt{get(i)}$, $\mathtt{set(i,x)}$, $\mathtt{add(i,x)}$ and $\mathtt{remove(i)}$ on an $\mathtt{SLList}$. Each of these operations should run in $O(1+\ensuremath{\mathtt{i}})$ time.