Get Length of Linked List in DSA Rust - Execution Trace

Concept Flow - Get Length of Linked List

Start at head node

↓

Is current node None?

Yes→Stop, length counted

No↓

Increment length count

↓

Move to next node

↩Back to check current node

Start from the head node, check if current node exists, count it, move to next, repeat until no more nodes.

Execution Sample

DSA Rust

fn get_length(head: &Option<Box<Node>>) -> usize {
    let mut count = 0;
    let mut current = head;
    while let Some(node) = current {
        count += 1;
        current = &node.next;
    }
    count
}

Counts how many nodes are in the linked list by moving from head to end.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start at head	1 -> 2 -> 3 -> null	current points to node 1	1 -> 2 -> 3 -> null
2	Check current node	1 -> 2 -> 3 -> null	current not None	1 -> 2 -> 3 -> null
3	Increment count	1 -> 2 -> 3 -> null	count = 1	1 -> 2 -> 3 -> null
4	Move to next node	1 -> 2 -> 3 -> null	current points to node 2	1 -> 2 -> 3 -> null
5	Check current node	1 -> 2 -> 3 -> null	current not None	1 -> 2 -> 3 -> null
6	Increment count	1 -> 2 -> 3 -> null	count = 2	1 -> 2 -> 3 -> null
7	Move to next node	1 -> 2 -> 3 -> null	current points to node 3	1 -> 2 -> 3 -> null
8	Check current node	1 -> 2 -> 3 -> null	current not None	1 -> 2 -> 3 -> null
9	Increment count	1 -> 2 -> 3 -> null	count = 3	1 -> 2 -> 3 -> null
10	Move to next node	1 -> 2 -> 3 -> null	current points to None	1 -> 2 -> 3 -> null
11	Check current node	1 -> 2 -> 3 -> null	current is None	1 -> 2 -> 3 -> null
12	Stop and return count	1 -> 2 -> 3 -> null	count = 3	1 -> 2 -> 3 -> null

💡 current becomes None, meaning end of list reached, stop counting

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
count	0	1	2	3	3
current	node 1	node 2	node 3	None	None

Key Moments - 3 Insights

Why do we check if current node is None before counting?

Because if current is None, it means we reached the end of the list and there are no more nodes to count. See execution_table step 11 where current is None and counting stops.

Why do we move current to next node after incrementing count?

We count the current node first, then move to the next node to continue counting. This order ensures no node is skipped. See execution_table steps 3 and 4.

What happens if the list is empty (head is None)?

The loop never runs because current is None at start, so count stays 0 and function returns 0 immediately. This is shown by the exit condition in step 11.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of count at step 6?

A 3

B 1

C 2

D 0

💡 Hint

Check the 'Increment count' operation at step 6 in execution_table.

At which step does current pointer become None?

A Step 12

B Step 10

C Step 4

D Step 1

💡 Hint

Look at 'Pointer Changes' column in execution_table to find when current points to None.

If the linked list had only one node, how many times would count increment?

A 1

B 0

C 2

D 3

💡 Hint

Refer to variable_tracker count values and how loop runs for each node.

Concept Snapshot

Get Length of Linked List:
- Start at head node
- While current node is not None:
  - Increment count
  - Move to next node
- Return count
Counts nodes by traversing list until end.

Full Transcript

To get the length of a linked list, we start at the head node and check if the current node exists. If it does, we add one to our count and move to the next node. We repeat this until we reach a node that is None, which means the end of the list. Then we return the count. This method ensures we count every node exactly once. If the list is empty, the count remains zero. The execution table shows each step, including pointer moves and count increments, helping visualize the process clearly.

Practice

1. What does the function to get the length of a linked list typically do?

easy

A. Counts the number of nodes by traversing from head to end

B. Returns the value of the first node

C. Deletes all nodes in the list

D. Finds the maximum value in the list

Solution

1. Step 1: Understand the linked list traversal

   The function starts at the head node and moves through each node one by one.

2. Step 2: Count each node visited

   For every node visited, the function increments a counter until it reaches the end (null).

3. Final Answer:

   Counts the number of nodes by traversing from head to end -> Option A

