3.4 Discussion and Exercises

Both singly-linked and doubly-linked lists are established techniques, having been used in programs for over 40 years. They are discussed, for example, by Knuth [46, Sections 2.2.3-2.2.5]. Even the $ \mathtt{SEList}$ data structure seems to be a well-known data structures exercise. The $ \mathtt{SEList}$ is sometimes referred to as an unrolled linked list [67].

Another way to save space in a doubly-linked list is to use so-called XOR-lists. In an XOR-list, each node, $ \mathtt{u}$, contains only one pointer, called $ \mathtt{u.nextprev}$, that holds the bitwise exclusive-or of $ \mathtt{u.prev}$ and $ \mathtt{u.next}$. The list itself needs to store two pointers, one to the $ \mathtt{dummy}$ node and one to $ \mathtt{dummy.next}$ (the first node, or $ \mathtt{dummy}$ if the list is empty). This technique uses the fact that, if we have pointers to $ \mathtt{u}$ and $ \mathtt{u.prev}$, then we can extract $ \mathtt{u.next}$ using the formula

$\displaystyle \ensuremath{\mathtt{u.next}} = \ensuremath{\mathtt{u.prev}} \verb+^+ \ensuremath{\mathtt{u.nextprev}} \enspace .
$

(Here ^ computes the bitwise exclusive-or of its two arguments.) This technique complicates the code a little and is not possible in some languages that have garbage collection but gives a doubly-linked list implementation that requires only one pointer per node. See Sinha's magazine article [68] for a detailed discussion of XOR-lists.

Exercise 3..1   Why is it not possible to use a dummy node in an $ \mathtt{SLList}$ 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   Design and implement an $ \mathtt{SLList}$ method, $ \mathtt{secondLast()}$, that returns the second-last element of an $ \mathtt{SLList}$. Do this without using the member variable, $ \mathtt{n}$, that keeps track of the size of the list.

Exercise 3..3   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.

Exercise 3..4   Design and implement an $ \mathtt{SLList}$ method, $ \mathtt{reverse()}$ that reverses the order of elements in an $ \mathtt{SLList}$. This method should run in $ O(\ensuremath{\mathtt{n}})$ time, should not use recursion, should not use any secondary data structures, and should not create any new nodes.

Exercise 3..5   Design and implement $ \mathtt{SLList}$ and $ \mathtt{DLList}$ methods called $ \mathtt{checkSize()}$. These methods walk through the list and count the number of nodes to see if this matches the value, $ \mathtt{n}$, stored in the list. These methods return nothing, but throw an exception if the size they compute does not match the value of $ \mathtt{n}$.

Exercise 3..6   Try to recreate the code for the $ \mathtt{addBefore(w)}$ operation that creates a node, $ \mathtt{u}$, and adds it in a $ \mathtt{DLList}$ just before the node $ \mathtt{w}$. Do not refer to this chapter. Even if your code does not exactly match the code given in this book it may still be correct. Test it and see if it works.

The next few exercises involve performing manipulations on $ \mathtt{DLList}$s. You should complete them without allocating any new nodes or temporary arrays. They can all be done only by changing the $ \mathtt{prev}$ and $ \mathtt{next}$ values of existing nodes.

Exercise 3..7   Write a $ \mathtt{DLList}$ method $ \mathtt{isPalindrome()}$ that returns $ \mathtt{true}$ if the list is a palindrome, i.e., the element at position $ \mathtt{i}$ is equal to the element at position $ \ensuremath{\mathtt{n}}-i-1$ for all $ i\in\{0,\ldots,\ensuremath{\mathtt{n}}-1\}$. Your code should run in $ O(\ensuremath{\mathtt{n}})$ time.

Exercise 3..8   Implement a method $ \mathtt{rotate(r)}$ that ``rotates'' a $ \mathtt{DLList}$ so that list item $ \mathtt{i}$ becomes list item $ (\ensuremath{\mathtt{i}}+\ensuremath{\mathtt{r}})\bmod \ensuremath{\mathtt{n}}$. This method should run in $ O(1+\min\{\ensuremath{\mathtt{r}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{r}}\})$ time and should not modify any nodes in the list.

