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

Concept Flow - Why Linked List Exists and What Problem It Solves

Start: Need to store items

↓

Use Array? Fixed size, costly resizing

No↓

Use Linked List

↓

Store nodes with data + pointer to next

↓

Add or remove nodes easily without shifting

↓

Flexible size, efficient insert/delete

↓

Problem solved: Dynamic data storage without resizing cost

Shows why linked lists are chosen over arrays to handle dynamic data with easy insertions and deletions.

Execution Sample

DSA Rust

Node1 -> Node2 -> Node3 -> null
Add Node4 at end
Node1 -> Node2 -> Node3 -> Node4 -> null

Shows a linked list growing by adding a new node at the end without shifting existing nodes.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with empty list	None	head = null	null
2	Add Node1	Node1	head -> Node1	Node1 -> null
3	Add Node2	Node1, Node2	Node1.next -> Node2	Node1 -> Node2 -> null
4	Add Node3	Node1, Node2, Node3	Node2.next -> Node3	Node1 -> Node2 -> Node3 -> null
5	Add Node4 at end	Node1, Node2, Node3, Node4	Node3.next -> Node4	Node1 -> Node2 -> Node3 -> Node4 -> null
6	Stop	4 nodes	No change	List ready with 4 nodes

💡 List built dynamically without resizing or shifting elements

Variable Tracker

Variable	Start	After 2	After 3	After 4	After 5	Final
head	null	Node1	Node1	Node1	Node1	Node1
Node1.next	null	null	Node2	Node2	Node2	Node2
Node2.next	null	null	null	Node3	Node3	Node3
Node3.next	null	null	null	null	Node4	Node4
Node4.next	null	null	null	null	null	null
List Size	0	1	2	3	4	4

Key Moments - 3 Insights

Why not use an array instead of a linked list?

Arrays have fixed size and resizing them requires copying all elements, which is costly. The execution_table shows how linked list nodes are added without shifting or resizing.

How does linked list allow easy insertion?

Each node points to the next, so adding a node just changes one pointer (Node3.next -> Node4 in step 5), no need to move other nodes.

What does 'null' mean at the end of the list?

'null' means the last node points to nothing, marking the list end. This is shown in the Visual State column in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does Node1.next point to?

A null

B Node3

C Node2

D Node4

💡 Hint

Check the Pointer Changes and Visual State columns at step 3

At which step does the list first contain 3 nodes?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the Nodes in List column to see when 3 nodes appear

If we tried to add a node in an array, what problem would we face compared to linked list?

A Need to shift elements or resize array

B Pointers would break

C Cannot add nodes at all

D List would become circular

💡 Hint

Refer to the concept_flow where arrays require resizing or shifting

Concept Snapshot

Linked List stores items as nodes with data and pointer to next.
Unlike arrays, linked lists grow dynamically without resizing.
Insertion and deletion only change pointers, no shifting needed.
Ends with null pointer marking list end.
Solves problem of fixed size and costly resizing in arrays.

Full Transcript

Linked lists exist to solve the problem of storing data dynamically without the fixed size limitation of arrays. Arrays need resizing and shifting elements when adding or removing items, which is costly. Linked lists store data in nodes where each node points to the next. Adding a node means changing one pointer, no shifting needed. The list ends when a node points to null. This makes linked lists flexible and efficient for dynamic data storage.

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