Linked Lists in Rust

About This Module

This module explores linked list data structures in Rust, covering both the theoretical concepts and practical implementation challenges. Students will learn about different types of linked lists (singly and doubly linked), understand their computational complexity, and discover why implementing linked lists in Rust requires careful consideration of ownership rules. The module compares various implementation approaches and discusses when to use linked lists versus other data structures.

Prework

Before this lecture, please read:

Pre-lecture Reflections

  1. Why can't you implement a recursive data structure directly in Rust without using Box<T>?
  2. What are the memory layout differences between arrays and linked lists?
  3. How do ownership rules affect pointer-based data structures in Rust?

Learning Objectives

By the end of this lecture, you should be able to:

  • Understand the structure and operations of linked lists
  • Analyze the computational complexity of linked list operations
  • Implement basic linked lists in Rust using Box<T> and proper ownership patterns
  • Compare the performance characteristics of different linked list variants
  • Choose appropriate data structures based on access patterns and performance requirements

What is a linked list?

  • A recursive data structure
  • Simplest version is a single pointer (head) that points to the first element in the list
  • Each list element contains some data and a pointer to the next element in the list
  • A special pointer value (None) used to indicate the end of the list
  • If first == None then the list is empty

An implementation using Box (Optional)

This is optional, but here is an example of how to implement a linked list using Box<T>.

Box<T> is a smart pointer that allocates data on the heap. See the Rust Language Book for more details.

//===============================
// Node struct and method
//===============================

// Define a node that contains a value and a pointer to the next node.
#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

// Implement a new method for the node.
impl<T> Node<T> {
    fn new(value: T) -> Self {
        Node { value, next: None }
    }
}

//===============================
// List struct and methods
//===============================

// Then to implement a linked list, we need to define a type that contains a pointer to the first node.

#[derive(Debug)]
struct List<T> {
    head: Option<Box<Node<T>>>,
}

// Then we can implement methods to add and remove nodes from the list.

impl<T> List<T> {
    fn new() -> Self {
        List { head: None }
    }

    fn push(&mut self, value: T) {
        let mut new_node = Box::new(Node::new(value));
        new_node.next = self.head.take();
        self.head = Some(new_node);
    }

    // There's a lot packed into this function, but at a high level, it takes
    // the node that the head points to, replaces head with the next node and
    // drops what the head previously pointed to.
    fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.value
        })
    }
}

//Then we can use the list to add and remove nodes.

fn main() {
    let mut list = List::<&str>::new();
    println!("{:?}", list);

    list.push("Charlie");
    println!("{:?}", list);

    list.push("Bob");
    println!("{:?}", list);

    list.push("Alice");
    println!("{:?}", list);

    println!("{:?}", list.pop());
    println!("{:?}", list.pop());
    println!("{:?}", list.pop());
    println!("{:?}", list.pop());
}

Inserting and Removing from the beginning of the list

Assume you have a new list element "John". How do you add it to the list?

new "John"
"John".next = *head
head = "John"

How about getting an element out of the list?

item = head
head = item.next
item.next = None
return item

Common optimization for lists

  • Doubly linked list
  • Tail pointer


Cost of list operations

  • Insert to Front: (SLL O(1), DLL O(1))
  • Remove from Front (SLL O(1), DLL O(1))
  • Insert to Back (SLL O(N), DLL O(1))
  • Remove from Back (SLL O(N), DLL O(1))
  • Insert to Middle (SLL O(N), DLL O(N))
  • Remove from Middle (SLL O(N), DLL O(N))

Rust's LinkedList

Rust provides a doubly-linked list in the standard library.

use std::collections::LinkedList;

fn main() {
  let mut list = LinkedList::from(["Alice", "Bob", "Charlie"]);
  println!("{:?}", list);
  list.push_front("John");
  println!("{:?}", list);
  list.push_back("Donna");
  println!("{:?}", list);
  list.pop_front();
  println!("{:?}", list);
  list.pop_back();
  println!("{:?}", list);
}

Summary of Useful LinkedList Methods

  • push_front(value): Adds a value to the front of the list.
  • push_back(value): Adds a value to the back of the list.
  • pop_front(): Removes and returns the value from the front of the list.
  • pop_back(): Removes and returns the value from the back of the list.
  • front(): Returns a reference to the value at the front of the list.
  • back(): Returns a reference to the value at the back of the list.
  • len(): Returns the number of elements in the list.
  • is_empty(): Returns true if the list is empty, false otherwise.
  • clear(): Removes all elements from the list.
  • drain(): Returns an iterator that removes all elements and yields them. The list becomes empty after this operation.

See the documentation for more details.

Don't use LinkedList!

Warning from the Rust documentation on LinkedList:

NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache.

We'll see VecDeque in a later lecture.

Moving on...

In-Class Poll

True or False:

  1. In a singly linked list, inserting a new element at the front is an O(1) operation.
  2. A linked list stores its elements in contiguous memory locations, just like a Vec.
  3. Accessing the element at an arbitrary index i in a linked list is O(1), the same as indexing into an array or Vec.
  4. Removing an element from the back of a singly linked list is O(1), but O(N) for a doubly linked list.
  5. The Rust standard library's LinkedList is a doubly-linked list, but the documentation recommends using Vec or VecDeque in most cases.

Recap

  • Linked lists are a recursive data structure
  • They are not contiguous in memory, and poor processor cache utilization
  • Simple to access the beginning or end