Memory Layout Comparison Array vs Linked List in DSA Rust - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Memory layout of array elements in Rust

What is the output of the following Rust code that prints the memory addresses of array elements?

DSA Rust

fn main() {
    let arr = [10, 20, 30];
    for i in 0..arr.len() {
        println!("{:p}", &arr[i]);
    }
}

A Three consecutive memory addresses increasing by size of i32

B Three random memory addresses with no order

C Same memory address printed three times

D Compilation error due to invalid pointer formatting

💡 Hint

Arrays store elements contiguously in memory.

Arrays in Rust store elements in contiguous memory locations. Printing the address of each element shows addresses increasing by the size of each element (i32 is 4 bytes).

❓ Predict Output

intermediate

Memory layout of linked list nodes in Rust

What is the output pattern when printing the memory addresses of nodes in a singly linked list in Rust?

DSA Rust

use std::rc::Rc;

struct Node {
    value: i32,
    next: Option<Rc<Node>>,
}

fn main() {
    let node3 = Rc::new(Node { value: 30, next: None });
    let node2 = Rc::new(Node { value: 20, next: Some(node3.clone()) });
    let node1 = Rc::new(Node { value: 10, next: Some(node2.clone()) });

    let mut current = Some(node1.clone());
    while let Some(node) = current {
        println!("{:p}", Rc::as_ptr(&node));
        current = node.next.clone();
    }
}

A Memory addresses are consecutive increasing by size of Node

B Compilation error due to Rc usage

C Memory addresses appear random and non-contiguous

D Same memory address printed three times

💡 Hint

Linked list nodes are allocated separately on the heap.

Each linked list node is allocated separately on the heap, so their memory addresses are not contiguous and appear random.

🧠 Conceptual

advanced

Why arrays have better cache locality than linked lists?

Which reason best explains why arrays generally have better cache locality than linked lists?

A Arrays can be resized dynamically while linked lists cannot

B Linked lists store elements in reverse order

C Linked lists use more memory per element due to pointers

D Array elements are stored contiguously in memory, improving cache hits

💡 Hint

Think about how CPU cache works with memory addresses.

Arrays store elements next to each other in memory, so accessing one element loads nearby elements into cache, speeding up access. Linked lists have nodes scattered in memory, causing more cache misses.

🔧 Debug

advanced

Identify the cause of unexpected memory layout in linked list

Given this Rust code for a linked list, why might the nodes not be stored contiguously in memory?

DSA Rust

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

fn main() {
    let node3 = Box::new(Node { value: 30, next: None });
    let node2 = Box::new(Node { value: 20, next: Some(node3) });
    let node1 = Box::new(Node { value: 10, next: Some(node2) });

    // Print addresses
    let mut current = Some(&node1);
    while let Some(node) = current {
        println!("{:p}", &**node);
        current = node.next.as_ref().map(|b| &**b);
    }
}

A Each node is allocated separately on the heap, so addresses are not contiguous

B Box allocates nodes contiguously in memory

C Rust compiler optimizes nodes to be contiguous automatically

D The code uses references incorrectly causing undefined behavior

💡 Hint

Box allocates memory on the heap individually for each node.

Box allocates each node separately on the heap, so nodes are not stored contiguously. This causes non-contiguous memory layout for linked lists.

🚀 Application

expert

Choosing data structure for memory-sensitive application

You need to store a large number of integers and access them frequently in order. Which data structure is best for minimizing memory fragmentation and maximizing cache performance?

A Singly linked list, because it uses less memory per element

B Array, because elements are stored contiguously in memory

C Doubly linked list, because it allows backward traversal

D Hash map, because it provides fast key-based access

💡 Hint

Think about how memory layout affects cache and fragmentation.

Arrays store elements contiguously, reducing memory fragmentation and improving cache hits. Linked lists allocate nodes separately, causing fragmentation and poor cache performance.

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