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.
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.
5.3.1.2. Insert Practice Exericse¶
5.3.2. Append and Remove¶
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.
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.
