Get Length of Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the length of the linked list after these insertions?

Consider a singly linked list where nodes are inserted at the head. What will be the length of the list after inserting the values 10, 20, and 30 in that order?

DSA Rust

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

struct LinkedList {
    head: Option<Box<Node>>,
}

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

    fn insert_at_head(&mut self, data: i32) {
        let new_node = Box::new(Node {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

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

fn main() {
    let mut list = LinkedList::new();
    list.insert_at_head(10);
    list.insert_at_head(20);
    list.insert_at_head(30);
    println!("Length: {}", list.length());
}

A Length: 2

B Length: 0

C Length: 1

D Length: 3

💡 Hint

Each insertion adds one node at the head, increasing the length by one.

The list starts empty. Each insert_at_head adds a new node at the front. After inserting 10, length is 1; after 20, length is 2; after 30, length is 3.

❓ Predict Output

intermediate

What is the output of length method on an empty linked list?

Given a newly created linked list with no nodes, what will be the output of calling the length method?

DSA Rust

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

struct LinkedList {
    head: Option<Box<Node>>,
}

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

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

fn main() {
    let list = LinkedList::new();
    println!("Length: {}", list.length());
}

A Length: -1

B Length: 0

C Length: None

D Length: 1

💡 Hint

An empty list has no nodes, so length should be zero.

The head is None, so the while loop never runs and count remains zero.

🔧 Debug

advanced

Why does this length method cause a compile error?

This Rust code for length method in linked list causes a compile error. What is the cause?

DSA Rust

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

A Cannot move out of borrowed content: self.head is borrowed but moved

B Missing semicolon after count += 1

C Type mismatch: current should be &Option<Box<Node>> not Option<Box<Node>>

D Infinite loop because current never changes

💡 Hint

In Rust, you cannot move ownership from a borrowed reference.

The code tries to move self.head out of &self, which is not allowed. Instead, it should borrow references to traverse.

🧠 Conceptual

advanced

What is the time complexity of the length method for a singly linked list?

Given a singly linked list with n nodes, what is the time complexity of a method that counts the number of nodes by traversing the list?

A O(1)

B O(log n)

C O(n)

D O(n^2)

💡 Hint

The method visits each node once.

The length method must check each node once, so it takes time proportional to n nodes.

❓ Predict Output

expert

What is the printed output after reversing the linked list and getting its length?

Given the linked list with nodes 1 -> 2 -> 3 -> null, after reversing it and then getting its length, what is the output?

DSA Rust

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

struct LinkedList {
    head: Option<Box<Node>>,
}

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

    fn insert_at_head(&mut self, data: i32) {
        let new_node = Box::new(Node {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    fn reverse(&mut self) {
        let mut prev = None;
        let mut current = self.head.take();
        while let Some(mut node) = current {
            let next = node.next.take();
            node.next = prev;
            prev = Some(node);
            current = next;
        }
        self.head = prev;
    }

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

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

fn main() {
    let mut list = LinkedList::new();
    list.insert_at_head(3);
    list.insert_at_head(2);
    list.insert_at_head(1);
    list.reverse();
    list.print_list();
    println!("Length: {}", list.length());
}

A

3 -> 2 -> 1 -> null
Length: 3

B

1 -> 2 -> 3 -> null
Length: 3

C

null
Length: 0

D

1 -> 2 -> 3 -> null
Length: 0

💡 Hint

Reversing the list changes the order of nodes, but length remains the same.

Initially list is 1 -> 2 -> 3 -> null. After reverse, it becomes 3 -> 2 -> 1 -> null. Length is still 3.

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