Quiz Entry - updated: 2026.09.29
Compare the running times of an array-list and a linked list for the common list operations.
Array-lists win at indexed access (get/set in $O(1)$); linked lists win at inserting and removing at the ends or next to a node you already hold ($O(1)$). Anything that has to find a position by index is $O(n)$ on both.
| Operation | Array-list | Linked list |
|---|---|---|
get(index) |
$O(1)$ | $O(n)$ |
set(index, data) |
$O(1)$ | $O(n)$ |
add(index, data) |
$O(n)$ | $O(n)$ |
addFirst(data) |
$O(n)$ | $O(1)$ |
addAfter(u, v) |
— | $O(1)$ |
addLast(data) |
$O(n)$ | $O(1)$ |
remove(index) |
$O(n)$ | $O(n)$ |
The reasons come from how each one stores its data:
- Array-list, contiguous memory. Element $i$ sits at a computable address, so indexed access is one step. But inserting at the front (or anywhere) shifts every later element one slot, and a full array must be copied, hence the $O(n)$ entries.
- Linked list, chained nodes. Changing the structure next to a known node is a few reference updates. But reaching position $i$ means following $i$ links from the head.
add(index)andremove(index)are $O(n)$ on both, for different reasons: the array-list pays for shifting, the linked list pays for walking to the index.
Gotcha: addLast on an array-list is listed as $O(n)$ because a single call may trigger a resize. Averaged over many calls it is amortised $O(1)$, which is why appending to an array-list is fast in practice.
Tip: pick by the operation you do most. Lots of random reads call for an array-list; lots of inserting and removing at the ends or at a cursor call for a linked list.
Go deeper:
Python TimeComplexity — the measured costs of listandcollections.deque, operation by operation.