Accessing and Traversing a Linked List

Since a linked list is not stored in contiguous memory, we cannot access a node by index directly like an array. Instead, we have to traverse the list by starting at the head and following the pointers one by one.

Access by Index

Getting a node at a specific index means walking through the list until we reach that position.

Finding a specific node at position N takes O(n) since worse case scenario, we have to through every node.

In C

// Returns a pointer to the node at the given index or NULL if out of bounds
Node *get_node(Node *head, int index) {
    Node *current = head;
    int i = 0;

    // Traverse the linked list from node to node
    while (current != NULL) {
        // If we've reached the target index, return the current node
        if (i == index) {
            return current;
        }

        // Move to the next node
        current = current->next;

        // Increment i
        i++;
    }

    // Index out of bounds
    return NULL;
}

// Usage
Node *node = get_node(head, 2);     // Get the third node (index 2)
if (node != NULL) {
    printf("%d\n", node->data);
}

while (current != NULL) loops as long as current isn't NULL.

if (i == index) checks if we've reached the target index. If so we return current, which is the pointer to the node at that index.

current = current->next is the line that let us traverse through the list. It reassigns the node we are currently in to the node after it. Essentially, we follow the pointer to the next node, moving one step forward through the list.

We return NULL if the index is out of bounds, so the caller must always check before using the result.

TIP

Alternatively, we could return -1 or some other sentinel value to indicate an error, but NULL is the standard way to represent "no node" in C.

WARNING

Forgetting to check for NULL before using the returned pointer and dereferencing it will crash the program with a segfault.

In Rust

rust

impl Node {
    fn get(head: &Option<Box<Node>>, index: usize) -> Option<&Node> {
        let mut current = head;
        let mut i = 0;

        // Traverse the linked list from node to node
        while let Some(node) = current {
            // If we've reached the target index, return the current node
            if i == index {
                return Some(node);
            }

            // Move to the next node
            current = &node.next;

            // Increment i
            i += 1;
        }

        // Index out of bounds
        None
    }
}

// Usage
if let Some(node) = Node::get(&head, 2) {
    println!("{}", node.data);
}

while let Some(node) = current is Rust's way of writing while (current != NULL) in C, but it also automatically unwraps the Option<Box<Node>> and gives us access to the current node safely.

if (i == index) checks if we've reached the target index, just like in C. If so we return Some(node).

We return None if the index is out of bounds, but unlike C, the caller cannot use the result without checking it first.

TIP

In C, forgetting to check for NULL is an easy mistake that can crash our program at runtime. In Rust, Option forces us to handle the empty case, since the compiler won't let us ignore it.

Key Difference

	C	Rust
Traverse	`current = current->next`	`current = &node.next`
Out of bounds	Returns `NULL`	Returns `None`
Caller check	Manual `if (node != NULL)`	Forced by `Option`
Null dereference	Possible, crashes at runtime	Impossible
Complexity	O(n)	O(n)

Traverse and Print

Sometimes, usually for visualizing or debugging, we want to visit every node in order and print its value.

In C

// Prints all nodes in the list
void print_list(Node *head) {
    Node *current = head;

    // Walk through the entire list
    while (current != NULL) {
        // Print the current node's data
        printf("%d", current->data);

        // Add an arrow if there's a next node
        if (current->next != NULL) {
            printf(" -> ");
        }

        // Move to the next node
        current = current->next;
    }

    printf("\n");
}

// Usage
print_list(head);  // Output: 10 -> 20 -> 30

Just like before, current = current->next traverses the list, but this time, instead of stopping after reaching a certain index, we just traverse the entire list.

if (current->next != NULL) makes sure we don't print an arrow after the last node.

In Rust

rust

impl Node {
    fn print_list(head: &Option<Box<Node>>) {
        let mut current = head;

        // Walk through the entire list
        while let Some(node) = current {
            // Print the current node's data
            print!("{}", node.data);

            // Add an arrow if there's a next node
            if node.next.is_some() {
                print!(" -> ");
            }

            // Move to the next node
            current = &node.next;
        }

        println!();
    }
}