Exercise 3..9   Write a method, $ \mathtt{truncate(i)}$, that truncates a $ \mathtt{DLList}$ at position $ \mathtt{i}$. After executing this method, the size of the list will be $ \mathtt{i}$ and it should contain only the elements at indices $ 0,\ldots,\ensuremath{\mathtt{i}}-1$. The return value is another $ \mathtt{DLList}$ that contains the elements at indices $ \ensuremath{\mathtt{i}},\ldots,\ensuremath{\mathtt{n}}-1$. This method should run in $ O(\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$ time.

Exercise 3..10   Write a $ \mathtt{DLList}$ method, $ \mathtt{absorb(l2)}$, that takes as an argument a $ \mathtt{DLList}$, $ \mathtt{l2}$, empties it and appends its contents, in order, to the receiver. For example, if $ \mathtt{l1}$ contains $ a,b,c$ and $ \mathtt{l2}$ contains $ d,e,f$, then after calling $ \mathtt{l1.absorb(l2)}$, $ \mathtt{l1}$ will contain $ a,b,c,d,e,f$ and $ \mathtt{l2}$ will be empty.

Exercise 3..11   Write a method $ \mathtt{deal()}$ that removes all the elements with odd-numbered indices from a $ \mathtt{DLList}$ and return a $ \mathtt{DLList}$ containing these elements. For example, if $ \mathtt{l1}$, contains the elements $ a,b,c,d,e,f$, then after calling $ \mathtt{l1.deal()}$, $ \mathtt{l1}$ should contain $ a,c,e$ and a list containing $ b,d,f$ should be returned.

Exercise 3..12   Write a method, $ \mathtt{reverse()}$, that reverses the order of elements in a $ \mathtt{DLList}$.

Exercise 3..13   This exercise walks you through an implementation of the merge-sort algorithm for sorting a $ \mathtt{DLList}$, as discussed in Section 11.1.1.
  1. Write a $ \mathtt{DLList}$ method called $ \mathtt{takeFirst(l2)}$. This method takes the first node from $ \mathtt{l2}$ and appends it to the the receiving list. This is equivalent to $ \mathtt{add(size(),l2.remove(0))}$, except that it should not create a new node.
  2. Write a $ \mathtt{DLList}$ static method, $ \mathtt{merge(l1,l2)}$, that takes two sorted lists $ \mathtt{l1}$ and $ \mathtt{l2}$, merges them, and returns a new sorted list containing the result. This causes $ \mathtt{l1}$ and $ \mathtt{l2}$ to be emptied in the proces. For example, if $ \mathtt{l1}$ contains $ a,c,d$ and $ \mathtt{l2}$ contains $ b,e,f$, then this method returns a new list containing $ a,b,c,d,e,f$.
  3. Write a $ \mathtt{DLList}$ method $ \mathtt{sort()}$ that sorts the elements contained in the list using the merge sort algorithm. This recursive algorithm works in the following way:
    1. If the list contains 0 or 1 elements then there is nothing to do. Otherwise,
    2. Using the $ \mathtt{truncate(size()/2)}$ method, split the list into two lists of approximately equal length, $ \mathtt{l1}$ and $ \mathtt{l2}$;
    3. Recursively sort $ \mathtt{l1}$;
    4. Recursively sort $ \mathtt{l2}$; and, finally,
    5. Merge $ \mathtt{l1}$ and $ \mathtt{l2}$ into a single sorted list.

The next few exercises are more advanced and require a clear understanding of what happens to the minimum value stored in a $ \mathtt{Stack}$ or $ \mathtt{Queue}$ as items are added and removed.

Exercise 3..14   Design and implement a $ \mathtt{MinStack}$ data structure that can store comparable elements and supports the stack operations $ \mathtt{push(x)}$, $ \mathtt{pop()}$, and $ \mathtt{size()}$, as well as the $ \mathtt{min()}$ operation, which returns the minimum value currently stored in the data structure. All operations should run in constant time.

Exercise 3..15   Design and implement a $ \mathtt{MinQueue}$ data structure that can store comparable elements and supports the queue operations $ \mathtt{add(x)}$, $ \mathtt{remove()}$, and $ \mathtt{size()}$, as well as the $ \mathtt{min()}$ operation, which returns the minimum value currently stored in the data structure. All operations should run in constant amortized time.

Exercise 3..16   Design and implement a $ \mathtt{MinDeque}$ data structure that can store comparable elements and supports all the deque operations $ \mathtt{addFirst(x)}$, $ \mathtt{addLast(x)}$ $ \mathtt{removeFirst()}$, $ \mathtt{removeLast()}$ and $ \mathtt{size()}$, and the $ \mathtt{min()}$ operation, which returns the minimum value currently stored in the data structure. All operations should run in constant amortized time.

The next exercises are designed to test the reader's understanding of the implementation and analysis of the space-efficient $ \mathtt{SEList}$:

Exercise 3..17   Prove that, if an $ \mathtt{SEList}$ is used like a $ \mathtt{Stack}$ (so that the only modifications to the $ \mathtt{SEList}$ are done using $ \ensuremath{\mathtt{push(x)}}\equiv
\ensuremath{\mathtt{add(size(),x)}}$ and $ \ensuremath{\mathtt{pop()}}\equiv \ensuremath{\mathtt{remove(size()-1)}}$), then these operations run in constant amortized time, independent of the value of $ \mathtt{b}$.

Exercise 3..18   Design and implement of a version of an $ \mathtt{SEList}$ that supports all the $ \mathtt{Deque}$ operations in constant amortized time per operation, independent of the value of $ \mathtt{b}$.

Exercise 3..19   Explain how to use the bitwise exclusive-or operator, ^, to swap the values of two $ \mathtt{int}$ variables without using a third variable.

opendatastructures.org