Linked List vs Array When to Choose Which in DSA Rust - Trade-offs & Analysis

Mental Model

Arrays store items in a row, easy to find by position but hard to change size. Linked lists chain items with pointers, easy to add or remove but slower to find by position.

Analogy: An array is like a row of mailboxes where each box has a fixed spot. A linked list is like a treasure hunt where each clue points to the next spot.

Array: [1][2][3][4][5]
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: Compare adding a new item at the start and accessing the third item in both array and linked list with initial data 1, 2, 3, 4, 5

Goal: Show how adding at start and accessing by position differ in arrays and linked lists

Step 1: Add 0 at start of array by shifting all elements right

[0][1][2][3][4][5]

Why: Arrays need to move all items to make space at the start

Step 2: Access third item in array directly by index 2

[0][1][2][3][4][5] (accessed value: 2)

Why: Arrays allow direct access by position quickly

Step 3: Add 0 at start of linked list by creating new node pointing to old head

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Linked lists add at start by changing just one pointer

Step 4: Access third item in linked list by moving pointer from head twice

0 -> 1 -> [2] -> 3 -> 4 -> 5 -> null (accessed value: 2)

Why: Linked lists must follow pointers step by step to find position

Result:

Array after add: [0][1][2][3][4][5]
Linked List after add: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
Accessed third item: 2 in both

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

// Node for singly linked list
#[derive(Debug)]
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node { val, next: None }))
    }
}

// Linked list with head pointer
struct LinkedList {
    head: Option<Rc<RefCell<Node>>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { head: None }
    }

    // Add at start by creating new node pointing to old head
    fn add_at_start(&mut self, val: i32) {
        let new_node = Node::new(val);
        new_node.borrow_mut().next = self.head.take();
        self.head = Some(new_node);
    }

    // Access nth item by following pointers
    fn get_nth(&self, n: usize) -> Option<i32> {
        let mut current = self.head.clone();
        let mut count = 0;
        while let Some(node) = current {
            if count == n {
                return Some(node.borrow().val);
            }
            current = node.borrow().next.clone();
            count += 1;
        }
        None
    }

    // Print list as string
    fn to_string(&self) -> String {
        let mut result = String::new();
        let mut current = self.head.clone();
        while let Some(node) = current {
            result.push_str(&format!("{} -> ", node.borrow().val));
            current = node.borrow().next.clone();
        }
        result.push_str("null");
        result
    }
}

fn main() {
    // Array example
    let mut array = vec![1, 2, 3, 4, 5];
    // Add 0 at start by shifting
    array.insert(0, 0);
    println!("Array after add at start: {:?}", array);
    // Access third item (index 2)
    println!("Array third item: {}", array[2]);

    // Linked list example
    let mut list = LinkedList::new();
    // Build list 1->2->3->4->5
    for &v in &[5, 4, 3, 2, 1] {
        list.add_at_start(v);
    }
    // Add 0 at start
    list.add_at_start(0);
    println!("Linked List after add at start: {}", list.to_string());
    // Access third item (index 2)
    if let Some(val) = list.get_nth(2) {
        println!("Linked List third item: {}", val);
    } else {
        println!("Linked List third item: None");
    }
}

array.insert(0, 0);

Shift all elements right to add at start in array

println!("Array third item: {}", array[2]);

Direct access to third item by index in array

list.add_at_start(v);

Add new node at start by pointing to old head in linked list

list.add_at_start(0);

Add 0 at start of linked list by changing head pointer

list.get_nth(2)

Traverse linked list nodes to find third item

Output

Array after add at start: [0, 1, 2, 3, 4, 5]

Array third item: 2

Linked List after add at start: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Linked List third item: 2

Complexity Analysis

Time: O(n) for adding at start in array because all elements shift; O(1) for linked list add at start because only pointer changes; O(1) for array access by index; O(n) for linked list access by position because traversal needed

Space: O(n) for both because they store n elements; linked list uses extra space for pointers

vs Alternative: Arrays are faster for random access but slower for insertions/deletions at start; linked lists are faster for insertions/deletions but slower for random access

Edge Cases

Empty array or linked list

Adding at start works normally; accessing any index returns None or error

DSA Rust

if let Some(val) = list.get_nth(2) { ... }

Accessing index out of bounds

Array panics if out of bounds; linked list returns None safely

DSA Rust

while let Some(node) = current { ... }

Single element list or array

Add at start still works; access index 0 returns the element

DSA Rust

array.insert(0, 0); and list.add_at_start(0);

When to Use This Pattern

When a problem needs fast random access, think array; when frequent insertions or deletions at start or middle are needed, think linked list.

Common Mistakes

Mistake: Trying to access linked list elements by index directly like an array
Fix: Traverse nodes step by step to reach the desired position

