Next: 4. Skiplists Up: 3. Linked Lists Previous: 3.3 : A Space-Efficient Contents Index
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.
to avoid
all the special cases that occur in the operations
,
,
, and
?
method,
, that returns
the second-last element of an
. Do this without using the
member variable,
, that keeps track of the size of the list.
operations
,
,
and
on an
. Each of these operations
should run in
time.
method,
that reverses the
order of elements in an
. This method should run in
time, should not use recursion, should not use any secondary data
structures, and should not create any new nodes.
and
methods called
.
These methods walk through the list and count the number of nodes to
see if this matches the value,
, stored in the list. These methods
return nothing, but throw an exception if the size they compute does
not match the value of
.
operation that creates a
node,
, and adds it in a
just before the node
. 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
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.
method
that returns
if the
list is a palindrome,
i.e., the element at position
is equal to
the element at position
for all
.
Your code should run in
time.
that ``rotates'' a
so that list
item
becomes list item
. This method should
run in
time and should not modify any nodes in
the list.
, that truncates a
at position
. After executing this method, the size of the list will be
and
it should contain only the elements at indices
. The
return value is another
that contains the elements at indices
. This method should run in
time.
method,
, that takes as an argument
a
,
, empties it and appends its contents, in order,
to the receiver. For example, if
contains 
and
contains 
, then after calling
,
will contain
and
will be empty.
that removes all the elements with odd-numbered
indices from a
and return a
containing these elements.
For example, if
, contains the elements
, then after
calling
,
should contain 
and a list containing
should be returned.
, that reverses the order of elements in
a
.
, as discussed in Section 11.1.1.
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.
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
.
method
that sorts the elements
contained in the list using the merge sort algorithm.
This recursive algorithm works in the following way:
method, split the list
into two lists of approximately equal length,
and
;
;
; and, finally,
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.
data structure that can store
comparable elements and supports the stack operations
,
, and
, as well as the
operation, which
returns the minimum value currently stored in the data structure.
All operations should run in constant time.
data structure that can store
comparable elements and supports the queue operations
,
, and
, as well as the
operation, which
returns the minimum value currently stored in the data structure.
All operations should run in constant amortized time.
data structure that can store
comparable elements and supports all the deque operations
,
,
and
, and the
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
:
is used like a
(so that the
only modifications to the
are done using
and
), then these
operations run in constant amortized time, independent of the value
of
.
that supports all
the
operations in constant amortized time per operation,
independent of the value of
.
^, to
swap the values of two
variables without using a third variable.opendatastructures.org