Data Structures and Algorithms
Compared with an array, which is a correct description of a linked list (a list in which each element holds a pointer to the next element)?
- AIf the element just before the insertion point is known, a new element can be inserted just by changing pointers without moving other elements, but reading the i-th element requires following the list from the front
- BThe position of the i-th element can be computed, so any element can be read in constant time, O(1)
- CThe elements are stored contiguously in memory, so caches and prefetching work well when reading them in order
Show answer and explanation
Answer: A. If the element just before the insertion point is known, a new element can be inserted just by changing pointers without moving other elements, but reading the i-th element requires following the list from the front
In a linked list, once the position is known, insertion and deletion only require rewriting the neighboring pointers, which takes O(1). Reading the i-th element, however, requires following i pointers from the front, which takes O(n). An array can compute the address of the i-th element from its start address and element size, so it reads any element in O(1), but inserting in the middle takes O(n) to shift the following elements. Also, because array elements are contiguous, caches and prefetching work well, whereas the nodes of a linked list tend to be scattered in memory, so even an O(n) traversal can be much slower.
- A. Correct. Insertion and deletion are just pointer changes, but reading by position means walking from the front.
- B. Computing the address and reading in O(1) is a property of arrays.
- C. Contiguous storage that suits caches is a property of arrays. Linked list nodes tend to be scattered.