Why Linked List Exists and What Problem It Solves in DSA Rust - Why This Pattern

Mental Model

A linked list is a chain of nodes where each node points to the next, making it easy to add or remove items without shifting everything.

Analogy: Imagine a treasure hunt where each clue points to the next location. You don't need to rearrange all clues if you add or remove one; you just change the pointers.

head -> [1] -> [2] -> [3] -> null

Dry Run Walkthrough

Input: array: [1, 2, 3], insert 0 at start, then insert 4 at end

Goal: Show how linked list avoids shifting elements when inserting at start or end

Step 1: Start with array [1, 2, 3]

[1, 2, 3]

Why: This is the usual array where elements are stored in order

Step 2: Insert 0 at start of array by shifting all elements right

[0, 1, 2, 3]

Why: Array needs to move all elements to make space at start, which is slow

Step 3: Start with linked list 1 -> 2 -> 3 -> null

head -> [1] -> [2] -> [3] -> null

Why: Linked list stores elements as nodes connected by pointers

Step 4: Insert 0 at start by creating new node pointing to head

head -> [0] -> [1] -> [2] -> [3] -> null

Why: No shifting needed, just change head pointer to new node

Step 5: Insert 4 at end by linking new node after last node

head -> [0] -> [1] -> [2] -> [3] -> [4] -> null

Why: Add at end by changing last node's pointer, no shifting

Result:

head -> [0] -> [1] -> [2] -> [3] -> [4] -> null

Annotated Code

DSA Rust

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

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

#[derive(Debug)]
struct LinkedList {
    head: Option<Rc<RefCell<Node>>>,
}

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

    fn insert_at_start(&mut self, val: i32) {
        let new_node = Rc::new(RefCell::new(Node { value: val, next: self.head.clone() }));
        self.head = Some(new_node);
    }

    fn insert_at_end(&mut self, val: i32) {
        let new_node = Rc::new(RefCell::new(Node { value: val, next: None }));
        match &self.head {
            None => self.head = Some(new_node),
            Some(head) => {
                let mut current = head.clone();
                loop {
                    let next_opt = current.borrow().next.clone();
                    match next_opt {
                        None => {
                            current.borrow_mut().next = Some(new_node);
                            break;
                        }
                        Some(next_node) => current = next_node,
                    }
                }
            }
        }
    }

    fn print_list(&self) {
        let mut current_opt = self.head.clone();
        while let Some(current) = current_opt {
            print!("{} -> ", current.borrow().value);
            current_opt = current.borrow().next.clone();
        }
        println!("null");
    }
}

fn main() {
    // Start with empty linked list
    let mut list = LinkedList::new();

    // Insert 1, 2, 3 at end to simulate initial list
    list.insert_at_end(1);
    list.insert_at_end(2);
    list.insert_at_end(3);

    // Insert 0 at start
    list.insert_at_start(0);

    // Insert 4 at end
    list.insert_at_end(4);

    // Print final list
    list.print_list();
}

let new_node = Rc::new(RefCell::new(Node { value: val, next: self.head.clone() }));

create new node pointing to current head for insert at start

self.head = Some(new_node);

update head pointer to new node

let new_node = Rc::new(RefCell::new(Node { value: val, next: None }));

create new node with no next for insert at end

let mut current = head.clone();

start traversal from head to find last node

match next_opt { None => { current.borrow_mut().next = Some(new_node); break; } Some(next_node) => current = next_node, }

if next is None, link new node; else move to next node

while let Some(current) = current_opt { print!("{} -> ", current.borrow().value); current_opt = current.borrow().next.clone(); }

traverse and print all nodes until null

Output

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

Complexity Analysis

Time: O(n) for insert at end because we traverse all nodes to find the last; O(1) for insert at start because we just change head pointer

Space: O(n) because each element is stored as a node with pointers

vs Alternative: Compared to arrays, linked lists avoid shifting elements on insertions at start or middle, making those operations faster but use extra memory for pointers

Edge Cases

empty list

inserting at start or end sets head to new node without traversal

DSA Rust

