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 SEList data structure seems to be a well-known data structures exercise.

Exercise 3..1   Why is it not possible, in an 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 List operations $\mathtt{get(i)}$, $\mathtt{set(i,x)}$, $\mathtt{add(i,x)}$ and $\mathtt{remove(i)}$ on an SLList. Each of these operations should run in $O(1+\ensuremath{\mathtt{i}})$ time.