Compare array vs list stack costs
Updated
Array stack: push/pop amortized O(1), peek O(1), extra pointer to the array, growth copies. List stack: push/pop O(1) worst-case, peek O(1), extra pointer per node, no growth copy, worse constants and locality.
What to focus on
Use an array unless you need true worst-case O(1) without amortized pauses, or you already have nodes. Size is O(1) if stored on either.
Worked examples
array push full
a = [4, 1, 9], cap 3, push 8- copy 3 then write
- this push O(n), amortized O(1)
Result: growth hiccup
list push
a = [4, 1, 9] as list, push 8- one node alloc
- two pointer writes
Result: O(1) worst-case
peek both
a = [4, 1, 9]- array a[size-1]
- list head.value
Result: O(1) both
Try it
Write backingCost(kind). kind is "arrayGrow", "listPush", or "peek". Return the cost. Capacity 3 is full before the array growth push. a = [4, 1, 9], cap 3, push 8 → growth hiccup. a = [4, 1, 9] as list, push 8 → O(1) worst-case. a = [4, 1, 9] → O(1) both.
The stack is non-empty. Capacity 3 is full before the array growth push. Values are integers.