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 Python, list is a dynamic array of object references; collections.deque supports efficient operations at both ends.

Source

• Open Data Structures: Interfaces