Array Lists

What is a List ADT?

A list abstract data type represents a linear sequence of elements with operations to add, remove, and access elements.

What is an index?

An integer that identifies an element's position in a list.

What is the main advantage of array indexing?

Elements can be accessed directly using their index in O(1) time.

Why is accessing an indexed linked-list element slower?

You must traverse the list from node to node to reach the desired index.

What does size() return?

The number of elements stored in the list.

What does isEmpty() return?

A boolean indicating whether the list contains zero elements.

What does get(i) do?

Returns the element at index i.

What does set(i, e) do?

Replaces the element at index i with e and returns the old element.

What does add(i, e) do?

Inserts e at index i and shifts later elements one position right.

What does remove(i) do?

Removes and returns the element at index i, shifting later elements left.

What happens when a list method receives an invalid index?

An IndexOutOfBoundsException may be thrown.

What is an ArrayList implementation?

A list implementation that stores element references in an underlying array.

How does an array list implement get(i)?

It accesses the array directly at A[i].

How does an array list implement set(i, e)?

It replaces the reference stored at A[i] with e.

Why can add(i, e) be expensive?

Elements after index i may need to shift one position right.

Why can remove(i) be expensive?

Elements after index i may need to shift one position left.

What is the space complexity of an array-based list?

O(n), where n is the number of stored elements.

What is the time complexity of get(i)?

O(1), constant time.

What is the time complexity of set(i, e)?

O(1), constant time.

What is the time complexity of add(i, e)?

O(n) in the worst case because elements may need shifting.

What is the time complexity of remove(i)?

O(n) in the worst case because elements may need shifting.

What is a limitation of a fixed-capacity array list?

It cannot store more elements than its allocated capacity.

What happens when a fixed-capacity array is full?

Adding another element may cause an exception.

Why can choosing an array that is too large waste memory?

Unused array positions still occupy allocated memory.

Why can choosing an array that is too small be a problem?

The array may run out of capacity before all elements fit.

What is a dynamic array?

An array-backed list that can grow when its current capacity is full.

How does a dynamic array store its elements?

In an internal array that may have more capacity than the current list size.

What happens when a dynamic array runs out of capacity?

It allocates a larger array and copies the existing element references.

What are the four steps for growing a dynamic array?

Allocate a larger array, copy elements, switch to the new array, and insert the new element.

Why does a dynamic array allocate extra capacity?

To allow future insertions without replacing the array every time.

What is push in the slides?

Adding an element to the end of the dynamic array.

What happens during a dynamic array resize?

A larger array is allocated and the existing element references are copied.

Why can resizing a dynamic array be expensive?

Copying n existing elements takes O(n) time.

What is amortized analysis?

An analysis of the average cost per operation over a sequence of operations.

Why is doubling array capacity efficient?

One expensive resize allows many subsequent insertions without resizing.

What is the amortized time complexity of adding to the end of a dynamic array?

O(1) amortized time.

What is the worst-case time complexity of an individual push during resizing?

O(n), because existing elements must be copied.

Why is doubling capacity better than growing by one slot?

It reduces how frequently expensive resizing and copying are needed.

What is the difference between worst-case and amortized time?

Worst-case considers one operation; amortized time averages costs over a sequence.

Why can StringBuilder be efficient for building long strings?

It uses a growable storage strategy, reducing repeated expensive allocations and copying.

If an array list has 5 elements, what are its valid element indexes?

0, 1, 2, 3, and 4.

If a list has size 5, is add(5, e) valid?

Yes. Insertion is allowed at index size, which appends to the end.

If a list has size 5, is get(5) valid?

No. Valid element indexes are 0 through 4.

If you insert at index 1, which elements shift?

All elements originally at index 1 and later shift one position right.

If you remove the element at index 2, which elements shift?

All elements originally after index 2 shift one position left.

If an array list contains [A, B, C], what does add(1, X) produce?

[A, X, B, C]

If an array list contains [A, B, C], what does remove(1) leave?

[A, C]. The removed element is B.

If an array list contains [A, B, C], what does set(1, X) produce?

[A, X, C]. The old element B is returned.

Why is get(i) faster in an array than in a linked list?

An array calculates the location directly instead of traversing nodes.

A dynamic array has capacity 8 and size 8. What happens when you add another item?

It allocates a larger array, copies the 8 references, then inserts the new item.

Why are not all dynamic-array insertions equally expensive?

Most insertions use free capacity; occasional insertions trigger an expensive resize.

Does O(1) amortized mean every insertion takes constant time?

No. Some insertions take O(n), but the average over many insertions is O(1).

If an array list has 5 elements, what are its valid element indexes?

0, 1, 2, 3, and 4.

If a list has size 5, is add(5, e) valid?

Yes. Insertion is allowed at index size, which appends to the end.

If a list has size 5, is get(5) valid?

No. Valid element indexes are 0 through 4.

If you insert at index 1, which elements shift?

All elements originally at index 1 and later shift one position right.

If you remove the element at index 2, which elements shift?

All elements originally after index 2 shift one position left.

If an array list contains [A, B, C], what does add(1, X) produce?

[A, X, B, C]

If an array list contains [A, B, C], what does remove(1) leave?

[A, C]. The removed element is B.

If an array list contains [A, B, C], what does set(1, X) produce?

[A, X, C]. The old element B is returned.

Why is get(i) faster in an array than in a linked list?

An array calculates the location directly instead of traversing nodes.

A dynamic array has capacity 8 and size 8. What happens when you add another item?

It allocates a larger array, copies the 8 references, then inserts the new item.

Why are not all dynamic-array insertions equally expensive?

Most insertions use free capacity; occasional insertions trigger an expensive resize.

Does O(1) amortized mean every insertion takes constant time?

No. Some insertions take O(n), but the average over many insertions is O(1).