Building Singly Linked List in Rust

4 min readMay 13, 2023

I had never thought that working with linked data structure in Rust is a challenge.

In C language, building a singly linked list of following node is a very basic practice for the learners of the language. The pointer next links to the next element of the list. You can easily handle an element (inserting, removing, modifying or searching) with the pointer.

struct Node {
    int val;
    struct Node *next;
};

But things are totally different in Rust. It’s quite troublesome to work with the linked data structure due to the restriction of memory ownership.

After a good load of testing and googling, I finally worked out a workable way for linked data structure. In this article, I will show the example code of handling the singly linked list. Doubly linked list and binary tree should also work in the similar way.

Data Structure

Here comes my definition of the node of the list:

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

struct Node {
    val: u32,
    next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    pub fn new(val: u32, next: Option<Rc<RefCell<Node>>>) -> Self {
        Node { val, next }
    }
}

I use Rc and RefCell to contain the memory that is allocated from heap for a node.

Why do I use Rc? Because I need to access the node or even pass a node to another function as parameter, while I don’t want to consume it. With the Rc::clone() function I can use a “shadow” of a node easily.

Why do I use RefCell? Because RefCell provides borrow() and borrow_mut(), so I can read and write the node content easily.

Creating List

A vector of u32 is passed to the function singly_linked_list_create() for creating the list. Call singly_linked_list_insert() for each value of the vector to insert a node in the list in ascending order.

// Create a single linked list from a vector of u32
fn singly_linked_list_create(vals: Vec<u32>) -> Option<Rc<RefCell<Node>>> {
    // Create a head of the list.
    // Using an extra node increased the overhead of the algorithm, but can save you a lot of trouble.
    let list = Some(Rc::new(RefCell::new(Node::new(0, None))));

    // Insert each value to the list
    for val in vals {
        singly_linked_list_insert(list.clone(), val);
    }

    // Skp the head. Return the real elements of the list.
    list.unwrap().borrow().next.clone()
}

In the function for creating the list, I choose to create an extra node before the real first element of the list. Although it takes a piece of additional memory, this is worthy, believe me. Otherwise you need to write more code to handle the head of the list.

Inserting Node

The insertion function singly_linked_list_insert() is the critical part.

In the function, current and next are cursors to walk along the linked list. The most important things of the function is to:

Update both current and next cursors for searching a proper location
Modify the current cursor to insert a new node

// Create a Node to hold the value. Insert the node to the list in the order of ascending.
// After the insertion, the list is sorted.
fn singly_linked_list_insert(list: Option<Rc<RefCell<Node>>>, val: u32) {
    // Use a current and next "pointer" to move along the list
    let mut current = list.clone();
    let mut next = current.clone().map(|x| x.borrow().next.clone()).flatten();

    // Move to a location where:
    // * The "current" pointer holds a value less/equal than "val"
    // * The "next" pointer is None or holds a larger value than "val"
    // So the new node should be inserted between "current" and "next".
    while next.is_some() && next.clone().map(|x| x.borrow().val).unwrap() <= val {
        current = next.clone();
        next = current.clone().map(|x| x.borrow().next.clone()).flatten();
    }

    // Set the new node to the "next" field of current ptr, and move forward the current ptr
    match current.take() {
        Some(current_taken) => {
            current_taken.borrow_mut().next = Some(Rc::new(RefCell::new(Node::new(val, next))));
            // Critical!
            // After "current.take()", the content of "current" is taken away, now "current" is None.
            // Do not forget to set the taken content back after modifying it.
            current = current_taken.borrow().next.clone();
        }
        None => {
            panic!("impossible")
        }
    };
}

Accessing the content of Option is a little bit troublesome, but thanks to the map() and take() function of it.

To move the cursors, I need to read the value and next pointer of the node. Option::map() function helps.

To update the next field of the target node, I choose to use Option::take() which transfers the data from the Option. But don’t forget to assign the new node back to current. Because after calling the take() function, current became None, the chain is broken.

Traversing List

Based on the previous code, traversing the list is quite easy.

// Traverse the linked list and build a vector of values.
// The vector should be sorted.
fn singly_linked_list_traverse(list: Option<Rc<RefCell<Node>>>) -> Vec<u32> {
    let mut traverse = vec![];
    let mut current = list.clone();

    while current.is_some() {
        match current.take() {
            Some(current_taken) => {
                traverse.push(current_taken.borrow().val);
                current = current_taken.borrow().next.clone();
            }
            None => {}
        }
    }

    traverse
}

Testing

pub fn test() {
    let vals = vec![5, 4, 2, 1, 0, 3, 8, 9, 6, 7];
    let list = singly_linked_list_create(vals.clone());
    let traverse = singly_linked_list_traverse(list);
    assert_eq!(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9], traverse);
}