Comparisons and explanations · Intermediate

Arrays versus linked lists

Compare arrays and linked lists by separating lookup from updates, then consider locality, allocation, stable handles and workload requirements.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Contiguous positions versus linked positions
  2. Indexing is different from searching by value
  3. Count the work needed to reach an insertion point
  4. Account for locality and representation overhead
  5. Choose from lifetime and operation mix
  6. Ask Logeia about this articleCheck your understanding

Contiguous positions versus linked positions

An array of fixed-size elements computes a location from a base and an index. A linked list follows nodes containing a value and links. Array continuity supports indexing and sequential access, while a list makes local relinking convenient once the relevant position is known. If array elements are references, their target objects are not necessarily contiguous. Lists also differ: singly linked, doubly linked and tail-tracked representations support different operations. Specify the representation before relying on a generic comparison table. The useful question is which locations the caller already knows and what access or update must be performed, rather than which structure has a better-sounding asymptotic label.

OperationArraySingly linked list
Known-index accessUsually O(1)O(n) worst case
Order-preserving local insertionMay shift following items: O(n)O(1) relinking with required references
Unknown-value lookupO(n) worst case if unsortedO(n) worst case

Indexing is different from searching by value

Reading an array at a known index is O(1) in the usual RAM model. Finding index i in a singly linked list requires following links from the start and can take O(n). However, looking for an unknown value in an unsorted array also has linear worst-case cost. Saying that array search is constant-time conflates indexing with value lookup. Reading index 500000 and asking whether value 500000 occurs are different tasks, even if the same number appears in their descriptions. If key-based lookup is central, sorting, indexing or a hash table may be a more relevant design change than exchanging an array for a list.

Count the work needed to reach an insertion point

To insert 25 after 20 in [10,20,30,40] while preserving order, an array moves 30 and 40. If a list node holding 20 is already available, insertion can update the links from 20 through the new node to 30. Searching for 20 first adds traversal work, however. Deleting from a singly linked list can also require the predecessor. The constant-time statement concerns a known local link change, not necessarily allocation, lookup and deallocation in the complete interface. Align those operation boundaries when comparing structures. Otherwise the list is credited with a known location while the array is charged for finding and moving data, producing a result unrelated to the caller’s real requirements.

Account for locality and representation overhead

Sequential array traversal often accesses nearby addresses, which can help caching and prefetching. Separately allocated list nodes add link storage, allocator overhead and dependencies on reading the next address before proceeding. These are tendencies, not an unconditional speed theorem: nodes can be pooled, while moving large array elements can be expensive. Two O(n) traversals can therefore differ considerably on a machine. Align item count, element size, allocation strategy, access order and cache state when measuring. The result should explain a particular representation and workload. It should not be generalized into a claim that lists always lose or that removing element movement automatically makes a structure faster.

Choose from lifetime and operation mix

Growing a dynamic array can relocate storage and invalidate references or iterators, according to the library contract. A list also invalidates access to a deleted node, and concurrent modification needs synchronization. Check how long references may be retained for either representation. Arrays are natural candidates for indexing and traversal; lists can suit frequent relinking around known nodes. Other structures, such as deques or segmented arrays, occupy useful middle ground. Write down the actual mix of searches, insertions, removals and scans, along with lifetime requirements. That workload description supports a more reliable decision than selecting from the asymptotic cost of one carefully isolated operation.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 9

Choose a learning path