Practice question · Multiple choice
Inserting at the front of an array is O(n) and at the front of a linked list is O(1). Why does that reverse the usual verdict between the two structures?
Hints
- Ask what has to be true for
arr[i]to be computable from i alone. - The same property that makes one operation fast makes the other slow. Name it.
Show the answer
B. Because contiguity, which makes indexing instant, forces every element to shift
Why
Contiguity is a single design choice paying off in one direction and charging in the other: computable addresses require everything in order, so a front insert moves everything. Neither structure dominates, which is why the choice is made from the workload rather than from a table.
Practise Arrays, Lists, and Memory Layout
The app has 7 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.