2.2. Array-Based List Implementation¶
2.2.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.
2.2.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)\).
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 List simply
access the current list element or move the current position.
They all require \(\Theta(1)\) time.
