Data Structures & AlgorithmsLinked Lists

What Is a Linked List?

LevelBeginner

Duration55 mins

TopicLinked Lists

4 / 4

Logical Order vs Physical Memory Order

Order Without Adjacency

Here's a profound question: What does it mean for things to be 'in order'?

With a physical bookshelf, order is obvious—book 1 sits left of book 2, which sits left of book 3. The physical arrangement is the order.

But what if book 1 is in your home, book 2 is at your office, and book 3 is at a library across town? They're still 'in order' if you know: start at home → go to office → go to library. The books don't need to be physically adjacent; you just need directions from each location to the next.

This is exactly how linked lists work. The logical order (the sequence 1, 2, 3) is independent of physical memory order (where nodes actually reside). Understanding this distinction unlocks deep insight into how linked lists function and why they behave differently from arrays.

What You Will Learn

By the end of this page, you will understand how arrays conflate logical and physical order, how linked lists separate them, why this separation enables efficient insertions and deletions, and the mental model needed to reason about linked list operations correctly.

Arrays: Where Order Equals Physical Position

In an array, logical order is determined by physical memory position. The element at the lowest address is 'first,' the next address is 'second,' and so on.

This coupling has consequences:

Direct address calculation: Element i is at base + i × size. Position = order.
Insertion requires shifting: To insert between positions 3 and 4, you must physically move elements 4, 5, 6, ... to make room.
Deletion requires compacting: Removing element 3 leaves a gap. You must shift 4, 5, 6, ... down to fill it.
Contiguous memory required: The entire sequence must fit in one continuous block.

Let's visualize inserting 'X' between elements B and C in an array:

Array Insertion: Physical Movement Required
Step	Memory State	Operations
Initial	[A][B][C][D][E]	Elements at positions 0-4
Make room	[A][B][ ][C→][D→][E→]	Shift C, D, E right (3 moves)
Insert X	[A][B][X][C][D][E]	Place X at position 2
Total cost	—	O(n) moves for each insertion

The Cost of Coupled Order

Because physical position determines logical order, changing the logical order requires changing physical positions. Every insertion in the middle of an array is O(n)—you must move n/2 elements on average. For large arrays with frequent insertions, this becomes prohibitively expensive.

Linked Lists: Order Through Connections

In a linked list, logical order is determined by pointers, not physical positions. Nodes can live anywhere in memory. Their order is defined solely by which node points to which.

This decoupling enables:

Insertion without shifting: To insert between nodes B and C, create a new node, point it to C, and point B to the new node. Nothing moves.
Deletion without compacting: To remove node C, simply point B directly to D. C is bypassed. No other nodes change.
Non-contiguous allocation: Nodes can be scattered across memory. No fragmentation problems for large lists.
Dynamic size: Adding a node just requires allocating one more node anywhere. No reallocation of the entire structure.

Let's visualize the same insertion of 'X' between B and C in a linked list:

Linked List Insertion: Pointer Redirection Only
Step	Pointer State	Operations
Initial	head→[A]→[B]→[C]→[D]→[E]→null	Chain of 5 nodes
Create X	X created at random address	Allocate 1 new node
Point X→C	X.next = C	1 pointer assignment
Point B→X	B.next = X	1 pointer assignment
Result	head→[A]→[B]→[X]→[C]→[D]→[E]→null	X is now in sequence
Total cost	—	O(1) — constant time!

The Power of Decoupled Order

No nodes moved. Nodes A, C, D, E are completely unchanged. Only two pointers were modified. This is why linked list insertion—once you're at the insertion point—is O(1). Physical memory locations never change; only logical connections do.

Visualizing the Decoupling

Let's examine memory layouts in detail to cement this understanding.

Array Memory Layout:

Address:  0x1000  0x1004  0x1008  0x100C  0x1010
Content:  [  A  ] [  B  ] [  C  ] [  D  ] [  E  ]
Logical:   0th     1st     2nd     3rd     4th

Physical position (address) determines logical position. Consecutive addresses = consecutive elements.

Linked List Memory Layout:

Address 0x3000: [A | next→0x1500]
Address 0x1500: [B | next→0x5200]
Address 0x5200: [C | next→0x0800]
Address 0x0800: [D | next→0x2100]
Address 0x2100: [E | next→null]

head = 0x3000

Addresses are random! Logical order is A→B→C→D→E, but physically:

A is at 0x3000
B is at 0x1500 (not adjacent to A)
C is at 0x5200 (far from B)
D is at 0x0800 (before A and B in memory!)
E is at 0x2100

The logical first element (A) isn't at the lowest address. The logical last element (E) isn't at the highest. Order exists only in the pointer chain.

Memory Layout Is Arbitrary

When you allocate nodes (via new/malloc), the memory allocator decides where they go based on available memory. You have no control over physical placement, nor do you need it. The pointer chain maintains order regardless of where nodes physically reside.

Insertion: The Pointer Surgery

Let's trace through an insertion operation step by step, paying attention to what changes and what doesn't.

Scenario: Insert node X between nodes B and C.

Before:

B (at 0x1500): [B | next→0x5200]
C (at 0x5200): [C | next→...]

B points to C. This is the connection we'll modify.

Step 1: Allocate X

X (at 0x9000): [X | next→null]  // Allocated at some address

Step 2: Point X to C

X.next = B.next  // X now points to what B pointed to (C)
X (at 0x9000): [X | next→0x5200]

Step 3: Point B to X

B.next = X  // B now points to X instead of C
B (at 0x1500): [B | next→0x9000]

After:

B (at 0x1500): [B | next→0x9000]  → X (at 0x9000): [X | next→0x5200] → C (at 0x5200)

Logical order: B → X → C Physical addresses: 0x1500 → 0x9000 → 0x5200 (not sequential at all!)

Insert After Node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Insert a new node with value 'data' after node 'prev'
function insertAfter<T>(prev: ListNode<T>, data: T): ListNode<T> {
    // Step 1: Create the new node
    const newNode = new ListNode(data);
    
    // Step 2: Point new node to what prev pointed to
    newNode.next = prev.next;
    
    // Step 3: Point prev to new node
    prev.next = newNode;
    
    return newNode;
}
 
// Example: Insert 'X' after node B
// Before: A → B → C → D
// Call: insertAfter(nodeB, 'X')
// After: A → B → X → C → D
 
// Note: This is O(1) - no loops, no element movement

Order of Operations Matters!

You MUST point the new node to the next node BEFORE redirecting the previous node. If you do step 3 before step 2, you lose the reference to the rest of the list! This is a classic linked list bug.

Deletion: Bypassing a Node

Deletion in linked lists is equally elegant: you simply redirect pointers to bypass the node being removed.

Scenario: Delete node C from the list A → B → C → D.

Before:

B (at 0x1500): [B | next→0x5200]  // Points to C
C (at 0x5200): [C | next→0x0800]  // Points to D
D (at 0x0800): [D | next→...]

The Bypass:

B.next = C.next  // B now points to D, skipping C
B (at 0x1500): [B | next→0x0800]  // Points directly to D

After:

A → B → D → E

Node C is now unreachable from the head. In languages with garbage collection (Java, Python, JS), it will be automatically freed. In languages without (C/C++), you must explicitly free the memory.

Delete Node After
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Delete the node that comes after 'prev'
function deleteAfter<T>(prev: ListNode<T>): T | null {
    if (prev.next === null) {
        return null;  // Nothing to delete
    }
    
    const nodeToDelete = prev.next;
    const deletedValue = nodeToDelete.data;
    
    // Bypass the node: prev now points to what the deleted node pointed to
    prev.next = nodeToDelete.next;
    
    // nodeToDelete is now unreachable (will be garbage collected)
    return deletedValue;
}
 
// Example: Delete node C (which is after B)
// Before: A → B → C → D
// Call: deleteAfter(nodeB)
// After: A → B → D
// Returns: 'C'
 
// Note: This is O(1) - no loops, no element movement

Physical Memory Unchanged

Notice that the deleted node's memory still exists (until garbage collected or freed). We haven't erased data; we've made it unreachable. The logical structure changed; the physical memory contents (until reclaimed) did not.

Order Flexibility: Reordering Is Cheap

Because logical order is just pointers, reordering a linked list doesn't move any data in memory—it only changes pointers.

Example: Moving Node D to After A

Before: A → B → C → D → E Goal: A → D → B → C → E

In an array, this would mean:

Save D's value
Shift B and C right
Insert D's value at position 1

Total: O(n) operations, actual data movement.

In a linked list:

C.next = D.next (C now points to E)
D.next = A.next (D now points to B)
A.next = D (A now points to D)

Total: 3 pointer assignments, O(1). No data moved.

Reversing a Linked List

Reversing an array requires O(n) swaps. Reversing a linked list requires O(n) pointer reversals—same complexity, but no data is moved in memory. Each node stays where it is; only the arrows change direction.

Array Reordering

•Move D: Shift B, C, copy D → O(n)
•Reverse: Swap pairs → O(n) copies
•Sort: O(n log n) with many element moves
•Large elements = expensive copies

Linked List Reordering

•Move D: 3 pointer changes → O(1)
•Reverse: O(n) pointer reversals, no copies
•Sort: O(n log n) but only pointer changes
•Node size irrelevant—always pointer operations

Memory and Garbage Collection Implications

The decoupling of logical and physical order has important implications for memory management:

Fragmented But Functional

Nodes allocated at different times will be scattered across the heap. Unlike arrays that might fail to allocate if no contiguous block exists, linked lists work fine with fragmented memory.

Garbage Collection Behavior

In garbage-collected languages, a node is reclaimed when unreachable:

Delete a node → it becomes unreachable → GC frees it
'Lose' the head pointer → entire list becomes unreachable → all freed

Memory Leaks in Manual Memory Languages

In C/C++, you must explicitly free each node. Common bugs:

Deleting head without traversing to free all nodes → leak
Breaking the chain and losing references → leak
Circular references with manual allocation → permanent leak

Reference Counting Corner Cases

In reference-counted environments (Python, Swift, Rust Arc), circular linked lists can cause leaks:

Node A points to B, B points to A
Both have reference count ≥ 1
Neither can be freed automatically

Know Your Memory Model

Linked lists interact with memory management differently than arrays. In GC languages, they 'just work' but create GC pressure. In manual memory languages, every node allocation/deallocation is your responsibility. Understand your language's model before implementing linked lists.

When Physical Order Actually Matters

While linked lists free us from physical order constraints, physical order still affects performance in subtle ways:

Cache Performance

As we discussed earlier, CPU caches load 64-byte cache lines. If your nodes were (hypothetically) physically adjacent, traversal would be cache-friendly. In practice, linked list nodes are scattered, causing cache misses.

Memory Allocator Patterns

Some allocators try to place consecutive allocations near each other. Nodes allocated together might be somewhat physically close, improving cache behavior slightly. But this is allocator-dependent and not guaranteed.

Arena Allocation Pattern

Advanced systems sometimes allocate linked list nodes from a pre-allocated array (arena). This forces physical proximity while maintaining logical flexibility—a best-of-both-worlds approach used in performance-critical code.

NUMA Considerations

On multi-socket systems with Non-Uniform Memory Access (NUMA), memory access time depends on which CPU socket allocated the memory. Scattered nodes may incur cross-socket access penalties.

Performance-Critical Code

In most application code, the flexibility of linked lists outweighs cache concerns. But in performance-critical systems (databases, game engines, compilers), developers sometimes use hybrid approaches—arena-allocated nodes, unrolled linked lists, or cache-conscious data structures—to get linked structure benefits with better cache behavior.

The Complete Mental Model

Let's consolidate everything into a comprehensive mental model for linked lists:

The Visualization:

Think of nodes as boxes floating in space (memory), connected by strings (pointers). The strings define the path; the boxes can be anywhere.

The Core Principle:

Logical order is defined by pointer chains, not by physical memory proximity.

Implications:

Access: Follow the string from the start; can't jump to arbitrary boxes
Insertion: Tie a new box into the string chain; other boxes don't move
Deletion: Un-tie a box from the chain; other boxes don't move
Reordering: Re-route strings; boxes stay in place
Growth: Add boxes anywhere; no reallocation needed
Shrinkage: Remove boxes; memory freed immediately

The Trade-Off Summary:

Characteristic	Array	Linked List
Order determined by	Physical position	Pointer chain
Access any element	O(1)	O(n)
Insert/delete middle	O(n) shifts	O(1) pointer change
Memory allocation	Contiguous required	Scattered OK
Cache behavior	Excellent	Poor
Memory overhead	None	Pointer per node

Hold This Model Firmly

This mental model—order through connections, not positions—is the foundation for understanding all linked structures: doubly linked lists, circular lists, trees, graphs, and more. Every advanced data structure builds on this principle of pointer-based relationships.

Summary: Logical vs Physical Order