// Usage
Node::print_list(&head);  // Output: 10 -> 20 -> 30

The & in &Option<Box<Node>> means that instead of taking ownership, we just want to borrow or look at the values, not modify or consume them.

node.next.is_some() checks if there's another node. In C, it's the same as current->next != NULL.

What is is_some() and is_none()?

is_some() and is_none() are methods used to check whether an Option contains a value. is_some() returns true if the Option is Some(...) (has a value), while is_none() returns true if it is None (empty). These methods are useful when we only need to know whether a value exists, without accessing the value itself, and they help avoid unsafe operations like unwrap().

TIP

Notice we're using &head when calling print_list(). This borrows the list instead of moving it. After printing, we can still use head because we never took ownership, we only borrowed its value.

Key Difference

	C	Rust
Loop	`while (current != NULL)`	`while let Some(node) = current`
Next check	`current->next != NULL`	`node.next.is_some()`
Ownership	Works on a copy of the pointer	Borrows the list with `&`
Complexity	O(n)	O(n)

Traverse and Apply a Function

A more powerful use of traversal is applying a function to each node's data. For example, we might want to double every value, or mark certain nodes as "visited".

In C

// Apply a function to every node's data
void traverse_apply(Node *head, void (*func)(int *)) {
    Node *current = head;

    // Walk through the entire list
    while (current != NULL) {
        // Apply the function to the current node's data
        func(&current->data);

        // Move to the next node
        current = current->next;
    }
}

// Example function: double the value
void double_value(int *data) {
    *data *= 2;
}

// Usage
traverse_apply(head, double_value);  // All values doubled
print_list(head);  // Output: 20 -> 40 -> 60

void (*func)(int *) is a function pointer so that we can pass any function we want to apply to each node in the list (so long as it follows the same type).

The function receives an integer pointer to the data (int *), so it can modify the value directly in the node instead of making a local copy.

In Rust

rust

impl Node {
    fn traverse_apply<F>(head: &mut Option<Box<Node>>, mut func: F)
    where
        F: FnMut(&mut i32),
    {
        let mut current = head;

        // Walk through the entire list
        while let Some(node) = current {
            // Apply the function to the current node's data
            func(&mut node.data);

            // Move to the next node
            current = &mut node.next;
        }
    }
}

// Usage
Node::traverse_apply(&mut head, |data| *data *= 2);  // All values doubled
Node::print_list(&head);  // Output: 20 -> 40 -> 60

FnMut(&mut i32) is a generic function that simply accepts any function that takes a mutable reference to an i32 or integer.

|data| *data *= 2 is a closure (Rust's version of an anonymous function). This lets us write the logic inline without having to define a separate function. We could also pass a named function if we wanted.

&mut head is used because we're modifying the data inside the nodes.

TIP

Although we could just define a function beforehand and use it in the traversal directly, making the function a parameter means we can pass any function, like doubling values, incrementing counters, filtering, mapping, or even complex logic, so long as it matches the generic function type. This pattern makes traverse_apply much more flexible.

Key Difference

	C	Rust
Function type	Function pointer `void (func)(int )`	Generic with `FnMut(&mut i32)`
Syntax	`traverse_apply(head, double_value)`	`Node::traverse_apply(&mut head, \|data\| ...)`
Inline functions	Not available (need to define separately)	Closures allow inline logic
Complexity	O(n)	O(n)

Accessing and Traversing a Linked List ​

Access by Index ​

In C ​

In Rust ​

Key Difference ​

Traverse and Print ​

In C ​

In Rust ​

Key Difference ​

Traverse and Apply a Function ​

In C ​

In Rust ​

Key Difference ​

Accessing and Traversing a Linked List

Access by Index

In C

In Rust

Key Difference

Traverse and Print

In C

In Rust

Key Difference

Traverse and Apply a Function

In C

In Rust

Key Difference