Expand description
A doubly-linked list implementation over raw pointers
§About
Even in 2025 you still hear stories about coding interviews that involve linked lists despite the fact that the world has mostly moved on from them. Most programs opt instead to use contiguous storage structures that take advantage of cache locality and minimal allocations despite some hard coping with amortized O(1) “add” operations. So why do linked lists remain? What gives these simple structures such rich lore? The reality is that its probably just a simple litmus test to ensure you were awake in your CS courses. Linked lists are traditionally introduced early on in CS programs because they provide a good introduction to the foundational concepts required to build more complex structures, such as managing references (and/or pointers) correctly (and soundly in languages that use pointers).
Rust takes a notoriously different approach to pointers and memory safety from languages like C/C++ which can make otherwise simple pointer-based structures unusually difficult for Rust novices. Singly-linked lists are easy to build with safe, beginner-friendly Rust code because each node only requires a single reference in an adjacent node. Using the Box type to create pointers in singly-linked lists neatly follows Rust’s “one mutable reference or many immutable references” borrowing rules. It’s in doubly-linked lists where you have to start keeping multiple mutable references to an object where things get necessarily tricky.
One option for safe code is to use smart pointers like RefCell that provide interior mutability. You may even choose to wrap it in a Rc type for multiple ownership, but this approach gets unwieldy fast and requires runtime checks which may incur undesirable performance hits[1].
Pragmatically speaking, the humble linked list only really excels in situations where you need lots of list alterations (think splices and splits), so you want a structure that is as performant as possible. The natural conclusion is that you must dip into the shadows of unsafe Rust with either *mut T or NonNull pointers to get those blazingly fast… linked lists.
This module attempts to illustrate the delicate operations necessary to safely manage multiple sets of raw, unsafe pointers in Rust. Your friends all told you this was a bad idea, but I made the sacrifice to find out why so you don’t have to.
[1] See the chapter on Rc<RefCell<T>> in the famous Learning Rust With Entirely Too Many Linked Lists book for details.
§Design
The module consists of two primary structs; LinkedList and CursorMut. The list works by storing and managing pointer-based links to (private) Node structs. The LinkedList struct itself contains links to the list’s head and its tail, and stores the list’s length, which is simply the number of nodes that make up the list. You do not operate on nodes directly, but rather through list and cursor operations. Each node contains data, a link to the previous node, and a link to the next node. An empty list contains no nodes, but as soon as you add a single node, that node becomes the list’s head and tail node. Because each node contains links to previous and next nodes, a list with a single node effectively contains two “ghost” (sentinel) nodes in front of and behind the single list node.
None <- A -> NoneThe “ghost” nodes dont have any data or any links, which provides a natural stopping point for attempts to move beyond the head or tail of the list. You can remove or replace the head and tail nodes, but you cannot define what lays beyond until you get there. 👻 Ultimately, this is an overly poetic and long-winded way to say that the list does not wrap or provide circular buffering.
The list takes on a more familiar shape once you start adding nodes.
None <- A <-> B <-> C -> None§The LinkedList Struct
The LinkedList struct contains methods for basic list operations. These operations allow you to use
the list as an unsorted linked list, a stack, or a queue with insert and remove operations
on both the front and tail of the list in O(1) time.
use dsa_rust::sequences::doubly_linked_list::LinkedList;
let mut list = LinkedList::new();
list.push_tail("a");
list.push_tail("b");
list.push_tail("c");
print!("First: [");
let mut i = 0;
for e in list.iter() {
print!("{e}");
if i == list.len() - 1 {
print!("]");
} else {
print!(", ");
}
i += 1;
}§The CursorMut Struct
Rob Pike has famously claimed to have never written a program with cursors. Unfortunately for me, I’m not as clever as Rob Pike, so this module’s second major struct is CursorMut. This mutable cursor type adds positional functionality to the list and contains functions for splitting and splicing lists, and range operations.
use dsa_rust::sequences::doubly_linked_list::LinkedList;
// First list
let mut first = LinkedList::new();
first.push_tail("a");
first.push_tail("b");
first.push_tail("c");
assert_eq!(first.peek_head(), Some(&"a"));
assert_eq!(first.peek_tail(), Some(&"c"));
// Second list
let mut second = LinkedList::new();
second.push_tail("1");
second.push_tail("2");
second.push_tail("3");
second.push_tail("4");
assert_eq!(second.peek_head(), Some(&"1"));
assert_eq!(second.peek_tail(), Some(&"4"));
// Spliced
// Postcondition: [1, 2, a, b, c, 3, 4]
let mut cur = second.cursor_mut();
cur.move_next(); // 0
cur.move_next(); // 1
cur.splice_after(first);
assert_eq!(second.peek_head(), Some(&"1"));
assert_eq!(second.peek_tail(), Some(&"4"));
eprint!("All together now: [");
for (i, e) in second.iter().enumerate() {
eprint!("{e}");
if i == second.len() - 1 {
eprintln!("]");
} else {
eprint!(", ");
}
}
// Range split
// Postcondition: [1, 2] [a, b, c, 3, 4]
let mut cur = second.cursor_mut();
cur.move_next(); // 0
cur.move_next(); // 1
let mut new_list = cur.split_after(); // splits after "2"
assert_eq!(new_list.peek_head(), Some(&"a"));
assert_eq!(new_list.peek_tail(), Some(&"4"));
// Postcondition: [1, 2] [a, b, c] [3, 4]
let mut new_cur = new_list.cursor_mut();
new_cur.move_next(); // 0
new_cur.move_next(); // 1
new_cur.move_next(); // 2
let new_back = new_cur.split_after(); // splits again after "c"
// Reassembles the two numbered lists
// Postcondition: [1, 2, 3, 4] [a, b, c]
cur.splice_after(new_back);
drop(cur);
// Makes sure everything is as it seems
assert_eq!(new_list.peek_head(), Some(&"a"));
assert_eq!(new_list.peek_tail(), Some(&"c"));
assert_eq!(second.peek_head(), Some(&"1"));
assert_eq!(second.peek_tail(), Some(&"4"));
// Prints everything, in case you're a visual learner like me
eprint!("Split numbers: [");
for (i, e) in second.iter().enumerate() {
eprint!("{e}");
if i == second.len() - 1 {
eprintln!("]");
} else {
eprint!(", ");
}
}
eprint!("Split letters: [");
for (i, e) in new_list.iter().enumerate() {
eprint!("{e}");
if i == new_list.len() - 1 {
eprintln!("]");
} else {
eprint!(", ");
}
}
//panic!("Uncomment to show me them beautiful lists");Structs§
- Cursor
Mut - About
- Iter
- Linked
List - About