match &self.head { None => self.head = Some(new_node),

single element list

insert at end links new node after the only node

DSA Rust

match next_opt { None => { current.borrow_mut().next = Some(new_node); break; }

When to Use This Pattern

When you see a problem where inserting or deleting elements frequently at the start or middle is slow due to shifting, reach for linked list because it uses pointers to avoid shifting.

Common Mistakes

Mistake: Trying to insert at start by shifting elements like an array
Fix: Change the head pointer to the new node instead of moving all nodes

Mistake: Not updating the last node's next pointer when inserting at end
Fix: Traverse to the last node and set its next pointer to the new node

Summary

Linked list stores elements as nodes connected by pointers to allow easy insertions and deletions.

Use linked lists when you need fast insertions or deletions without shifting elements.

The key insight is that changing pointers is cheaper than moving many elements.

Practice

1. Why do we use a linked list instead of an array in some cases?

easy

A. Because linked lists store elements in contiguous memory locations

B. Because linked lists use less memory than arrays always

C. Because linked lists allow easy insertion and deletion without shifting elements

D. Because linked lists are faster for accessing elements by index

Solution

1. Step 1: Understand array limitations and linked list advantages

   Arrays store elements in contiguous memory, so inserting or deleting in the middle requires shifting elements, which is slow. Linked lists store elements as nodes linked by pointers, so insertion and deletion can be done by changing pointers without shifting.

2. Final Answer:

   Because linked lists allow easy insertion and deletion without shifting elements -> Option C

3. Quick Check:

   Linked list insertion/deletion ease [OK]

Hint: Linked lists excel at insert/delete without shifting [OK]

Common Mistakes:

• Thinking linked lists use less memory always
• Believing linked lists store elements contiguously
• Assuming linked lists are faster for index access

2. Which of the following is the correct way to define a node struct for a singly linked list in Rust?

easy

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

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

C. struct Node { value: i32, next: &Node }

D. struct Node { value: i32, next: Node }

Solution

1. Step 1: Recall Rust ownership rules and Option usage

   Rust requires recursive types like linked lists to use indirection like Box to allocate on heap. The next pointer can be None if it's the last node, so Option is needed.

2. Final Answer:

   struct Node { value: i32, next: Option } -> Option B

3. Quick Check:

   Use Option for next pointer [OK]

Hint: Use Option for next pointer in Rust linked list [OK]

Common Mistakes:

• Using next: Node causes infinite size error
• Using references (&Node) without lifetime causes errors
• Omitting Option causes no way to mark list end

3. What will be the output of the following Rust code that creates a linked list with values 1, 2, 3 and prints them?

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

fn main() {
    let third = Node { value: 3, next: None };
    let second = Node { value: 2, next: Some(Box::new(third)) };
    let first = Node { value: 1, next: Some(Box::new(second)) };

    let mut current = &first;
    while let Some(ref next_node) = current.next {
        println!("{} ->", current.value);
        current = next_node;
    }
    println!("{} -> null", current.value);
}

medium

A. 1 -> 2 -> 3 -> null

B. 3 -> 2 -> 1 -> null

C. 1 -> 2 -> null

D. Compilation error due to ownership

Solution

1. Step 1: Trace linked list creation and printing loop

   Nodes are created in reverse order: third (3), second (2), first (1) linking to next. Loop prints current.value then moves to next node until next is None, printing 1, 2, 3 in order.

2. Final Answer:

   1 -> 2 -> 3 -> null -> Option A

3. Quick Check:

   Print order matches linked list order [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Confusing order and printing reversed
• Expecting compilation error due to ownership
• Stopping loop too early missing last node

4. The following Rust code tries to insert a new node with value 4 at the beginning of a linked list but causes a compilation error. What is the error?

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

fn main() {
    let mut first = Node { value: 1, next: None };
    let new_node = Node { value: 4, next: Some(Box::new(first)) };
    first = new_node;
}

medium

A. Borrow of moved value `first`

B. Cannot assign to `first` because it is not mutable

C. Recursive type has infinite size without Box

D. No error, code compiles fine

Solution

1. Step 1: Identify actual error

   `first` is declared mutable, so assignment should be allowed and Cannot assign to `first` because it is not mutable is incorrect. The error is `first` is moved into `Box::new(first)` when creating `new_node`, but then `first = new_node` tries to use `first` after the move, causing borrow of moved value.

2. Final Answer:

   Borrow of moved value `first` -> Option A

3. Quick Check:

   Ownership move error [OK]

Hint: Check ownership moves when assigning linked nodes [OK]

Common Mistakes:

• Confusing mutability error with ownership error
• Thinking code compiles fine
• Ignoring ownership rules in Rust

5. You want to implement a linked list in Rust that supports efficient insertion at the front and also allows traversing the list. Which of the following best explains why a linked list is preferred over a vector (array) for this use case?

hard

A. Linked lists store elements contiguously, making traversal faster than vectors

B. Vectors allow O(1) insertion at front but linked lists are simpler to implement

C. Vectors use pointers to link elements, so linked lists are redundant

D. Linked lists allow O(1) insertion at front without reallocating or shifting elements

Solution

1. Step 1: Analyze insertion and traversal complexities

   Vectors require shifting elements or reallocating memory for insertion at front, which is O(n). Linked lists insert at front by changing head pointer and new node's next pointer, which is O(1) without shifting. Traversal in linked lists is sequential via pointers; vectors have contiguous memory but insertion cost is higher at front.

2. Final Answer:

   Linked lists allow O(1) insertion at front without reallocating or shifting elements -> Option D

3. Quick Check:

   Insertion cost at front = O(1) linked list [OK]

Hint: Linked list front insertion is O(1), vector front insertion is O(n) [OK]

Common Mistakes:

• Thinking vectors insert at front in O(1)
• Believing linked lists store elements contiguously
• Confusing pointers in vectors with linked list nodes