We've completed the conceptual foundation for understanding linked lists:

Arrays:

Logical order = physical memory order
Position is computed from address
Insertion/deletion requires physical movement
Contiguous memory required

Linked Lists:

Logical order = pointer chain
Position is traversed via pointers
Insertion/deletion changes pointers only
Scattered memory is fine

The Key Insight:

By decoupling logical order from physical order, linked lists gain flexibility for modification at the cost of access speed. This trade-off defines when each structure is appropriate.

Key Takeaways

•Arrays couple logical and physical order — position in memory = position in sequence
•Linked lists decouple them — nodes can be anywhere; pointers define order
•This enables O(1) insertion/deletion — only pointer changes, no element movement
•Physical memory layout is irrelevant to the logical sequence
•Reordering is cheap — change pointers, not data
•This principle underlies all linked structures — trees, graphs, and beyond

Module Complete!

You now have a complete conceptual understanding of what a linked list is:

Definition: A chain of nodes connected by pointers
Nodes: Data + next pointer
Access Pattern: Sequential (traverse from head)
Order: Logical (pointer-defined), not physical (memory-defined)

In the next module, we'll explore the Singly Linked List in depth—its structure, visual representation, and why the head pointer is everything.

Module Complete: What Is a Linked List?

Congratulations! You now understand the fundamental mental model of linked lists. You can articulate what a linked list is, how nodes work, why sequential access is necessary, and how logical order is maintained through pointers rather than physical memory positions. You're ready to dive into specific linked list implementations.

4 / 4

Loading learning content...

Data Structures & AlgorithmsLinked Lists

What Is a Linked List?

LevelBeginner

Duration55 mins

TopicLinked Lists

4 / 4

Logical Order vs Physical Memory Order

Order Without Adjacency

Here's a profound question: What does it mean for things to be 'in order'?

With a physical bookshelf, order is obvious—book 1 sits left of book 2, which sits left of book 3. The physical arrangement is the order.

What You Will Learn

Arrays: Where Order Equals Physical Position

In an array, logical order is determined by physical memory position. The element at the lowest address is 'first,' the next address is 'second,' and so on.

This coupling has consequences:

Direct address calculation: Element i is at base + i × size. Position = order.
Insertion requires shifting: To insert between positions 3 and 4, you must physically move elements 4, 5, 6, ... to make room.
Deletion requires compacting: Removing element 3 leaves a gap. You must shift 4, 5, 6, ... down to fill it.
Contiguous memory required: The entire sequence must fit in one continuous block.

Let's visualize inserting 'X' between elements B and C in an array:

Array Insertion: Physical Movement Required
Step	Memory State	Operations
Initial	[A][B][C][D][E]	Elements at positions 0-4
Make room	[A][B][ ][C→][D→][E→]	Shift C, D, E right (3 moves)
Insert X	[A][B][X][C][D][E]	Place X at position 2
Total cost	—	O(n) moves for each insertion

The Cost of Coupled Order

Linked Lists: Order Through Connections

In a linked list, logical order is determined by pointers, not physical positions. Nodes can live anywhere in memory. Their order is defined solely by which node points to which.

This decoupling enables:

Insertion without shifting: To insert between nodes B and C, create a new node, point it to C, and point B to the new node. Nothing moves.
Deletion without compacting: To remove node C, simply point B directly to D. C is bypassed. No other nodes change.
Non-contiguous allocation: Nodes can be scattered across memory. No fragmentation problems for large lists.
Dynamic size: Adding a node just requires allocating one more node anywhere. No reallocation of the entire structure.

Let's visualize the same insertion of 'X' between B and C in a linked list:

Linked List Insertion: Pointer Redirection Only
Step	Pointer State	Operations
Initial	head→[A]→[B]→[C]→[D]→[E]→null	Chain of 5 nodes
Create X	X created at random address	Allocate 1 new node
Point X→C	X.next = C	1 pointer assignment
Point B→X	B.next = X	1 pointer assignment
Result	head→[A]→[B]→[X]→[C]→[D]→[E]→null	X is now in sequence
Total cost	—	O(1) — constant time!

The Power of Decoupled Order

Visualizing the Decoupling

Let's examine memory layouts in detail to cement this understanding.

Array Memory Layout:

Address:  0x1000  0x1004  0x1008  0x100C  0x1010
Content:  [  A  ] [  B  ] [  C  ] [  D  ] [  E  ]
Logical:   0th     1st     2nd     3rd     4th

