Memory Layout Comparison Array vs Linked List in DSA Rust - Visual Comparison

Concept Flow - Memory Layout Comparison Array vs Linked List

Array Memory

↓

Contiguous Blocks

↓

Fast Index Access

↓

Fixed Size or Resize Cost

↓

Linked List Memory

↓

Nodes Scattered in Memory

↓

Each Node Points to Next

↓

Flexible Size, Slower Access

Shows two separate flows: array uses contiguous memory blocks for fast access but fixed size; linked list uses scattered nodes with pointers for flexible size but slower access.

Execution Sample

DSA Rust

let arr = [10, 20, 30];
// Memory: contiguous blocks

struct Node {
  data: i32,
  next: Option<Box<Node>>,
}
// Memory: scattered nodes linked by pointers

Shows array stored in contiguous memory and linked list nodes scattered with pointers.

Execution Table

Step	Operation	Memory Layout	Pointer Changes	Visual State
1	Create array [10, 20, 30]	Contiguous blocks allocated for 3 elements	No pointers changed	┌─────┬─────┬─────┐ │ 10 │ 20 │ 30 │ └─────┴─────┴─────┘ contiguous memory
2	Create linked list node with data 10	Node allocated at scattered memory location	head → node1	┌────────┐ │ data:10│ │ next:∅ │ └────────┘ scattered node
3	Create linked list node with data 20	Another scattered node allocated	node1.next → node2	┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│ │ next:─┼ │ next:∅ │ └────────┘ └────────┘
4	Create linked list node with data 30	Another scattered node allocated	node2.next → node3	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│ │ next:─┼ │ next:─┼ │ next:∅ │ └────────┘ └────────┘ └────────┘
5	Access array element at index 1	Direct access via offset	No pointer changes	Value: 20 (fast access)
6	Access linked list element at position 1	Traverse nodes one by one	Traverse: head → node1 → node2	Value: 20 (slower access)
7	Resize array to add element 40	Allocate new contiguous block, copy elements	No pointer changes	┌─────┬─────┬─────┬─────┐ │ 10 │ 20 │ 30 │ 40 │ └─────┴─────┴─────┴─────┘
8	Add node with data 40 to linked list end	Allocate new scattered node	node3.next → node4	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│ │ next:─┼ │ next:─┼ │ next:─┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘
9	End of demonstration	No further changes	No pointer changes	Final states shown above

💡 All steps completed showing memory layout and pointer changes for array and linked list

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
Array	∅	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]	[10, 20, 30, 40]	[10, 20, 30, 40]	[10, 20, 30, 40]
LinkedList Head	∅	∅	node1(10)	node1(10)	node1(10)	node1(10)	node1(10)	node1(10)	node1(10)	node1(10)
LinkedList Nodes	∅	∅	node1(10) → ∅	node1(10) → node2(20) → ∅	node1(10) → node2(20) → node3(30) → ∅	node1(10) → node2(20) → node3(30) → ∅	node1(10) → node2(20) → node3(30) → ∅	node1(10) → node2(20) → node3(30) → ∅	node1(10) → node2(20) → node3(30) → node4(40) → ∅	node1(10) → node2(20) → node3(30) → node4(40) → ∅

Key Moments - 3 Insights

Why does accessing an element in an array feel faster than in a linked list?

Because arrays store elements in contiguous memory blocks allowing direct access by index, while linked lists require traversal node by node as shown in execution_table steps 5 and 6.

Why does resizing an array require copying elements but linked lists do not?

Arrays need a new contiguous block to fit more elements, so existing elements are copied (step 7). Linked lists add new nodes anywhere in memory by updating pointers (step 8), no copying needed.

What does 'scattered memory' mean for linked lists?

It means each node can be anywhere in memory, not next to each other, connected only by pointers as shown in pointer changes in steps 2 to 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the pointer change?

A node1.next → node2

B head → node2

C node2.next → node3

D No pointer changes

💡 Hint

Check the 'Pointer Changes' column at step 3 in execution_table

At which step does the array resize happen?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look for 'Resize array' operation in execution_table

If we add a node with data 50 after step 8, what pointer changes would occur?

A head → node5

B node4.next → node5

C node3.next → node5

D No pointer changes

💡 Hint

Observe how new nodes are linked at the end in execution_table step 8

Concept Snapshot

Array:
- Stores elements in contiguous memory
- Fast direct access by index
- Fixed size or costly resize

Linked List:
- Nodes scattered in memory
- Each node points to next
- Flexible size, slower access
- Pointer updates link nodes

Full Transcript

This visual execution compares memory layout of arrays and linked lists. Arrays allocate contiguous memory blocks for elements, enabling fast direct access by index but resizing requires copying all elements to a new block. Linked lists allocate nodes scattered in memory, each node holding data and a pointer to the next node. Accessing elements requires traversal from head node through pointers, making it slower but allowing flexible size without copying. Pointer changes show how nodes link together. The execution table traces creation of array and linked list nodes, pointer updates, and access operations step-by-step. Key moments clarify why arrays are faster for access and why linked lists are flexible. The visual quiz tests understanding of pointer changes and resizing steps. The snapshot summarizes key differences in memory layout and access behavior.

Practice

1. Which statement best describes the memory layout difference between an array and a linked list?

easy

