The list is a generalization of both stacks and queues, which are linear structures into (respectively, from) which items can be inserted (resp., removed). But where these insertions and removals can occur is very restricted. In a stack, they occur at the same end, called the top, which gives rise to a LIFO ("last-in-first-out") insertion/removal pattern. In queues, insertions occur at one end, the rear, and removals at the other end, the front, which gives rise to a FIFO ("first-in-first-out") insertion/removal pattern. In the most restrictive versions of stacks and queues, we are also limited as to which items are observable: in a stack, only the item at the top can be observed; in a queue, only the item at the front.
If we lift these restrictions so as to allow insertion and deletion anywhere, plus the capability of navigation (i.e., "moving around" among the items), we get the concept of a list. Different varieties of lists are obtained by making different choices as to exactly which operations are included to provide these capabilities. The kind of list we present here represents only one such choice, which we refer to as the List-with-Cursors paradigm.
We can view a list as a sequence of nodes, in each of which is stored a data item. Each node has a predecessor and a successor, with the exception of the first and last nodes. If we consider the first node to be the successor of the last, we arrive at the concept of a circular list or ring, as opposed to a grounded list. In this document, we will focus upon grounded lists.
Here is one possible depiction of a (grounded) list of animals:
+---+ +---+ +---+ +---+ +---+ +---+ +---+ | C | | D | | B | | A | | O | | Y | | C | | A |----| O |----| U |----| N |----| W |----| A |----| O |----★ | T | | G | | G | | T | | L | | K | | W | ^ +---+ +---+ +---+ +---+ +---+ +---+ +---+ | ^ | | | | | front rear |
In (most versions of) lists, observation and mutation may occur not only at the two ends but also in the middle. Thus, we need some mechanism for maneuvering (or navigating) through the structure and for viewing what's there. For this purpose, we introduce the concept of a cursor, which can be positioned at any of a list's nodes or at the special rear position that follows the list's last node. (Note that the front position corresponds to a list's first node, unless the list is empty (i.e., has no nodes), in which case the front and rear positions coincide.)
Most of the operations that we define on lists-with-cursors are done with respect to a cursor. For example, to access the contents of a node, we place a cursor at that node and then invoke the cursor's getItem() operation (which, as the name suggests, retrieves the data in the node at which the cursor is positioned). Similarly, to remove a node, we place a cursor there and invoke its remove() operation.
Hence, to express our specification for List-with-Cursors in Java, we use two interfaces, one for cursors and one for lists.
Specification:
public interface ListWithCursors<T> {
int lengthOf(); // returns # nodes in the list
ListCursor<T> getCursor(); // returns a cursor into the list
}
|
public interface ListCursor<T> {
/** observers **/
boolean atFront(); // is cursor at front of list?
boolean atRear(); // is cursor at rear of list?
T getItem(); // returns (reference to) item at cursor's position
// returns (a reference to) the list that "owns" this cursor
ListWithCursors<T> getList()
// Note: precondition of getItem() is !atRear()
/** navigation **/
// For the client's convenience, each navigation operation not only
// positions the cursor but also returns it.
ListCursor<T> toFront(); // positions cursor at front of list
ListCursor<T> toRear(); // positions cursor at rear of list
ListCursor<T> toNext(); // moves cursor one place towards rear
ListCursor<T> toPrev(); // moves cursor one place towards front
// positions this cursor at same place as the given one
ListCursor<T> setTo(ListCursor<T> c);
// Note : precondition of toNext() is !atRear()
// precondition of toPrev() is !atFront()
void dispose(); // "kills" this cursor
/** list mutation **/
T remove(); // removes node at which cursor is positioned
void replace(T newItem); // replaces item at cursor's position
void insert(T newItem); // inserts new node, containing the specified item,
// as predecessor of cursor's position
// Note : precondition of remove() and replace() is !atRear()
}
|
Arrays vs. Lists:
Some authors present a version of the list concept that is really a hybrid between the list and the array, or what might be called an indexed list or squishy array (as it was called by our late colleague Jack Beidler). Java's List interface take this point of view.
But there are significant differences between arrays and lists (as traditionally understood, at least). Placing a value into a specified location/index within an array has the effect of replacing the element that had occupied that location. But you can't literally insert a new element into an array, nor can you remove one. You can only replace. With lists, this restriction does not apply.
On the other hand, in a list, retrieving (or replacing) the k-th element, for a specified value of k, is not —in contrast to arrays— a "primitive" operation in the sense that locating the specified element is, generally, not a trivial task.
As an example, consider any Java class that implements Java's List interface (e.g., ArrayList or LinkedList), and suppose that list is a variable bound to an object of one of those classes. Then the call list.get(4) retrieves the 4-th element of list and the call list.set(4,x) replaces the 4th element by the value of x. These operations are analogous to retrieving a value from, and replacing a value in, an array, respectively, where the element's location is specified via an index value. But one can also make the calls list.add(4,y) and list.remove(4), the former of which inserts the value of x into position 4 (and bumps the elements formerly at positions 4, 5, 6, etc., to positions 5, 6, 7, etc.) and the latter of which removes the value at position 4 (and bumps those at positions 5, 6, 7, etc., into positions 4, 5, 6, etc.). There are no "primitive" operations upon an array that can do this.
So then why would we ever choose to use an array when we instead could choose to use a more versatile structure, such as an object from the ArrayList or LinkedList class? The answer is that by restricting mutation operations to replace alone (and not supporting insert and remove), both indexed-based retrieval (i.e., get-kth-element) and mutation (i.e., replace-kth-element) can be carried out by constant-time algorithms (i.e., algorithms whose running times do not depend upon the length of the array).
Supporting, in addition, the insert-at-position-k and remove-at-position-k operations imposes a performance penalty. That is, whatever underlying representation scheme is chosen, supporting not only indexed-based retrieval and replacement but also insertion and removal results in one or more of those operations requiring time that depends upon the number of elements in the list.
This is just one example of a more general truth in computing, which is that often there is a tradeoff between performance and versatility: Given two abstractions/interfaces A and B, where A supports all the operations provided by B, plus more, the likelihood is that an implementation of B will exhibit superior performance (in terms of running times and/or memory usage) to an (equally good) implementation of A.
Having sketched a (rather large, compared to the ADT's we've already seen) collection of operations, let's do a few list "applications".
Problem #0: Develop a method that finds the length of (i.e., the
number of nodes in) a list. (Ignore the fact that we stipulated the
existence of a lengthOf() operation!)
Solution:
public int lengthOf(ListWithCursors list) {
int cntr = 0;
ListCursor c = list.getCursor();
c.toFront();
// loop invariant: cntr = # of nodes preceding c's position
while ( !c.atRear() ) {
cntr = cntr + 1;
c.toNext();
}
c.dispose();
return cntr;
}
|
Problem #1: Develop a method that finds the sum of the values
in a list of items from the wrapper class Integer.
Solution:
public static int sumOf(ListWithCursors<Integer> list) {
int sumSoFar = 0;
ListCursor<Integer> c = list.getCursor();
c.toFront();
// loop invariant:
// sumSoFar == sum of list elements at nodes preceding c's position
while ( !c.atRear() ) {
sumSoFar = sumSoFar + c.getItem();
c.toNext();
}
c.dispose();
return sumSoFar;
}
|
Here we see an algorithmic pattern that is quite common: traversing a list, examining each node, and, in doing so, performing some operation that helps in the accumulation of some result.
Trivial modifications to the method yield solutions to similar problems such as, say, counting the number of nodes containing positive values. Here, we would replace the assignment statement inside the loop with this if statement:
if (c.getItem() > 0)
{ cntr = cntr + 1; }
|
Problem #2: For each node in a given list of items from the
(wrapper) class Integer, increment its value if it is
positive, decrement it if it is negative, and don't change it
if it is zero.
Solution:
public static void incOrDec(ListWithCursors<Integer> list ) {
ListCursor<Integer> c = list.getCursor();
c.toFront();
while ( !c.atRear() )
int y = c.getItem();
if (y < 0)
{ c.replace(y-1); }
else if (y > 0)
{ c.replace(y+1); }
else // y = 0
{ }
c.toNext();
}
c.dispose();
}
|
Problem #3:
Remove from a list any node containing the same value (as determined by
the equals() method) as its predecessor.
That is, the final state of the list should be such that it contains the
same sequence of values as originally, but with no consecutive duplicates.
Solution:
public static <T> void removeAdjacentDuplicates(ListWithCursors<T> list)
{
if (list.lengthOf() < 2)
{ }
else {
ListCursor<T> pred, crrnt;
pred = list.getCursor().toFront();
crrnt = list.getCursor().toFront().toNext();
// loop invariant: there are no adjacent duplicates in the portion of
// list preceding 'crrnt'; also, 'pred' and 'crrnt' are at adjacent
// positions, the latter being the successor of the former
*/
while ( !crrnt.atRear() ) {
if (pred.getItem().equals(crrnt.getItem()))
{ crrnt.remove(); }
else {
pred.toNext(); // or, equivalently, pred.setTo(crrnt);
crrnt.toNext();
}
}
pred.dispose(); crrnt.dispose();
}
}
|
Problem #4:
Assuming that the items in list are in ascending order with
respect to the Comparator comp, insert a new item into its
rightful place.
Solution:
/* pre: list is in ascending order (with respect to comp)
** post: list is still in ascending order, and is the same as before,
** except that a new node containing obj appears in it
*/
public static <T> void orderedInsert(ListWithCursors<T> list,
Comparator<T> comp,
T datum) {
ListCursor<T> cur = list.getCursor();
cur.toFront();
/* loop invariant:
** All nodes preceding cur contain values less than datum
*/
while (!cur.atRear() && comp.compare(datum, cur.getItem()) > 0)
{ cur.toNext(); }
// assertion: either
// (1) cur.atRear() and datum is larger than every item in list, or
// (2) !cur.atRear() and the node at which cur is positioned is the
// first one containing a value greater than or equal to datum
cur.insert(datum);
cur.dispose();
}
|
Problem #5: Sorting.
Given an array of objects and a comparator comp that defines a
total ordering upon them, construct an ascending-ordered list containing
the objects in the array.
Solution:
public static <T> ListWithCursors<T> sort(T[] a, Comparator<T> comp)
{
ListWithCursors<T> list = new ListWithCursorsViaX<T>();
for (int i=0; i != a.length; i = i+1) {
orderedInsert(list, comp, a[i]); // from previous problem
}
return list;
}
|
Here we have assumed that ListWithCursorsViaX is a (concrete) Java class that implements the ListWithCursors interface.
Suppose that the objects in the array were in "random" order. What would be the expected asymptotic running time of this sorting algorithm, as a function of the length of the array? Well, on average we would expect each call to orderedInsert() to traverse half the list (that has been constructed so far) before finding the right place to insert the new node. The list grows by one in length each time a new item is inserted. Thus, we should expect that the running time would be proportional to (1/2)(0+1+2+ ... +(N-1)), which is about N2/4 and thus in the complexity class O(N2).
Problem #6: Partitioning. Given a list of objects, a Comparator by which to compare them, and a "pivot" object, rearrange the items in the list so that, upon completion, all those less than the pivot precede those not less than the pivot. The returned cursor corresponds to the position at which the not-less-than-the pivot objects begin. Note that this solution requires that the equals() method on cursors yield true iff two cursors are at the same position (within the same list!) and thus does not necessarily correspond to ==.
Solution #1:
public ListCursor<T> <T> void partition1(ListWithCursors<T> list,
Comparator<T> comp,
T pivot) {
int compareResult;
ListCursor<T> cLeft = list.getCursor();
ListCursor<T> cRight = list.getCursor();
cLeft.toFront();
cRight.toRear();
/* loop invariant: The set of items in the list is fixed ∧
** all nodes preceding cLeft are less than the pivot ∧
** all nodes at or following cRight are not less than the pivot.
*/
while (!cLeft.equals(cRight)) {
compareResult = comp.compare(cLeft.getItem(), pivot);
if (compareResult >= 0) {
cRight.insert(cLeft.getItem());
cRight.toPrev();
cLeft.remove();
}
else {
cLeft.toNext();
}
}
cRight.dispose();
return cLeft;
}
|
We next illustrate the method above using an example in which the list contains Integer values, the pivot is 27, and the Comparator implements the standard ordering on numbers.
Before first loop iteration:
7 15 2 35 42 10 50 29 8 *
^ ^
| |
| |
cLeft cRight
|
After three iterations, during each of which cLeft advances past
a number that is less than 27 (the pivot):
7 15 2 35 42 10 50 29 8 *
^ ^
| |
| |
cLeft cRight
|
After one more iteration, during which the node pointed to by
cLeft (35) is removed but a node containing the same value is inserted
in front of cRight, which is then positioned at that new node:
7 15 2 42 10 50 29 8 35 *
^ ^
| |
| |
cLeft cRight
|
After one more iteration, which takes similar actions as the
previous one:
7 15 2 10 50 29 8 42 35 *
^ ^
| |
| |
cLeft cRight
|
The next iteration advances cLeft past another value (10) smaller than
the pivot:
7 15 2 10 50 29 8 42 35 *
^ ^
| |
| |
cLeft cRight
|
After another iteration that removes a node (50) but inserts a new one
containing the same value:
7 15 2 10 29 8 50 42 35 *
^ ^
| |
| |
cLeft cRight
|
Yet another iteration that removes a node (29) and inserts a new one:
7 15 2 10 8 29 50 42 35 *
^ ^
| |
| |
cLeft cRight
|
The last iteration advances cLeft past a value (8) smaller than the pivot,
at which point cLeft and cRight are at the same place, and so the
loop terminates with both cursors positioned at the first list element
that is greater than or equal to the pivot:
7 15 2 10 8 29 50 42 35 *
^
|
|
cRight
cLeft
|
Solution #2: (A bit better, in that it uses the replace()
method rather than remove() or insert().)
public ListCursor<T> <T> void partition2(ListWithCursors<T> list,
Comparator<T> comp,
T pivot) {
int compareResult;
ListCursor<T> cLeft = list.getCursor();
ListCursor<T> cRight = list.getCursor();
cLeft.toFront();
cRight.toRear();
/* loop invariant: The set of nodes and items in list is fixed
** (although some pairs of nodes have had their items swapped) ∧
** all nodes preceding cLeft are less than the pivot ∧
** all nodes at or following cRight are not less than the pivot.
*/
while (!cLeft.equals(cRight)) {
if (comp.compare(cLeft.getItem(), pivot) < 0) {
cLeft.toNext();
}
else {
//assert: CLeft != cRight and cLeft.getItem() ≥ pivot
cRight.toPrev();
if (!cLeft.equals(cRight)) {
if (comp.compare(cRight.getItem(), pivot) >= 0) {
cRight.toPrev();
}
else {
// assert cRight.getItem() < pivot
// swap data items at the two cursor positions
T temp = cLeft.getItem();
cLeft.replace(cRight.getItem());
cRight.replace(temp);
}
}
}
}
cRight.dispose();
return cLeft;
}
|