5.3. Array-Based List Implementation¶

5.3.1. Array-Based List Implementation¶

Here is an implementation for the array-based list, named AList. AList inherits from the List ADT,and so must implement all of the member functions of List.

// Array-based list implementation
class AList implements List {
  private Object listArray[];             // Array holding list elements
  private static final int DEFAULT_SIZE = 10; // Default size
  private int maxSize;                    // Maximum size of list
  private int listSize;                   // Current # of list items
  private int curr;                       // Position of current element

  // Constructors
  // Create a new list object with maximum size "size"
  AList(int size) {
    maxSize = size;
    listSize = curr = 0;
    listArray = new Object[size];         // Create listArray
  }
  // Create a list with the default capacity
  AList() { this(DEFAULT_SIZE); }          // Just call the other constructor

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

  // Insert "it" at current position
  public boolean insert(Object it) {
    if (listSize >= maxSize) return false;
    for (int i=listSize; i>curr; i--)  // Shift elements up
      listArray[i] = listArray[i-1];   //   to make room
    listArray[curr] = it;
    listSize++;                        // Increment list size
    return true;
  }

  // Append "it" to list
  public boolean append(Object it) {
    if (listSize >= maxSize) return false;
    listArray[listSize++] = it;
    return true;
  }

  // Remove and return the current element
  public Object remove() throws NoSuchElementException {
    if ((curr<0) || (curr>=listSize))  // No current element
      throw new NoSuchElementException("remove() in AList has current of " + curr + " and size of "
        + listSize + " that is not a a valid element");
    Object it = listArray[curr];       // Copy the element
    for(int i=curr; i<listSize-1; i++) // Shift them down
      listArray[i] = listArray[i+1];
    listSize--;                        // Decrement size
    return it;
  }

  public void moveToStart() { curr = 0; }       // Set to front
  public void moveToEnd() { curr = listSize; }  // Set at end
  public void prev() { if (curr != 0) curr--; } // Move left
  public void next() { if (curr < listSize) curr++; } // Move right
  public int length() { return listSize; }      // Return list size
  public int currPos() { return curr; }         // Return current position

  // Set current list position to "pos"
  public boolean moveToPos(int pos) {
    if ((pos < 0) || (pos > listSize)) return false;
    curr = pos;
    return true;
  }

  // Return true if current position is at end of the list
  public boolean isAtEnd() { return curr == listSize; }

  // Return the current element
  public Object getValue() throws NoSuchElementException {
    if ((curr < 0) || (curr >= listSize)) // No current element
      throw new NoSuchElementException("getvalue() in AList has current of " + curr + " and size of "
        + listSize + " that is not a a valid element");
    return listArray[curr];
  }
  
  // Check if the list is empty
  public boolean isEmpty() { return listSize == 0; }
}

// Array-based list implementation
class AList<E> implements List<E> {
  private E listArray[];                  // Array holding list elements
  private static final int DEFAULT_SIZE = 10; // Default size
  private int maxSize;                    // Maximum size of list
  private int listSize;                   // Current # of list items
  private int curr;                       // Position of current element

  // Constructors
  // Create a new list object with maximum size "size"
  @SuppressWarnings("unchecked") // Generic array allocation
  AList(int size) {
    maxSize = size;
    listSize = curr = 0;
    listArray = (E[])new Object[size];         // Create listArray
  }
  // Create a list with the default capacity
  AList() {
    this(DEFAULT_SIZE);                   // Just call the other constructor
  }

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

  // Insert "it" at current position
  public boolean insert(E it) {
    if (listSize >= maxSize) {
      return false;
    }
    for (int i=listSize; i>curr; i--) {  // Shift elements up
      listArray[i] = listArray[i-1];   //   to make room
    }
    listArray[curr] = it;
    listSize++;                        // Increment list size
    return true;
  }

  // Append "it" to list
  public boolean append(E it) {
    if (listSize >= maxSize) {
      return false;
    }
    listArray[listSize++] = it;
    return true;
  }

  // Remove and return the current element
  public E remove() throws NoSuchElementException {
    if ((curr<0) || (curr>=listSize)) {  // No current element
      throw new NoSuchElementException("remove() in AList has current of " + curr + " and size of "
        + listSize + " that is not a a valid element");
    }
    E it = listArray[curr];            // Copy the element
    for(int i=curr; i<listSize-1; i++) {// Shift them down
      listArray[i] = listArray[i+1];
    }
    listSize--;                        // Decrement size
    return it;
  }

  public void moveToStart() {      // Set to front
    curr = 0; 
  }  
  public void moveToEnd() {  // Set at end
    curr = listSize; 
  } 
  public void prev() {  // Move left
    if (curr != 0) {
      curr--; 
    }
  }
  public void next() {  // Move right
    if (curr < listSize) {
      curr++; 
    }
  }
  public int length() {       // Return list size
    return listSize; 
  }
  public int currPos() {          // Return current position
    return curr; 
  }

  // Set current list position to "pos"
  public boolean moveToPos(int pos) {
    if ((pos < 0) || (pos > listSize)) {
      return false;
    }
    curr = pos;
    return true;
  }

  // Return true if current position is at end of the list
  public boolean isAtEnd() { 
    return curr == listSize; 
  }

  // Return the current element
  public E getValue() throws NoSuchElementException {
    if ((curr < 0) || (curr >= listSize)) {// No current element
      throw new NoSuchElementException("getvalue() in AList has current of " + curr + " and size of "
        + listSize + " that is not a a valid element");
    }
  return listArray[curr];
  }
 
  //Tell if the list is empty or not
  public boolean isEmpty() {
    return listSize == 0;
  }
}

