Source: CS61B Textbook — 8. ArrayList
get(i)DLList (doubly linked list) only keeps references to the first and last nodes. To reach an arbitrary index i, you must walk node-by-node from one end.
getLast, which is O(1) (constant time, regardless of list size)Analogy: a linked list is like a chain of beads held only at both ends — to find bead #417 you have to slide along the chain counting as you go.
Arrays, by contrast, support O(1) indexed access (direct address calculation from base pointer + offset), which motivates building a list on top of an array instead.
Use an array items plus a counter size tracking how many slots are in use.
Core invariants (the foundation everything else relies on):
| Invariant | Meaning |
|---|---|
Next insert position = size |
New elements go at items[size] |
Element count = size |
size is the list length |
Last element position = size - 1 |
Access last item via items[size-1] |
Every public method (addLast, get, removeLast) is just logic that mutates size / items / items[i] while preserving these invariants.
Arrays have a fixed length. Once size == items.length, you can't just append — Java has no in-place "grow" operation. The only fix: allocate a new, bigger array and copy everything over.
int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
a[size] = 11;
items = a;
size = size + 1;
This process is called "resizing" — a bit of a misnomer, since the old array doesn't actually change size; a brand-new array is created instead.
(native/additive resizing means every time you want to add one more element and need to resize the whole list, you make a copy of the original list and insert them together with the new element.)
If each resize only adds a small fixed amount (e.g. +1), then: