11.2. Alternative List ADT Designs¶
The list ADT specifies that a List comprises not only a collection of objects in linear order, but also “the current position”. While this is a simple way to present the main concepts embodied by a list, it complicates any algorithm that relies on having two or more distinct “current positions” in the same list, such as any algorithm that steps from both ends towards the middle.
An alternative design is to separate the “current position” as a
separate object.
In the following ADT, we will call this a ListIndex.
This is a simple form of a concept that is sometimes called an
iterator.
The ListIndex interface abstracts the notion of a position in a
list.
interface ListIndex {
void prev();
void next();
}
interface List {
void clear();
void insert(Object it, ListIndex where);
void append(Object it);
Object remove(ListIndex where);
ListIndex getStart();
ListIndex getEnd();
ListIndex pointToPos(int where);
int length();
Object getValue(ListIndex where);
}
There is the issue in an implementation of how the two classes will
communicate.
For the array-based list, the ListIndex merely needs to store an
integer for the position.
For the linked list class, the ListIndex would store a pointer to
a linked list node.
This means that the List class needs to be able to set and get
this pointer, but nobody outside should need to know about it.
Some languages like Java and C++ have mechanisms that allow a specific
class to have access to non-public members of another class.
Oher languages like Processing have no such concept.
One general solution is to make the interface for ListIndex
public, but make the implementation a private inner class of the List
implementation.
This approach is used in the following implmentation for the
Array-based list.
// Array-based list implementation
class AList implements List {
private class AListIndex implements ListIndex {
int pos;
AListIndex(int posit) { pos = posit; }
void prev() { if (pos != 0) { pos--; } }
void next() { if (pos < listSize) { pos++; } }
}
private static final int defaultSize = 10; // Default size
private int maxSize; // Maximum size of list
private int listSize; // Current # of list items
private Object listArray[]; // Array holding list elements
// Constructors
// Create a new list object with maximum size "size"
AList(int size) {
maxSize = size;
listSize = 0;
listArray = new Object[size]; // Create listArray
}
// Create a list with the default capacity
AList() { this(defaultSize); } // Just call the other constructor
void clear() // Reinitialize the list
{ listSize = 0; } // Simply reinitialize values
// Insert "it" at current position
void insert(Object it, ListIndex where) {
if (listSize >= maxSize) {
println("List capacity exceeded, nothing inserted");
return;
}
int pos = ((AListIndex)where).pos;
for (int i=listSize; i>pos; i--) { // Shift elements up
listArray[i] = listArray[i-1]; // to make room
}
listArray[pos] = it;
listSize++; // Increment list size
}
// Append "it" to list
void append(Object it) {
if (listSize >= maxSize) {
println("List capacity exceeded, nothing inserted");
return;
}
listArray[listSize++] = it;
}
// Remove and return the current element
Object remove(ListIndex where) {
int pos = ((AListIndex)where).pos;
if ((pos<0) || (pos>=listSize)) { // No current element
return null;
}
Object it = listArray[pos]; // Copy the element
for(int i=pos; i<listSize-1; i++) { // Shift them down
listArray[i] = listArray[i+1];
}
listSize--; // Decrement size
return it;
}
// Return list size
int length() { return listSize; }
// Return a ListIndex to the beginning of the list
ListIndex getStart() {
return new AListIndex(0);
}
// Return a ListIndex past the end of the list
ListIndex getEnd() {
return new AListIndex(listSize);
}
ListIndex pointToPos(int pos) {
return new AListIndex(pos);
}
// Return the current element
Object getValue(ListIndex where) {
int pos = ((AListIndex)where).pos;
if ((pos < 0) || (pos >= listSize)) { // No current element
return null;
}
return listArray[pos];
}
}
