4.4. Array-Based List Implementation¶

4.4.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 : public List {
  ListItemType listArray[MAX_SIZE];  //Array holding list elements
  int listSize;   //Current number of list items
  int curr;   //Position of current element

  public:

  //Constructor
  // Create a new list element with maximum size "MAX_SIZE"
  AList() : listSize(0) {
    //Initial the array
    for (int k = 0; k < MAX_SIZE; k++) listArray[k] = 0;
  } //end constructor

  bool isEmpty() const {
    return listSize == 0;
  }

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

  // Insert "it" at current position
  bool insert(const ListItemType& it) {
    if (listSize >= MAX_SIZE) 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 >= MAX_SIZE ) return false;
    listArray[listSize++] = it;
    return true;
  }

  // Remove and return the current element
  ListItemType remove() {
    if( (curr < 0) || (curr >= listSize) )  // No current element
      return 0;
    ListItemType it = listArray[curr];      // Copy the element
    for (int i = curr; i < listSize; 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 to 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
      return 0;
    return listArray[curr];
  }
};

// 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() {
    if ((curr<0) || (curr>=listSize))  // No current element
      return null;
    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() {
    if ((curr < 0) || (curr >= listSize)) // No current element
      return null;
    return listArray[curr];
  }
  
  // Check if the list is empty
  public boolean isEmpty() { return listSize == 0; }
  
  public String toString() {
		StringBuffer out = new StringBuffer((listSize + 1) * 4);

		out.append("< ");
		for (int i = 0; i < curr; i++) {
			out.append(listArray[i]);
			out.append(" ");
		}
		out.append("| ");
		for (int i = curr; i < listSize; i++) {
			out.append(listArray[i]);
			out.append(" ");
		}
		out.append(">");
		return out.toString();
	  }
}

// 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

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

  // Insert "it" at current position
  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
  boolean append(Object it) {
    if (listSize >= maxSize) return false;
    listArray[listSize++] = it;
    return true;
  }

  // Remove and return the current element
  Object remove() {
    if ((curr<0) || (curr>=listSize))  // No current element
      return null;
    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;
  }

  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"
  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
  boolean isAtEnd() { return curr == listSize; }

  // Return the current element
  Object getValue() {
    if ((curr < 0) || (curr >= listSize)) // No current element
      return null;
    return listArray[curr];
  }
}

// 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() {
    if ((curr<0) || (curr>=listSize))  // No current element
      return null;
    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() { 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 E getValue() {
    if ((curr < 0) || (curr >= listSize)) // No current element
      return null;
    return listArray[curr];
  }
  
  public String toString() {
	StringBuffer out = new StringBuffer((listSize + 1) * 4);

	out.append("< ");
	for (int i = 0; i < curr; i++) {
		out.append(listArray[i]);
		out.append(" ");
	}
	out.append("| ");
	for (int i = curr; i < listSize; i++) {
		out.append(listArray[i]);
		out.append(" ");
	}
	out.append(">");
	return out.toString();
  }
  
  //Tell if the list is empty or not
  public boolean isEmpty() {
	  return listSize == 0;
  }
}

1 / 8 Settings

<<<>>>

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

class AList : public List {
ListItemType listArray[MAX_SIZE]; //Array holding list elements
int listSize; //Current number of list items
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

4.4.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
bool insert(const ListItemType& it) {
if (listSize >= MAX_SIZE) 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

4.4.1.2. Insert Practice Exericse¶

4.4.2. Append and Remove¶

1 / 5 Settings

<<<>>>

Inserting at the tail of the list is easy.

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.

curr

listSize

Saving...

Server Error
Resubmit

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

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

TDDI16 Fall 2021

Chapter 4 Linear Structures

4.4. Array-Based List Implementation¶

4.4.1. Array-Based List Implementation¶

4.4.1.1. Insert¶

4.4.1.2. Insert Practice Exericse¶

4.4.2. Append and Remove¶

4.4.2.1. Remove Practice Exericise¶

4.4.3. Array-based List Practice Questions¶