ArrayLists/ArrayStacks

Question 1

What is the runtime of the add(i,x) method for an ArrayList (a.k.a. ArrayStack)?

Answer 1

O(n-i) amortized time.

Question 2

What is the runtime of the get(i) method for an ArrayList (a.k.a. ArrayStack)?

Answer 2

O(1) time.

Question 3

What is the runtime of the set(i,x) method for an ArrayList (a.k.a. ArrayStack)?

Answer 3

O(1) time.

Question 4

What is the runtime of the remove(i) method for an ArrayList (a.k.a. ArrayStack)?

Answer 4

O(n-i) amortized time.

Question 5

What make the runtimes of the ArrayList/Arraystack add/remove methods amortized?

Answer 5

The copying in the resize() method.

(Arrays are of fixed length; therefore, any array-based List implementation must occasionally resize this array as we need more space. When we resize, we create a new array and copy all n elements from the original array into the new array, and this copying takes O(n) time that is amortized over all adds/removes that happened since the last add/remove.)

Question 6

Given an ArrayList/ArrayStack with n elements, what index i makes the add(i,x) method achieve its worst-case runtime?

Answer 6

index i=0, i.e. adding to the front.

(The runtime for add(i,x) is O(n-i) amortized time; therefore, index i=0 would achieve the worst runtime of O(n). In particular, adding to the front of the array requires an O(n) shift of all the n elements to the right.)

Question 7

How much extra space is required for an ArrayList/ArrayStack to store n elements?

Answer 7

O(n).

(The backing array is sometimes twice as big as is necessary (when resizing on an add we resize the backing array to length 2n), and sometimes three times as big as is necessary (when resizing on a remove it’s when the array is only 1/3 full.) In either case, we are using O(n) extra space to store n elements.)

Question 8

Given an ArrayList/ArrayStack with n elements, what index i makes the add(i,x) method achieve its best-case runtime?

Answer 8

index i=n-1, i.e. adding to the end.

(The runtime for add(i,x) is O(n-i) amortized time; therefore, index i=(n-1) would achieve the best runtime of O(1). In particular, adding to the end of the array requires no shift and is therefore quite quick — unless there is a resize…)

Question 9

Pros of ArrayLists/ArrayStacks

Answer 9

O(1) get(i)/set(i,x)
O(1) add(n-1,x)/remove(n-1) i.e. from the end (amortized)
(Therefore O(1) implementation of a Stack)
Straight-forward implementation

Question 10

Cons of ArrayLists/ArrayStacks

Answer 10

O(n) add(0,x)/remove(0) i.e. from the front
It’s also O(n) for all positions i in the first half of the array.
O(n) extra space.

Question 11

What is the backing storage of an ArrayList/ArrayStack?

Answer 11

an array to store the elements

an integer to store the size