Why use a linked list if arrays support fast random access?

Linked lists allow insertion or deletion in constant time given a reference to a node, without shifting other elements, which arrays cannot do in the middle. They are useful when the sequence changes frequently and positional random access is not needed.

Why are array appends considered constant time if resizing copies everything?

Resizing happens rarely because capacity typically doubles, so the total copying work over n appends is proportional to n. Spread across all appends, this gives an amortized constant cost per append even though individual resizes are O(n).

Arrays and Linked Lists

Arrays and linked lists are the two basic ways to store an ordered sequence of elements: arrays place them in contiguous memory for constant-time indexed access, while linked lists chain them through pointers for cheap insertion and deletion.

Trova un argomento con PaperMindIn arrivoFind papers & topics

Tools & resources

Scarica le diapositive

Learn & explore

VideoIn arrivo

Definition

An array stores elements in contiguous memory locations indexed by position, allowing constant-time random access; a linked list stores elements in separate nodes each holding a reference to the next (and possibly previous) node, allowing constant-time insertion or removal given a node reference.

Scope

This topic covers linear, sequence-based structures and the abstract data types built on them — static and dynamic arrays, singly and doubly linked lists, and the stack and queue ADTs. It contrasts their access, insertion and deletion costs, covers dynamic-array resizing and its amortized analysis, and explains memory-layout consequences such as cache locality. It excludes associative and hierarchical structures covered under hash tables and search trees.

Core questions

When does contiguous (array) storage outperform pointer-linked (list) storage?
How does a dynamic array achieve amortized constant-time append despite occasional resizing?
What are the cost trade-offs of arrays versus linked lists for insertion, deletion and access?
How are stacks and queues implemented on top of these structures?
How does memory layout affect real-world performance through cache behavior?

Key concepts

contiguous memory
indexed access
dynamic array resizing
singly and doubly linked lists
stacks (LIFO)
queues (FIFO)
amortized cost
cache locality

Key theories

Random access versus sequential linkage: Arrays support O(1) indexed access but O(n) insertion or deletion in the middle, whereas linked lists support O(1) splicing given a node but O(n) access by position; the right choice depends on the operation mix.
Amortized growth of dynamic arrays: A dynamic array that doubles its capacity when full performs occasional O(n) copies but amortizes to O(1) per append over any sequence of operations, by the aggregate or potential method.

Clinical relevance

Arrays and lists are the substrate of nearly every program: dynamic arrays implement the default list/vector types in most languages, queues underlie scheduling and breadth-first search, stacks underlie function-call management and expression evaluation, and the array-versus-list trade-off is a routine practical design decision affecting performance.

History

Arrays are among the earliest data structures, present in the first programming languages, and linked lists were introduced for symbolic and list processing (notably in Newell, Shaw and Simon's IPL and later Lisp) in the late 1950s. Knuth's systematic treatment in The Art of Computer Programming established their canonical analysis.

Key figures

Donald Knuth
Robert Sedgewick

Seminal works

knuth1997vol1
cormen2009

Frequently asked questions

Why use a linked list if arrays support fast random access?: Linked lists allow insertion or deletion in constant time given a reference to a node, without shifting other elements, which arrays cannot do in the middle. They are useful when the sequence changes frequently and positional random access is not needed.
Why are array appends considered constant time if resizing copies everything?: Resizing happens rarely because capacity typically doubles, so the total copying work over n appends is proportional to n. Spread across all appends, this gives an amortized constant cost per append even though individual resizes are O(n).