// Array-based list implementation
class AList : public List {
  ListItemType* listArray;            // Array holding list elements
  static const int DEFAULT_SIZE = 10; // Default size
  int maxSize;                        // Maximum size of list
  int listSize;                       // Current # of list items
  int curr;                           // Position of current element

public:
  // Constructors
  // Create a new list object with maximum size "size"
  AList(int size = DEFAULT_SIZE) : listSize(0), curr(0) {
    maxSize = size;
    listArray = new ListItemType[size];         // Create listArray
  }
  
  ~AList() { delete [] listArray; }      // destructor to remove array

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

  // Insert "it" at current position
  bool insert(const ListItemType& it) {
    if (listSize >= maxSize) return false;
    for (int i = listSize; i > curr; i--)  // Shift elements up
      listArray[i] = listArray[i-1];       // to make room
    listArray[curr] = it;
    listSize++;                            // Increment list size
    return true;
  }

  // Append "it" to list
  bool append(const ListItemType& it) {
    if (listSize >= maxSize) return false;
    listArray[listSize++] = it;
    return true;
  }

  // Remove and return the current element
  ListItemType remove() {
    if ((curr < 0) || (curr >= listSize)) // No current element
      throw std::out_of_range("remove() in AList has current of " + to_string(curr) + " and size of "
        + to_string(listSize) + " that is not a a valid element");
    ListItemType it = listArray[curr];     // Copy the element
    for(int i = curr; i < listSize-1; i++) // Shift them down
      listArray[i] = listArray[i+1];
    listSize--;                            // Decrement size
    return it;
  }

  void moveToStart() { curr = 0; }       // Set to front
  void moveToEnd() { curr = listSize; }  // Set at end
  void prev() { if (curr != 0) curr--; } // Move left
  void next() { if (curr < listSize) curr++; } // Move right
  int length() { return listSize; }      // Return list size
  int currPos() { return curr; }         // Return current position

  // Set current list position to "pos"
  bool moveToPos(int pos) {
    if ((pos < 0) || (pos > listSize)) return false;
    curr = pos;
    return true;
  }

  // Return true if current position is at end of the list
  bool isAtEnd() { return curr == listSize; }

  // Return the current element
  ListItemType getValue() {
    if ((curr < 0) || (curr >= listSize)) // No current element
      throw std::out_of_range("getvalue() in AList has current of " + to_string(curr) +  + " and size of "
        + to_string(listSize) + " that is not a a valid element");
    return listArray[curr];
  }
  
  // Check if the list is empty
  bool isEmpty() { return listSize == 0; }
};

1 / 8 Settings

<<<>>>

Let's take a look at the private data members for class AList.

class AList implements List {
private Object listArray[]; // Array holding list elements
private static final int DEFAULT_SIZE = 10; // Default size
private int maxSize; // Maximum size of list
private int listSize; // Current # of list items
private int curr; // Position of current element

Saving...

Server Error
Resubmit

1 / 5 Settings

<<<>>>

Class AList stores the list elements in the first listSize contiguous array positions. In this example, listSize is 5.

Saving...

Server Error
Resubmit

5.3.1.1. Insert¶

Because the array-based list implementation is defined to store list elements in contiguous cells of the array, the insert, append, and remove methods must maintain this property.

1 / 6 Settings

<<<>>>

Inserting an element at the head of an array-based list requires shifting all existing elements in the array by one position toward the tail.

// Insert "it" at current position
public boolean insert(Object it) {
if (listSize >= maxSize) return false;
for (int i=listSize; i>curr; i--) // Shift elements up
listArray[i] = listArray[i-1]; // to make room
listArray[curr] = it;
listSize++; // Increment list size
return true;
}

Saving...

Server Error
Resubmit

5.3.1.2. Insert Practice Exericse¶

5.3.2. Append and Remove¶

1 / 5 Settings

<<<>>>

Inserting at the tail of the list is easy.

// Append "it" to list
public boolean append(Object it) {
if (listSize >= maxSize) return false;
listArray[listSize++] = it;
return true;
}

maxSize

listSize

Saving...

Server Error
Resubmit

Removing an element from the head of the list is similar to insert in that all remaining elements must shift toward the head by one position to fill in the gap. If we want to remove the element at position $i$ , then $n - i - 1$ elements must shift toward the head, as shown in the following slideshow.

1 / 6 Settings

<<<>>>

Here is a list containing five elements. We will remove the value 12 in position 1 of the array, which is the current position.

// Remove and return the current element
public Object remove() throws NoSuchElementException {
if ((curr<0) || (curr>=listSize)) // No current element
throw new NoSuchElementException("remove() in AList has current of " + curr + " and size of "
+ listSize + " that is not a a valid element");
Object it = listArray[curr]; // Copy the element
for(int i=curr; i<listSize-1; i++) // Shift them down
listArray[i] = listArray[i+1];
listSize--; // Decrement size
return it;
}

curr

listSize

Saving...

Server Error
Resubmit

In the average case, insertion or removal each requires moving half of the elements, which is $\Theta(n)$ .

5.3.2.1. Remove Practice Exericise¶

Aside from insert and remove, the only other operations that might require more than constant time are the constructor and clear. The other methods for Class AList simply access the current list element or move the current position. They all require $\Theta(1)$ time.

CS3 Data Structures & Algorithms

Chapter 5 Linear Structures

5.3. Array-Based List Implementation¶

5.3.1. Array-Based List Implementation¶

5.3.1.1. Insert¶

5.3.1.2. Insert Practice Exericse¶

5.3.2. Append and Remove¶

5.3.2.1. Remove Practice Exericise¶

5.3.3. Array-based List Practice Questions¶