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

1 / 8 Settings

<<<>>>

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

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.

1. 130
2. 121
3. 202
4. 83
5. 34
6. 5
7. 6
8. 7

Saving...
Server Error
Resubmit

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

1. 130
2. 121
3. 202
4. 83
5. 34
6. 5
7. 6
8. 7

Insert 23

1. 8

maxSize

1. 5

listSize

1. 0

curr

Saving...
Server Error
Resubmit

9.3.2. Insert Practice Exericse¶

9.3.3. Append and Remove¶

1 / 5 Settings

<<<>>>

Inserting at the tail of the list is easy.

Append 23

1. 130
2. 121
3. 202
4. 83
5. 34
6. 5
7. 6
8. 7

maxSize

1. 8

listSize

1. 5

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.

1. 130
2. 121
3. 202
4. 83
5. 34
6. 5
7. 6
8. 7

it

curr

listSize

1. 1

1. 5

Saving...
Server Error
Resubmit

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

9.3.4. Array-based List Practice Questions¶