I use linear data structures as the first mental model for order. Arrays, lists, stacks, and queues are simple, but I recommend choosing them based on the operation that must stay cheap.
The simple mental model is this: arrays are good when position is important, linked lists are good when links change more than indexes, stacks are good for reversing recent history, queues are good for fair order, and deques are good when both ends are active.
The main question is not "which data structure is best?" The better question is "where will my code read, insert, and remove most often?"
Complexity cheat sheet
| Structure | Access by index | Search | Traverse | Insert front | Insert end | Insert middle | Delete front | Delete end | Delete middle | Peek |
|---|---|---|---|---|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(1) if space exists | O(n) | O(n) | O(1) | O(n) | O(1) |
| Dynamic array | O(1) | O(n) | O(n) | O(n) | O(1) amortized | O(n) | O(n) | O(1) | O(n) | O(1) |
| Singly linked list | O(n) | O(n) | O(n) | O(1) | O(1) with tail | O(n) | O(1) | O(n) | O(n) | O(1) head |
| Doubly linked list | O(n) | O(n) | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) | O(1) ends |
| Stack | Not the goal | O(n) | O(n) | Not used | Push O(1) | Not used | Not used | Pop O(1) | Not used | Top O(1) |
| Queue | Not the goal | O(n) | O(n) | Not used | Enqueue O(1) | Not used | Dequeue O(1) | Not used | Not used | Front O(1) |
| Deque | Depends on implementation | O(n) | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) | Ends O(1) |
Examples that make them stick
Think of an array as numbered seats in a theater. If you know seat 42, you can walk straight there: O(1). But if you insert a new seat near the front, everyone after it has to shift: O(n).
Think of a linked list as a treasure hunt. Each clue points to the next clue. Adding a clue at the front is easy, but finding the tenth clue means walking through the first nine.
Think of a stack as plates in a cafeteria. You put a plate on top and take from the top. Think of a queue as a support line. First customer in should be first customer served. Think of a deque as a train with doors on both ends.
Support queue and cache example
I use "Support queue and cache example" to keep Linear Data Structures grounded in a real system, because abstract patterns are too easy to agree with and too hard to operate.
A support desk queue is a useful real world memory hook. New tickets enter the back, agents take work from the front, urgent escalations may go to a deque, and the undo button in the ticket editor behaves like a stack.
Queue implementation example
// Stack: undo recent actions, O(1) push and pop.
const undo = [];
undo.push("rename file");
undo.push("delete branch");
const lastAction = undo.pop();
// Queue: process jobs fairly, O(1) enqueue and dequeue
// when implemented with a moving head index.
const jobs = ["email", "invoice", "report"];
let head = 0;
const nextJob = jobs[head++];
// Deque idea: add or remove from either end.
const deque = [];
deque.unshift("urgent"); // front, often O(n) in JS arrays
deque.push("normal"); // back, O(1) amortizedThe snippet maps each structure to behavior: stack for recent history, queue for fair processing, and deque when both ends of the collection matter.
When to use what
The practical rule
My recommendation in "The practical rule" is to draw the data movement before memorizing the complexity table.
If you mostly read by position, start with an array. If you mostly add and remove from one end, use a stack or queue. If both ends are active, use a deque. If you keep changing links inside a sequence and already have the node, a linked list can be useful.
Most real systems choose the simplest structure first and change only when the access pattern proves it is wrong. That is the healthy habit: let the operations pick the structure.