Physical position (address) determines logical position. Consecutive addresses = consecutive elements.

Linked List Memory Layout:

Address 0x3000: [A | next→0x1500]
Address 0x1500: [B | next→0x5200]
Address 0x5200: [C | next→0x0800]
Address 0x0800: [D | next→0x2100]
Address 0x2100: [E | next→null]

head = 0x3000

Addresses are random! Logical order is A→B→C→D→E, but physically:

A is at 0x3000
B is at 0x1500 (not adjacent to A)
C is at 0x5200 (far from B)
D is at 0x0800 (before A and B in memory!)
E is at 0x2100

The logical first element (A) isn't at the lowest address. The logical last element (E) isn't at the highest. Order exists only in the pointer chain.

Memory Layout Is Arbitrary

Insertion: The Pointer Surgery

Let's trace through an insertion operation step by step, paying attention to what changes and what doesn't.

Scenario: Insert node X between nodes B and C.

Before:

B (at 0x1500): [B | next→0x5200]
C (at 0x5200): [C | next→...]

B points to C. This is the connection we'll modify.

Step 1: Allocate X

X (at 0x9000): [X | next→null]  // Allocated at some address

Step 2: Point X to C

X.next = B.next  // X now points to what B pointed to (C)
X (at 0x9000): [X | next→0x5200]

Step 3: Point B to X

B.next = X  // B now points to X instead of C
B (at 0x1500): [B | next→0x9000]

After:

B (at 0x1500): [B | next→0x9000]  → X (at 0x9000): [X | next→0x5200] → C (at 0x5200)

Logical order: B → X → C Physical addresses: 0x1500 → 0x9000 → 0x5200 (not sequential at all!)

Insert After Node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Insert a new node with value 'data' after node 'prev'
function insertAfter<T>(prev: ListNode<T>, data: T): ListNode<T> {
    // Step 1: Create the new node
    const newNode = new ListNode(data);
    
    // Step 2: Point new node to what prev pointed to
    newNode.next = prev.next;
    
    // Step 3: Point prev to new node
    prev.next = newNode;
    
    return newNode;
}
 
// Example: Insert 'X' after node B
// Before: A → B → C → D
// Call: insertAfter(nodeB, 'X')
// After: A → B → X → C → D
 
// Note: This is O(1) - no loops, no element movement

Order of Operations Matters!

You MUST point the new node to the next node BEFORE redirecting the previous node. If you do step 3 before step 2, you lose the reference to the rest of the list! This is a classic linked list bug.

Deletion: Bypassing a Node

Deletion in linked lists is equally elegant: you simply redirect pointers to bypass the node being removed.

Scenario: Delete node C from the list A → B → C → D.

Before:

B (at 0x1500): [B | next→0x5200]  // Points to C
C (at 0x5200): [C | next→0x0800]  // Points to D
D (at 0x0800): [D | next→...]

The Bypass:

B.next = C.next  // B now points to D, skipping C
B (at 0x1500): [B | next→0x0800]  // Points directly to D

After:

A → B → D → E

Node C is now unreachable from the head. In languages with garbage collection (Java, Python, JS), it will be automatically freed. In languages without (C/C++), you must explicitly free the memory.

Delete Node After
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Delete the node that comes after 'prev'
function deleteAfter<T>(prev: ListNode<T>): T | null {
    if (prev.next === null) {
        return null;  // Nothing to delete
    }
    
    const nodeToDelete = prev.next;
    const deletedValue = nodeToDelete.data;
    
    // Bypass the node: prev now points to what the deleted node pointed to
    prev.next = nodeToDelete.next;
    
    // nodeToDelete is now unreachable (will be garbage collected)
    return deletedValue;
}
 
// Example: Delete node C (which is after B)
// Before: A → B → C → D
// Call: deleteAfter(nodeB)
// After: A → B → D
// Returns: 'C'
 
// Note: This is O(1) - no loops, no element movement

Physical Memory Unchanged

Order Flexibility: Reordering Is Cheap

Because logical order is just pointers, reordering a linked list doesn't move any data in memory—it only changes pointers.

Example: Moving Node D to After A

Before: A → B → C → D → E Goal: A → D → B → C → E

In an array, this would mean:

Save D's value
Shift B and C right
Insert D's value at position 1

Total: O(n) operations, actual data movement.

