Close
Register
Close Window

Data Structures & Algorithms

Chapter 3 Linked List and Stack

Show Source |    | About   «  3.2. The List ADT   ::   Contents   ::   3.4. Linked Lists  »

3.3. Array-Based List Implementation

3.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;
  }
}

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

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

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

3.3.1.2. Insert Practice Exericse

3.3.2. Append and Remove

Settings

Proficient Saving... Error 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.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

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

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

3.3.3. Array-based List Practice Questions

   «  3.2. The List ADT   ::   Contents   ::   3.4. Linked Lists  »

Close Window