10.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.

public interface ListIndex {
  public void prev();
  public void next();
}

public interface List {
  public void clear();
  public void insert(Object it, ListIndex where);
  public void append(Object it);
  public Object remove(ListIndex where);
  public ListIndex getStart();
  public ListIndex getEnd();
  public ListIndex pointToPos(int where);
  public int length();
  public 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; }
    public void prev() { if (pos != 0) { pos--; } }
    public 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

  public void clear()                     // Reinitialize the list
    { listSize = 0; }              // Simply reinitialize values

  // Insert "it" at current position
  public void insert(Object it, ListIndex where) {
    if (listSize >= maxSize) {
      System.out.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
  public void append(Object it) {
    if (listSize >= maxSize) {
      System.out.println("List capacity exceeded, nothing inserted");
      return;
    }
    listArray[listSize++] = it;
  }

  // Remove and return the current element
  public 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
  public int length() { return listSize; }

  // Return a ListIndex to the beginning of the list
  public ListIndex getStart() {
    return new AListIndex(0);
  }
  
  // Return a ListIndex past the end of the list
  public ListIndex getEnd() {
    return new AListIndex(listSize);
  }
  
  public ListIndex pointToPos(int pos) {
    return new AListIndex(pos);
  }

  // Return the current element
  public Object getValue(ListIndex where) {
    int pos = ((AListIndex)where).pos;
    if ((pos < 0) || (pos >= listSize)) { // No current element
      return null;
    }
    return listArray[pos];
  }
}

OpenDSA Complete Catalog

Chapter 10 Design

10.2. Alternative List ADT Designs¶