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];
  }
}

OpenDSA Stand-alone Modules

Chapter 0 modules

Alternative List ADT Designs¶