The simplest ways to sort data — rows, stacks, and queues.
Fundamentals 14 min Beginner May 3, 2026
You have learned to measure algorithm speed with Big-O. Now the question becomes: where do the data actually live? The answer — contiguous memory blocks, scattered pointer chains, or restricted-access stacks and queues — determines which operations are fast and which are slow.
These four linear structures are the foundation of every data-intensive program, from spreadsheets to neural networks. This article makes their trade-offs tangible.
Arrays — Contiguous Memory with Index Access
Array
AnalogyDefinition
Imagine an egg carton with 12 numbered slots (0 to 11). You grab slot 7 directly without checking slots 0 through 6 — that is O(1) access. To insert an egg at slot 3 when all slots are full, you must shift eggs 3 through 11 one position to the right — that is O(n). If you need a 13th egg, you need a bigger carton and must move everything — analogous to array resizing.
Example
In a real carton you could squeeze an egg between slots; in memory, elements must be contiguous with no gaps. Also, the carton does not model the dynamic resizing strategy (geometric growth).
Analogy:
Imagine an egg carton with 12 numbered slots (0 to 11). You grab slot 7 directly without checking slots 0 through 6 — that is O(1) access. To insert an egg at slot 3 when all slots are full, you must shift eggs 3 through 11 one position to the right — that is O(n). If you need a 13th egg, you need a bigger carton and must move everything — analogous to array resizing.
Example
In a real carton you could squeeze an egg between slots; in memory, elements must be contiguous with no gaps. Also, the carton does not model the dynamic resizing strategy (geometric growth).
Definition:
An array stores elements in a contiguous memory block where each element has the same size. The computer calculates the address of element i as base_address + i × element_size, making index access O(1). Inserting in the middle requires shifting all subsequent elements → O(n). Dynamic arrays (Python's list, Java's ArrayList) handle growth by over-allocating and doubling capacity, making append amortized O(1).
Python's list is internally a dynamic array with O(1) index access — the name is misleading. A true linked list has no index arithmetic and requires O(n) traversal to reach element k. To accommodate differently sized elements (like text and numbers) in the same list, Python internally stores only equal-sized pointers to the actual data.
Deep Dive: Dynamic Arrays
When a dynamic array is full, it allocates a new block with double the capacity and copies all elements. This resize costs O(n), but happens rarely enough that the amortized cost per append stays at O(1). Python's list uses exactly this strategy.
# Capacity doubling (simplified)
Capacity: 4 → full → new capacity: 8
→ full → new capacity: 16
# 1000 append operations:
# ~10 resizes, rest writes directly
# → amortized O(1) per append()
Linked Lists — Scattered Nodes with Pointers
Linked List
AnalogyDefinition
Imagine a scavenger hunt. Each clue card tells you where the next card is hidden. To find card 5, you must start at card 1 and follow each clue in sequence — O(n). To insert a new card between cards 2 and 3, you just rewrite the directions on card 2 — no other cards need to move (O(1) if you already hold card 2).
Example
In a real scavenger hunt, travel time between locations varies; in memory, following a pointer takes roughly constant time. The analogy also does not capture the extra memory cost of storing a pointer per node (overhead).
Analogy:
Imagine a scavenger hunt. Each clue card tells you where the next card is hidden. To find card 5, you must start at card 1 and follow each clue in sequence — O(n). To insert a new card between cards 2 and 3, you just rewrite the directions on card 2 — no other cards need to move (O(1) if you already hold card 2).
Example
In a real scavenger hunt, travel time between locations varies; in memory, following a pointer takes roughly constant time. The analogy also does not capture the extra memory cost of storing a pointer per node (overhead).
Definition:
A linked list stores elements in nodes scattered across memory. Each node holds a value and a pointer to the next node. There is no index arithmetic — to reach element k, you follow k−1 pointers from the head → O(k). The advantage: inserting or deleting at a known position requires only pointer rewiring → O(1).
Example: Insert at Position 500,000
An array with 1,000,000 elements: inserting at position 500,000 requires shifting ~500,000 elements → O(n). A linked list with a pointer to position 499,999: rewire 2 pointers → O(1). But: finding position 499,999 from the head costs O(n) traversal. The total cost is also O(n) unless you already have a reference to the position.
Variants: Singly vs. Doubly Linked
A singly linked list has pointers in one direction only (forward). A doubly linked list adds backward pointers, making deletion and backward navigation more efficient. Python's collections.deque uses a doubly linked structure for O(1) operations at both ends.
Complexity Table: Linked List
Operation Complexity
──────────────────────────────────────────
Access (position k) O(n)
Search O(n)
Insert/Delete at head O(1)
Insert at known position O(1)
Insert after search O(n)
Misconception: Linked Lists Are Always Better
The O(1) insertion only applies when you already have a pointer to the insertion site. In most real scenarios, you must first search for the position (O(n)), and arrays have better cache locality — making them faster for many workloads despite expensive middle-insertions.
Historical Context
Linked lists emerged in the 1950s from early AI research. Newell, Shaw, and Simon developed IPL (Information Processing Language, 1955), which used linked lists as a core structure. John McCarthy made linked lists the foundation of functional programming with LISP (1958).
Stacks and Queues — Access Disciplines
Stack (LIFO) Last In, First Out — the most recently added item is removed first. Example: undo function in a text editor.
Queue (FIFO) First In, First Out — the earliest added item is served first. Example: request queue on a web server.
Stack & Queue
AnalogyDefinition
A stack of plates: you place clean plates on top and always take the top plate first — the bottom plate stays buried (LIFO). A supermarket checkout line: the first person in line is served first; newcomers join at the back (FIFO). These two principles govern how you are allowed to access the data.
Example
In a real plate stack, you could reach in and grab a middle plate — a proper stack forbids this. At a real checkout, people can leave the line — a strict queue has no such flexibility.
Analogy:
A stack of plates: you place clean plates on top and always take the top plate first — the bottom plate stays buried (LIFO). A supermarket checkout line: the first person in line is served first; newcomers join at the back (FIFO). These two principles govern how you are allowed to access the data.
Example
In a real plate stack, you could reach in and grab a middle plate — a proper stack forbids this. At a real checkout, people can leave the line — a strict queue has no such flexibility.
Definition:
Stacks and queues are abstract data types that define access order, not storage layout. A stack follows LIFO (Last In, First Out): push adds to the top, pop removes the top. A queue follows FIFO (First In, First Out): enqueue adds to the back, dequeue removes from the front. Both achieve O(1) for their core operations regardless of underlying storage.
Example: The Call Stack
1
main() is called → Stack: [main]
2
processData() is called → Stack: [main, processData]
3
calculate() is called → Stack: [main, processData, calculate]
4
calculate() returns → Stack: [main, processData]
5
processData() returns → Stack: [main]
Function calls are managed as stack frames: each new call is pushed on top, and when a function returns, its frame is popped. This is exactly LIFO. If recursion goes too deep (e.g., fib(100000) without optimization), the stack overflows — a stack overflow.
Example: Web Server Queue
A web server receives 1,000 requests per second. Worker threads dequeue requests in arrival order and process them. FIFO ensures no request is starved — first come, first served.
Misconception: A Stack Is a Type of Array
A stack is a usage principle (LIFO contract) that can be implemented on an array, a linked list, or any other backing structure. The principle defines which operations are allowed (push/pop only), not how data is physically stored.
Deep Dive: Call Stack and Stack Overflow
Each function call creates a stack frame with local variables and a return address. Python has a default recursion limit of ~1,000 frames. If exceeded, Python terminates the program with a RecursionError — the famous stack overflow.
Friedrich Bauer and Klaus Samelson formalized the stack in 1957 at TU Munich for evaluating arithmetic expressions. Agner Krarup Erlang founded queueing theory in 1909 for analyzing telephone networks — his work underpins modern network design.
Array vs. Linked List — The Comparison
Array
Contiguous memory. O(1) index access, O(n) insert/delete. Good cache locality. Ideal when reading is more frequent than inserting.
Linked List
Scattered nodes with pointers. O(n) access, O(1) insert at known position. No cache advantage. Ideal when frequent insertions/deletions at known positions dominate.
Complexity Comparison Across All Structures
Stack / Queue push/pop O(1) · enqueue/dequeue O(1) · No random access
Linked List Access O(n) · Insert at head O(1) · At known pos. O(1) · Search O(n)
Click on a data structure to see its strengths and weaknesses. Watch the color pattern: green means O(1) — the operation is lightning fast regardless of data size. Red means O(n) — runtime grows linearly with the number of elements.
Operations by Data Structure
Advantage (small/fast/high)
Neutral
Disadvantage (large/slow/low)
Click a row for detail view
Structure
Access (Index)
Search
Insert
Delete
▸Array
O(1)
O(n)
O(n)
O(n)
▸Linked List
O(n)
O(n)
O(1)
O(1)
▸Stack
O(n)
O(n)
O(1)
O(1)
▸Queue
O(n)
O(n)
O(1)
O(1)
Key Takeaway: No structure is universally best. Arrays win at access, linked lists win at insertion. The right choice depends on which operations your program performs most frequently.
Key Takeaways
Arrays trade cheap reads (O(1) index) for expensive middle-insertions (O(n)) — choose them when you read far more often than you insert.
Linked lists trade cheap local edits (O(1) pointer rewiring) for expensive traversal (O(n)) — choose them when insertions/deletions at known positions dominate.
Stacks (LIFO) and queues (FIFO) are usage contracts, not storage types — they constrain how you access data, enabling powerful patterns like undo, recursion, and fair scheduling.
Quiz: Linear Data Structures
Question 1 / 4
Not completed
What is the key difference between an array and a linked list?
1. What is the key difference between an array and a linked list?
☐ A) Arrays are always faster than linked lists
☐ B) Arrays store elements contiguously in memory; linked lists store them scattered with pointers
☐ C) Linked lists can only store numbers
☐ D) Arrays do not allow inserting elements
2. You have a list of 1,000,000 entries and need to frequently insert elements in the middle. Which structure is more suitable?
☐ A) Array — it has better index access
☐ B) Linked list — IF you already have a reference to the insertion point, insertion is O(1)
☐ C) Stack — it allows push and pop
☐ D) Queue — it processes in order
3. A web server must handle incoming requests fairly — first come, first served. Which principle should it use?
☐ A) Stack (LIFO) — the latest request first
☐ B) Array — direct index access
☐ C) Queue (FIFO) — the earliest request first
☐ D) Linked list — scattered storage
4. Python's list is called 'list' but is internally a dynamic array. Why does this distinction matter?
☐ A) It does not matter — names do not affect performance
☐ B) Because arrays have O(1) index access while true linked lists need O(n) traversal — the name suggests different performance characteristics
☐ C) Because linked lists are always faster
☐ D) Because Python cannot implement true linked lists
Answer Key: 1) B · 2) B · 3) C · 4) B
Learning Goals
You have an array of 1,000,000 elements. How many elements must be shifted to insert a new one at position 500,000? What if you append at the end instead?
You need to build a playlist app. Users frequently add songs at the beginning and end but rarely access songs by position number. Would you choose an array or a linked list? Why?
Your text editor's undo feature stores actions. You type A, B, C, then press undo twice. Which actions are undone and in what order? Which principle (LIFO or FIFO) is at work — and why would the other principle be disastrous here?