Accessing the 1000th element: array (Python list) vs linked list?
Options
- Both are O(1), since the position is known
- Array: O(1); linked list: O(n), node by node (Correct option)
- Array: O(n); linked list: O(1) with an index
- Both are O(log n), halving the search space
Answer
Array O(1); linked list O(n) because you must walk node by node
Why
An array stores items next to each other in memory, so the position of item k can be calculated directly: O(1).
A linked list stores items in separate nodes, each pointing to the next. To reach item 1000 you must follow 1000 links: O(n).
In exchange, a linked list can insert or remove a node in O(1) once you are at the right place.
Remember
Array = fast access by index. Linked list = fast insert where you are.