Linear Data Structures

Linear structures organize elements in a sequence, but their representations and permitted operations differ.

Comparison

Structure	Indexed access	Insert/remove at end	Insert/remove at known interior position	Main trade-off
Dynamic array	$O(1)$	amortized $O(1)$	$O(n)$ shifts	locality and random access
Singly linked list	$O(n)$	$O(1)$ with tail for insert; tail removal $O(n)$	$O(1)$ after predecessor is known	indirection and node overhead
Doubly linked list	$O(n)$	$O(1)$ with endpoints	$O(1)$ after node is known	extra link per node
Stack	not part of contract	push/pop at top	not allowed by interface	LIFO discipline
Queue	not part of contract	enqueue/dequeue at opposite ends	not allowed by interface	FIFO discipline

Finding an interior node or position is separate from modifying it. Saying “linked-list insertion is $O(1)$” silently assumes the relevant node or predecessor is already available.

Selection rules

• Prefer a dynamic array for general-purpose sequences and iteration-heavy work.
• Prefer linked nodes when stable node identity and local splicing dominate.
• Expose a stack or queue when restricted access communicates an algorithmic invariant better than a general list.
• Use a circular buffer for a bounded queue with predictable storage.

In CPython, list uses a dynamic array of object references; this storage layout is implementation-specific. collections.deque supports efficient operations at both ends.

Choose by the next operation

For retrieving item 100 directly, follow arrays. For splicing next to a node already held by an algorithm, follow linked lists; a numeric position alone does not provide that node. For matching the latest unfinished delimiter, use a stack. For processing arrivals in order, use a queue.

Here $n$ is the number of stored elements and moving a slot or following a link has constant cost. Amortized cost bounds a whole sequence of operations, including occasional resizes; it is not an average over random inputs. The stack and queue rows describe interfaces, so their implementation costs must be read separately. These comparisons concern in-memory sequential containers, not concurrent message delivery or on-disk indexing.

Source

• Open Data Structures: Interfaces

My reading · Opened notes are remembered in this browser.