101
0/276
Loading content...
Now that we understand the theoretical foundation of linear data structures—sequential organization, one-to-one relationships, and the distinction between logical and physical order—it's time to meet the four structures that embody these principles most directly.
Arrays, linked lists, stacks, and queues are the foundational linear data structures. Every programmer encounters them, and every computer science curriculum teaches them. But more importantly, they appear everywhere in real software:
This page provides the conceptual foundation for each—the mental model, the key characteristics, and the intuition for when to use each one. Detailed implementations will follow in dedicated chapters.
By the end of this page, you will have a clear mental model for each of the four fundamental linear data structures, understand their distinguishing characteristics, and develop intuition for selecting the right structure for different problem types.
An array is the most fundamental data structure—a fixed-size, ordered collection of elements stored in contiguous memory locations. It is the direct manifestation of computer memory itself: a sequence of slots, each accessible by its position.
The mental model:
Imagine a row of numbered lockers in a hallway. Each locker has a number (its index), and you can walk directly to any locker by its number without checking the others. That's an array.
Key characteristics:
Real-world intuition:
Think of arrays when you think of:
The through-line: position-based access and known, stable collections.
Languages like Python (list), JavaScript (array), and Java (ArrayList) provide dynamic arrays that resize automatically. Under the hood, they allocate extra space and copy to larger arrays when needed—offering array-like random access with flexible sizing, at the cost of occasional O(n) resize operations (amortized O(1) for appends).
A linked list is a sequence of nodes where each node contains data and a reference (pointer) to the next node. Unlike arrays, nodes can be scattered anywhere in memory—they're connected by explicit links rather than physical adjacency.
The mental model:
Imagine a scavenger hunt where each clue leads you to the next location. You can't jump directly to clue #5; you must follow the chain from clue #1. But adding a new clue between existing ones is easy—just update the " next location" hints.
Key characteristics:
Variants:
Real-world intuition:
Think of linked lists when you think of:
The through-line: dynamic modification and sequential processing.
In practice, arrays often outperform linked lists due to cache efficiency—even for operations where linked lists have theoretically better complexity. Modern CPUs are optimized for sequential memory access. Always measure before assuming linked lists are faster.
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle: the last element added is the first one removed. You can only add or remove from one end—the "top" of the stack.
The mental model:
Imagine a stack of dinner plates. You can only add a plate to the top or remove the top plate. The plate at the bottom was placed first but will be removed last. You can't pull a plate from the middle without removing everything above it.
Key characteristics:
| Operation | Description | Time Complexity |
|---|---|---|
| push(item) | Add item to the top of the stack | O(1) |
| pop() | Remove and return the top item | O(1) |
| peek() / top() | Return the top item without removing | O(1) |
| isEmpty() | Check if the stack has no items | O(1) |
| size() | Return the number of items | O(1) |
Real-world intuition:
Think of stacks when you think of:
The through-line: reversing order and nested/recursive structures.
Every programming language uses a stack to manage function calls. When function A calls function B, a stack frame for B is pushed. When B returns, its frame is popped, and control returns to A. Stack overflow errors occur when the call stack exceeds its size limit—typically from deep or infinite recursion.
Implementation note:
Stacks can be implemented using either arrays or linked lists:
Both provide O(1) operations. Array-based is more common due to simplicity and cache efficiency.
A queue is a linear data structure that follows the First In, First Out (FIFO) principle: the first element added is the first one removed. You add at one end (the "back" or "rear") and remove from the other (the "front").
The mental model:
Imagine a line at a coffee shop. New customers join at the back; the person at the front is served first. It's fair—whoever arrived first gets served first. No cutting in line!
Key characteristics:
| Operation | Description | Time Complexity |
|---|---|---|
| enqueue(item) | Add item to the rear of the queue | O(1) |
| dequeue() | Remove and return the front item | O(1) |
| front() / peek() | Return the front item without removing | O(1) |
| isEmpty() | Check if the queue has no items | O(1) |
| size() | Return the number of items | O(1) |
Real-world intuition:
Think of queues when you think of:
The through-line: preserving order and processing in sequence.
Common queue variants include: Double-ended queue (deque) — add/remove from both ends; Priority queue — dequeue by priority, not FIFO order; Circular queue — efficient array-based implementation that wraps around.
Implementation note:
Queues can be implemented using:
Linked list implementation is conceptually cleaner; circular array is often faster in practice.
Now that we've surveyed each structure individually, let's compare them systematically. Understanding their differences helps you choose the right tool for each problem.
Organizational paradigm:
Stacks and queues are restricted interfaces on top of the underlying linear organization. They trade flexibility for clarity—by limiting what you can do, they make certain operations obvious and prevent misuse.
| Property | Array | Linked List | Stack | Queue |
|---|---|---|---|---|
| Access pattern | Any index | Sequential | Top only | Front/Rear |
| Ordering | By position | By links | LIFO | FIFO |
| Random access | O(1) | O(n) | Not applicable | Not applicable |
| Add to end | O(1)* | O(1)** | O(1) push | O(1) enqueue |
| Remove from end | O(1) | O(n)*** | O(1) pop | N/A |
| Add to front | O(n) | O(1) | N/A | N/A |
| Remove from front | O(n) | O(1) | N/A | O(1) dequeue |
| Memory usage | Compact | Overhead per node | Compact/Linked | Compact/Linked |
| Size flexibility | Fixed/Dynamic | Dynamic | Dynamic | Dynamic |
*Amortized O(1) for dynamic arrays **O(1) with tail pointer ***O(1) for doubly-linked lists
Key insight:
Arrays and linked lists are building blocks—they can implement any linear access pattern. Stacks and queues are behavioral abstractions—they define what operations are allowed, not how they're implemented.
In fact:
The stack/queue interface matters more than the underlying storage.
Think of arrays and linked lists as 'raw materials' and stacks/queues as 'finished products.' You can build stacks and queues from arrays or linked lists, just as you can build furniture from wood or metal. The choice of material (implementation) affects performance; the choice of product (interface) affects usage.
With four structures to choose from, how do you decide? Here's a practical decision framework based on your access patterns and operations:
Step 1: Determine your access pattern
Step 2: Identify your primary operations
| If you need... | Consider... |
|---|---|
| Fast access by index | Array |
| Binary search on sorted data | Array (sorted) |
| Frequent insertions at beginning | Linked List |
| Efficient insertions at arbitrary positions | Linked List |
| Undo/redo functionality | Stack |
| Matching/balancing (parens, tags) | Stack |
| Depth-first traversal | Stack |
| Task scheduling (FIFO order) | Queue |
| Breadth-first traversal | Queue |
| Buffer for streaming data | Queue |
| Both FIFO and LIFO capabilities | Deque (double-ended queue) |
Step 3: Consider practical factors
Let's ground our understanding with concrete applications. For each structure, here are domains where it's the natural choice:
Arrays in the Wild:
Linked Lists in the Wild:
Pattern recognition opportunity:
When you encounter these domains in problems or projects, you now have a starting point. See "fairness" or "ordering"? Think queue. See "reversal" or "matching"? Think stack. See "position-based" access? Think array. See "frequent modification"? Think linked list.
This domain-to-structure mapping is the beginning of pattern recognition—a skill that grows with practice and becomes increasingly automatic.
Every time you solve a problem, note which structure you used and why. Over time, you'll build an intuitive library: 'Problems that look like X usually need structure Y.' This library becomes your competitive advantage in both interviews and engineering.
We've surveyed the four foundational linear data structures, building intuition for their characteristics and use cases. Here are the essential insights:
What's next:
This module has established the conceptual foundation for linear data structures. In upcoming chapters, you'll dive deep into each structure with:
The intuition you've built here will make those deeper explorations more meaningful and memorable.
Congratulations! You've completed the module on Linear Data Structures. You understand their definition, how they achieve sequential organization, the one-to-one relationships that define them, and the characteristics of arrays, linked lists, stacks, and queues. This foundation will serve you throughout your DSA journey.