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

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?

"John".next = first  
first = "John"

How about getting an element out of the list?

item = first  
first = item.next  
item.next = NULL  
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

#![allow(unused)]
fn main() {
use std::collections::LinkedList;

let mut list = LinkedList::from([1, 2, 3]);
println!("{:?}", list);
list.push_front(0);
println!("{:?}", list);
list.push_back(4);
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...

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