4. Quick Check:

   Length = number of nodes visited [OK]

Hint: Traverse and count nodes until null [OK]

Common Mistakes:

• Returning the value of the first node instead of count
• Not handling empty list (null head)
• Trying to count without traversal

2. Which Rust code snippet correctly initializes a linked list node with value 5 and next pointer None?

easy

A. let node = Node::new(5);

B. let node = Node(5, None);

C. let node = Node { value: 5, next: None };

D. let node = Node { value: 5 };

Solution

1. Step 1: Check struct initialization syntax

   Rust structs are initialized with field names and values inside braces.

2. Step 2: Match field names and order

   let node = Node { value: 5, next: None }; uses correct field names and syntax. Tuple syntax requires tuple struct definition. Node::new(5) assumes an impl with new method. Omitting next field causes compile error.

3. Final Answer:

   let node = Node { value: 5, next: None }; -> Option C

4. Quick Check:

   Struct init uses field: value pairs [OK]

Hint: Use struct field names with braces for initialization [OK]

Common Mistakes:

• Using tuple syntax for struct without tuple struct definition
• Missing field names in initialization
• Omitting required fields like next

3. What is the output of this Rust code that calculates the length of a linked list?

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

fn length(head: &Option) -> usize {
    let mut count = 0;
    let mut current = head;
    while let Some(node) = current {
        count += 1;
        current = &node.next;
    }
    count
}

fn main() {
    let node3 = Node { value: 3, next: None };
    let node2 = Node { value: 2, next: Some(Box::new(node3)) };
    let node1 = Node { value: 1, next: Some(Box::new(node2)) };
    let head = Some(Box::new(node1));
    println!("{}", length(&head));
}

medium

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Understand the linked list structure

   There are three nodes linked: node1 -> node2 -> node3 -> None.

2. Step 2: Trace the length function

   The function counts nodes by traversing from head. It visits node1, node2, and node3, incrementing count each time.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   3 nodes counted [OK]

Hint: Count nodes by following next pointers until None [OK]

Common Mistakes:

• Counting only head node
• Not dereferencing Option correctly
• Confusing Option with Box

4. Identify the error in this Rust function to get linked list length:

fn length(head: &Option) -> usize {
    let mut count = 0;
    let mut current = head;
    while current.is_some() {
        count += 1;
        current = current.unwrap().next;
    }
    count
}

medium

A. Using unwrap() on &Option causes a move error

B. Loop condition should be current.is_none()

C. Count should start at 1, not 0

D. Function should return i32, not usize

Solution

1. Step 1: Analyze unwrap usage on reference

   Calling unwrap() on &Option tries to move out of a borrowed reference, which is not allowed.

2. Step 2: Correct way to access next node

   Use pattern matching or while let Some(node) = current to borrow without moving.

3. Final Answer:

   Using unwrap() on &Option causes a move error -> Option A

4. Quick Check:

   unwrap() moves ownership, not allowed on references [OK]

Hint: Use pattern matching, avoid unwrap on references [OK]

Common Mistakes:

• Using unwrap() on borrowed Option causing move error
• Wrong loop condition logic
• Incorrect return type for length

5. Given a linked list where each node contains an integer, how would you modify the length function to count only nodes with even values?

fn length_even(head: &Option) -> usize {
    // Your code here
}

hard

A. Use recursion without checking node values

B. Traverse list, increment count only if node.value % 2 == 0

C. Return length() / 2 assuming half are even

D. Count all nodes, then subtract odd values count

Solution

1. Step 1: Traverse the linked list nodes

   Start from head and move through each node until None.

2. Step 2: Check each node's value for evenness

   Increment count only if node.value % 2 == 0 (even number).

3. Step 3: Return the count of even-valued nodes

   This gives the length of nodes with even values.

4. Final Answer:

   Traverse list, increment count only if node.value % 2 == 0 -> Option B

5. Quick Check:

   Count only even nodes by checking value % 2 == 0 [OK]

Hint: Count nodes while checking even condition [OK]

Common Mistakes:

• Counting all nodes without filtering
• Assuming half nodes are even without check
• Using recursion without base case