Linear structures

Quick comparison

Structure	Access $i$-th	Add / remove at front	Add / remove at back	Delete a known item	Order
Array	$O(1)$	$O(n)$	$O(1)$ amortized	$O(n)$	By index
Singly linked list	$O(n)$	$O(1)$	$O(1)$ add with tail / $O(n)$ remove	$O(n)$	By links
Doubly linked list	$O(n)$	$O(1)$	$O(1)$	$O(1)$	By links
Circular linked list	$O(n)$	$O(1)$	$O(1)$ add	$O(n)$	Wraps around
Stack	top only	—	$O(1)$ push / pop	—	LIFO
Queue	front only	$O(1)$ dequeue	$O(1)$ enqueue	—	FIFO
Deque	$O(1)$ (array)	$O(1)$	$O(1)$	—	Both ends
Priority queue	min only	$O(\log n)$ extract-min	$O(\log n)$ insert	—	By priority

Which one to pick?

flowchart TD
  A{"Which item do you remove next?"} -->|"the newest"| S["Stack"]
  A -->|"the oldest"| Q["Queue"]
  A -->|"newest or oldest, both ends"| D["Deque"]
  A -->|"the most urgent"| P["Priority queue"]
  A -->|"any item"| B{"Need access by index?"}
  B -->|yes| AR["Array"]
  B -->|no| C{"Delete nodes you already hold, or walk backwards?"}
  C -->|yes| DL["Doubly linked list"]
  C -->|no| E{"Cycle through items forever?"}
  E -->|yes| CL["Circular linked list"]
  E -->|no| SL["Singly linked list"]

Key points

Arrays give $O(1)$ access because the address of item $i$ is computed directly.
Linked lists give $O(1)$ relinking because inserting next to a known node changes only pointers, not positions.
Stacks, queues and deques are $O(1)$ because they only ever touch the ends.
A priority queue costs $O(\log n)$ because a heap keeps only partial order, along one root-to-leaf path.
Pick by your most frequent operation because every structure makes some operations cheap by making others expensive.

External resources

VisuAlgo: Linked list, stack, queue, deque: animate every structure on this hub.
GeeksforGeeks: Data structures: tutorials for each structure with code.
MIT OCW 6.006: lectures on sequences, sets and heaps.

Videos

YouTube search: arrays vs linked lists: the core trade-off of this hub.

Mixed review

Quick comparison

The eight structures

Array

Singly linked list

Doubly linked list

Circular linked list

Stack

Queue

Deque

Priority queue

Which one to pick?

Key points

External resources

Review schedule

Feynman prompt

My notes