In a linked list:

C.next = D.next (C now points to E)
D.next = A.next (D now points to B)
A.next = D (A now points to D)

Total: 3 pointer assignments, O(1). No data moved.

Reversing a Linked List

Array Reordering

•Move D: Shift B, C, copy D → O(n)
•Reverse: Swap pairs → O(n) copies
•Sort: O(n log n) with many element moves
•Large elements = expensive copies

Linked List Reordering

•Move D: 3 pointer changes → O(1)
•Reverse: O(n) pointer reversals, no copies
•Sort: O(n log n) but only pointer changes
•Node size irrelevant—always pointer operations

Memory and Garbage Collection Implications

The decoupling of logical and physical order has important implications for memory management:

Fragmented But Functional

Nodes allocated at different times will be scattered across the heap. Unlike arrays that might fail to allocate if no contiguous block exists, linked lists work fine with fragmented memory.

Garbage Collection Behavior

In garbage-collected languages, a node is reclaimed when unreachable:

Delete a node → it becomes unreachable → GC frees it
'Lose' the head pointer → entire list becomes unreachable → all freed

Memory Leaks in Manual Memory Languages

In C/C++, you must explicitly free each node. Common bugs:

Deleting head without traversing to free all nodes → leak
Breaking the chain and losing references → leak
Circular references with manual allocation → permanent leak

Reference Counting Corner Cases

In reference-counted environments (Python, Swift, Rust Arc), circular linked lists can cause leaks:

Node A points to B, B points to A
Both have reference count ≥ 1
Neither can be freed automatically

Know Your Memory Model

When Physical Order Actually Matters

While linked lists free us from physical order constraints, physical order still affects performance in subtle ways:

Cache Performance

Memory Allocator Patterns

Arena Allocation Pattern

NUMA Considerations

On multi-socket systems with Non-Uniform Memory Access (NUMA), memory access time depends on which CPU socket allocated the memory. Scattered nodes may incur cross-socket access penalties.

Performance-Critical Code

The Complete Mental Model

Let's consolidate everything into a comprehensive mental model for linked lists:

The Visualization:

Think of nodes as boxes floating in space (memory), connected by strings (pointers). The strings define the path; the boxes can be anywhere.

The Core Principle:

Logical order is defined by pointer chains, not by physical memory proximity.

Implications:

Access: Follow the string from the start; can't jump to arbitrary boxes
Insertion: Tie a new box into the string chain; other boxes don't move
Deletion: Un-tie a box from the chain; other boxes don't move
Reordering: Re-route strings; boxes stay in place
Growth: Add boxes anywhere; no reallocation needed
Shrinkage: Remove boxes; memory freed immediately

The Trade-Off Summary:

Characteristic	Array	Linked List
Order determined by	Physical position	Pointer chain
Access any element	O(1)	O(n)
Insert/delete middle	O(n) shifts	O(1) pointer change
Memory allocation	Contiguous required	Scattered OK
Cache behavior	Excellent	Poor
Memory overhead	None	Pointer per node

Hold This Model Firmly

Summary: Logical vs Physical Order

We've completed the conceptual foundation for understanding linked lists:

Arrays:

Logical order = physical memory order
Position is computed from address
Insertion/deletion requires physical movement
Contiguous memory required

Linked Lists:

Logical order = pointer chain
Position is traversed via pointers
Insertion/deletion changes pointers only
Scattered memory is fine

The Key Insight:

By decoupling logical order from physical order, linked lists gain flexibility for modification at the cost of access speed. This trade-off defines when each structure is appropriate.

Key Takeaways

•Arrays couple logical and physical order — position in memory = position in sequence
•Linked lists decouple them — nodes can be anywhere; pointers define order
•This enables O(1) insertion/deletion — only pointer changes, no element movement
•Physical memory layout is irrelevant to the logical sequence
•Reordering is cheap — change pointers, not data
•This principle underlies all linked structures — trees, graphs, and beyond

Module Complete!

You now have a complete conceptual understanding of what a linked list is:

Definition: A chain of nodes connected by pointers
Nodes: Data + next pointer
Access Pattern: Sequential (traverse from head)
Order: Logical (pointer-defined), not physical (memory-defined)

In the next module, we'll explore the Singly Linked List in depth—its structure, visual representation, and why the head pointer is everything.

Module Complete: What Is a Linked List?

4 / 4