Mistake: Inserting at start of array without shifting elements
Fix: Use array insert method or shift elements manually

Summary

Arrays store items in order with fast access but slow insertions at start.

Use arrays when you need quick access by position and fewer insertions/deletions.

Linked lists let you add or remove items quickly by changing pointers but require walking through nodes to find items.

Practice

1. Which data structure is better when you need fast random access to elements by index?

easy

A. Queue

B. Array

C. Stack

D. Linked List

Solution

1. Step 1: Understand random access in arrays

   Arrays store elements in contiguous memory, so accessing any element by index is fast and direct.

2. Step 2: Compare with linked lists

   Linked lists require traversal from the head to reach an element, making random access slower.

3. Final Answer:

   Array -> Option B

4. Quick Check:

   Random access = Array [OK]

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

Common Mistakes:

• Thinking linked lists allow fast random access
• Confusing stacks or queues with arrays
• Assuming linked lists store elements contiguously

2. Which of the following is the correct Rust syntax to declare a mutable vector (dynamic array)?

easy

A. let mut v = vec[];

B. let v = Vec::new();

C. let mut v = Vec::new();

D. let v mut = Vec::new();

Solution

1. Step 1: Identify correct mutable vector declaration

   In Rust, 'let mut v = Vec::new();' declares a mutable vector named v.

2. Step 2: Check other options for syntax errors

   let v = Vec::new(); is immutable vector, C has wrong vec syntax, D has incorrect keyword order.

3. Final Answer:

   let mut v = Vec::new(); -> Option C

4. Quick Check:

   Mutable vector syntax = let mut v = Vec::new(); [OK]

Hint: Use 'let mut' before variable for mutability [OK]

Common Mistakes:

• Forgetting 'mut' for mutable vectors
• Using incorrect vec macro syntax
• Placing 'mut' after variable name

3. Consider this Rust code using a linked list from the standard library:

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.push_back(10);
list.push_back(20);
list.push_front(5);

let first = list.pop_front();
println!("{:?}", first);
println!("{:?}", list);

What is the printed output?

medium

A. Some(5)
[10, 20]

B. Some(10)
[5, 20]

C. None
[5, 10, 20]

D. Some(5)
[5, 10, 20]

Solution

1. Step 1: Trace list operations

   Initially empty list. push_back(10) -> [10], push_back(20) -> [10, 20], push_front(5) -> [5, 10, 20].

2. Step 2: pop_front() removes and returns first element

   pop_front() returns Some(5), list becomes [10, 20].

3. Final Answer:

   Some(5) [10, 20] -> Option A

4. Quick Check:

   pop_front returns first element = Some(5) [OK]

Hint: pop_front removes first element from linked list [OK]

Common Mistakes:

• Confusing push_front and push_back order
• Expecting pop_front to return None
• Misreading list contents after operations

4. The following Rust code tries to remove an element from a linked list but causes a compile error:

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);
let removed = list.remove(0);

What is the main reason for the error?

medium

A. LinkedList in Rust does not have a remove method with index parameter

B. You cannot push_back elements into a LinkedList

C. The list must be immutable to remove elements

D. The remove method requires a mutable reference to the element

Solution

1. Step 1: Check LinkedList API in Rust

   Rust's std::collections::LinkedList does not provide a remove method that takes an index.

2. Step 2: Understand error cause

   Trying to call remove(0) causes compile error because such method does not exist.

3. Final Answer:

   LinkedList in Rust does not have a remove method with index parameter -> Option A

4. Quick Check:

   LinkedList remove by index = no method [OK]

Hint: Rust LinkedList lacks remove by index method [OK]

Common Mistakes:

• Assuming LinkedList supports remove by index
• Confusing mutability rules
• Thinking push_back is invalid

5. You need to store a large collection of elements where insertions and deletions happen frequently at both ends, but you also need to access elements by index occasionally. Which data structure is the best choice in Rust?

hard

A. LinkedList

B. HashMap

C. Vec (Array)

D. VecDeque

Solution

1. Step 1: Analyze requirements for insertions/deletions at both ends

   LinkedList and VecDeque both support fast insertions/removals at front and back.

2. Step 2: Consider occasional index access

   LinkedList has slow index access (O(n)), VecDeque supports efficient indexing (O(1) amortized).

3. Step 3: Compare Vec and HashMap

   Vec has slow front insertions, HashMap is for key-value, not ordered sequence.

4. Final Answer:

   VecDeque -> Option D

5. Quick Check:

   Fast ends + index access = VecDeque [OK]

Hint: Use VecDeque for fast ends and index access [OK]

Common Mistakes:

• Choosing LinkedList despite slow index access
• Choosing Vec despite slow front insertions
• Confusing HashMap with sequence structures