A. A linked list stores elements contiguously, but an array uses pointers between elements.

B. Both array and linked list store elements contiguously in memory.

C. Arrays use pointers to link elements, linked lists store elements contiguously.

D. An array stores elements contiguously in memory, while a linked list stores elements scattered with pointers.

Solution

1. Step 1: Understand array memory layout

   An array stores all its elements in a continuous block of memory, so elements are next to each other.

2. Step 2: Understand linked list memory layout

   A linked list stores each element separately in memory, and each element has a pointer to the next, so elements are scattered.

3. Final Answer:

   An array stores elements contiguously in memory, while a linked list stores elements scattered with pointers. -> Option D

4. Quick Check:

   Array = contiguous, Linked list = scattered with pointers [OK]

Hint: Arrays are continuous blocks; linked lists use pointers [OK]

Common Mistakes:

• Thinking linked lists store elements contiguously
• Confusing pointers usage between arrays and linked lists
• Assuming arrays use pointers between elements

2. Which Rust code snippet correctly declares a fixed-size array of 5 integers with explicit type annotation?

easy

A. let arr = [1, 2, 3, 4, 5];

B. let arr = vec![1, 2, 3, 4, 5];

C. let arr: [i32; 5] = [1, 2, 3, 4, 5];

D. let arr = (1, 2, 3, 4, 5);

Solution

1. Step 1: Identify fixed-size array syntax in Rust

   Rust fixed-size arrays require type and size: [type; size].

2. Step 2: Check each option

   let arr: [i32; 5] = [1, 2, 3, 4, 5]; uses let arr: [i32; 5] = [1, 2, 3, 4, 5]; which is correct fixed-size array syntax.

3. Final Answer:

   let arr: [i32; 5] = [1, 2, 3, 4, 5]; -> Option C

4. Quick Check:

   Fixed-size array syntax = [type; size] [OK]

Hint: Fixed arrays need type and size: [type; size] [OK]

Common Mistakes:

• Using vec! macro for fixed-size array
• Missing type and size in array declaration
• Using tuple syntax instead of array

3. Consider this Rust code creating a linked list node struct and two nodes linked together:

struct Node {
    value: i32,
    next: Option,
}

fn main() {
    let node2 = Node { value: 20, next: None };
    let node1 = Node { value: 10, next: Some(Box::new(node2)) };
    println!("{} -> {} -> None", node1.value, node1.next.as_ref().unwrap().value);
}

What is the printed output?

medium

A. 10 -> 20 -> None

B. 20 -> 10 -> None

C. 10 -> None -> None

D. Compilation error due to ownership

Solution

1. Step 1: Understand node creation and linking

   node2 has value 20 and no next node. node1 has value 10 and points to node2 via Box.

2. Step 2: Trace the print statement

   Prints node1.value (10), then node1.next's value (20), then "None" for end.

3. Final Answer:

   10 -> 20 -> None -> Option A

4. Quick Check:

   Linked nodes print values in order: 10 then 20 [OK]

Hint: Follow pointers to print linked list values [OK]

Common Mistakes:

• Confusing order of nodes
• Expecting None printed as value
• Thinking ownership causes compile error here

4. This Rust code tries to create a linked list but fails to compile:

struct Node {
    value: i32,
    next: Option,
}

fn main() {
    let node1 = Node { value: 10, next: None };
    let node2 = Node { value: 20, next: Some(Box::new(node1)) };
    println!("{} -> {} -> None", node1.value, node2.value);
}

What is the main reason for the compilation error?

medium

A. Use of moved value: node1 is moved into node2 and cannot be used again

B. Missing lifetime annotations on struct Node

C. Box cannot be used inside Option

D. Printing node2.value is invalid syntax

Solution

1. Step 1: Analyze ownership of node1

   node1 is moved into Box inside node2's next field, so node1 cannot be used after move.

2. Step 2: Identify error cause

   Because node1 is moved, any further use or move causes compile error "use of moved value".

3. Final Answer:

   Use of moved value: node1 is moved into node2 and cannot be used again -> Option A

4. Quick Check:

   Ownership moved node1 causes compile error [OK]

Hint: Moving ownership invalidates original variable [OK]

Common Mistakes:

• Thinking Box inside Option is invalid
• Assuming missing lifetimes cause error here
• Believing print syntax is wrong

5. You want to store 1 million integers and frequently access elements by index. Considering memory layout and performance, which data structure is better in Rust and why?

hard

A. Array, because linked lists cannot store integers efficiently.

B. Array, because elements are stored contiguously allowing fast index access and better cache usage.

C. Linked list, because it uses less memory than arrays for large data.

D. Linked list, because it uses pointers and is faster for random access.

Solution

1. Step 1: Consider access pattern and memory layout

   Arrays store elements contiguously, so accessing by index is O(1) and cache-friendly.

2. Step 2: Compare linked list access and memory use

   Linked lists store elements scattered with pointers, making index access O(n) and less cache efficient.

3. Final Answer:

   Array, because elements are stored contiguously allowing fast index access and better cache usage. -> Option B

4. Quick Check:

   Contiguous arrays = fast index access [OK]

Hint: For fast index access, choose arrays over linked lists [OK]

Common Mistakes:

• Assuming linked lists are faster for index access
• Thinking linked lists use less memory for large data
• Believing arrays cannot store large data efficiently