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.



opendatastructures.org