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 data structure seems to be a well-known data structures exercise. The 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, , contains only one pointer, called , that holds the bitwise exclusive-or of and . The list itself needs to store two pointers, one to the node and one to (the first node, or if the list is empty). This technique uses the fact that, if we have pointers to and , then we can extract using the formula

`^`

computes the bitwise exclusive-or of its two arguments.)
This technique complicates the code a little and is not possible in
some languages, like Java and Python, 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.

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

- Write a method called . This method takes the first node from and appends it to the the receiving list. This is equivalent to , except that it should not create a new node.
- Write a static method, , that takes two sorted lists and , merges them, and returns a new sorted list containing the result. This causes and to be emptied in the proces. For example, if contains and contains , then this method returns a new list containing .
- Write a
method
that sorts the elements
contained in the list using the merge sort algorithm.
This recursive algorithm works in the following way:
- If the list contains 0 or 1 elements then there is nothing to do. Otherwise,
- Using the method, split the list into two lists of approximately equal length, and ;
- Recursively sort ;
- Recursively sort ; and, finally,
- Merge and 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 or as items are added and removed.

The next exercises are designed to test the reader's understanding of the implementation and analysis of the space-efficient :

`^`

, to
swap the values of two
variables without using a third variable.opendatastructures.org