DoubleLinkedList

A Rust doubly-linked list implementation that doesn't suck. Built for real-world use with proper error handling and performance optimizations.

Installation

Add this to your Cargo.toml:

[dependencies]
double_linked_list = "0.1.1"

Or install from the command line:

cargo add double_linked_list

Why Another Linked List?

Vec is great for most things but terrible for frequent insertions/removals in the middle. This library gives you the best of both worlds - O(1) insertions anywhere with a cursor, plus a memory pool to reduce allocations.

Honestly, I mostly wanted to explore smart pointer(Rc, Cell, RefCell, OnceCell, LazyCell, Weak) mechanisms in Rust, so this was more of an intellectual exercise than trying to build something actually useful.

Features

• Actually fast (up to 1,270x faster than Vec for certain operations - benchmarks here)
• Proper error handling with Result<T, ListError> - no more panics
• Memory pool optimization for heavy workloads
• 50+ methods covering everything you'd expect
• Functional programming support (map, filter, reduce, etc.)
• Cursor system for efficient sequential operations
• Thread-safe ready (just wrap in Arc<Mutex<>>)
• Zero unsafe code

Quick Start

use double_linked_list::DoubleLinkedList;

let mut list = DoubleLinkedList::new();
list.push(1)?;
list.push(2)?;
list.push(3)?;

let mut pooled_list = DoubleLinkedList::with_capacity(64);
pooled_list.push(42)?;
println!("Pool stats: {:?}", pooled_list.pool_stats());

use std::sync::{Arc, Mutex};
let shared_list = Arc::new(Mutex::new(DoubleLinkedList::new()));

For performance comparisons and when to use this vs Vec, check out the benchmarks.

Documentation

Full API Documentation

API Reference

The API is pretty straightforward. Here's what you get:

Basic Operations

fn new() -> Self
fn with_capacity(pool_capacity: usize) -> Self
fn len(&self) -> usize
fn is_empty(&self) -> bool
fn clear(&mut self)
fn pool_stats(&self) -> Option<(usize, usize)>
fn add_capacity(&mut self, additional: usize)
fn set_capacity(&mut self, new_capacity: usize) -> Result<()>

Adding/Removing Items

fn push(&mut self, value: T) -> Result<usize>
fn push_back(&mut self, value: T) -> Result<usize>
fn push_front(&mut self, value: T) -> Result<usize>
fn pop(&mut self) -> Option<T>
fn pop_back(&mut self) -> Option<T>
fn pop_front(&mut self) -> Option<T>
fn insert_at_index(&mut self, index: usize, value: T) -> Result<()>
fn insert_many_at_index<I>(&mut self, index: usize, values: I) -> Result<usize>
fn insert_at_begin(&mut self, value: T) -> Result<()>
fn insert_at_end(&mut self, value: T) -> Result<()>
fn remove_at_index(&mut self, index: usize) -> Result<T>
fn remove_at_begin(&mut self) -> Result<T>
fn remove_at_end(&mut self) -> Result<T>
fn get_at_index(&self, index: usize) -> Result<T>
fn get_at_begin(&self) -> Option<T>
fn get_at_end(&self) -> Option<T>
fn first(&self) -> Option<T>
fn last(&self) -> Option<T>
fn front(&self) -> Option<T>
fn back(&self) -> Option<T>

Searching

fn contains(&self, value: &T) -> bool
fn includes(&self, value: &T) -> bool
fn find<F>(&self, predicate: F) -> Option<T>
fn find_index<F>(&self, predicate: F) -> Option<usize>
fn index_of(&self, value: &T) -> Option<usize>

Functional Programming

fn map<U, F>(&self, f: F) -> DoubleLinkedList<U>
fn filter<F>(&self, predicate: F) -> Self
fn reduce<U, F>(&self, f: F, initial: U) -> U
fn every<F>(&self, predicate: F) -> bool
fn any<F>(&self, predicate: F) -> bool
fn some<F>(&self, predicate: F) -> bool
fn for_each<F>(&self, f: F)

Other Useful Stuff

fn reverse(&mut self)
fn splice(&mut self, index: usize, delete_count: usize, items: Vec<T>) -> Result<Vec<T>>
fn sort(&mut self)
fn sort_by<F>(&mut self, compare: F)
fn is_sorted(&self) -> bool
fn is_sorted_by<F>(&self, compare: F) -> bool
fn dedup(&mut self)
fn dedup_by<F>(&mut self, same_bucket: F)
fn swap(&mut self, a: usize, b: usize) -> Result<()>
fn retain<F>(&mut self, predicate: F)
fn remove_item(&mut self, value: &T) -> bool
fn remove_all(&mut self, value: &T) -> usize
fn extend<I>(&mut self, iter: I)
fn append(&mut self, other: &mut Self)
fn split_off(&mut self, at: usize) -> Result<Self>
fn split_at(&mut self, mid: usize) -> Result<(Vec<T>, Vec<T>)>
fn to_vec(&self) -> Vec<T>
fn to_vec_reversed(&self) -> Vec<T>
fn from_slice(slice: &[T]) -> Self

Cursor System

The cursor is what makes this list fast for sequential operations. Think of it as a bookmark in the list:

fn move_cursor_at_begin(&mut self) -> Result<()>
fn move_cursor_at_end(&mut self) -> Result<()>
fn move_cursor_at_index(&mut self, index: usize) -> Result<()>
fn move_cursor_to_value(&mut self, value: &T) -> Result<()>
fn move_cursor_to_next(&mut self) -> Result<()>
fn move_cursor_to_previous(&mut self) -> Result<()>
fn get_cursor_index(&self) -> Option<usize>
fn cursor_position(&self) -> usize
fn cursor_is_at_begin(&self) -> bool
fn cursor_is_at_end(&self) -> bool
fn can_move_cursor_next(&self) -> bool
fn can_move_cursor_previous(&self) -> bool
fn insert_after_cursor(&mut self, value: T) -> Result<()>
fn insert_before_cursor(&mut self, value: T) -> Result<()>
fn remove_after_cursor(&mut self) -> Result<T>
fn remove_before_cursor(&mut self) -> Result<T>
fn get_at_cursor(&self) -> Option<T>
fn get_before_cursor(&self) -> Option<T>
fn get_cursor(&self) -> Cursor<T>
fn set_cursor(&mut self, cursor: Cursor<T>) -> Result<()>
fn reset_cursor(&mut self)
fn validate_cursor(&self) -> bool

Display & Debug

fn display(&self, separator: Option<&str>)
fn log(&self, separator: Option<&str>)
fn enable_debug(&mut self)
fn disable_debug(&mut self)
fn is_debug_enabled(&self) -> bool

Error Handling

No more panics. Operations that can fail return Result<T, ListError>:

match list.get_at_index(100) {
    Ok(value) => println!("Got: {}", value),
    Err(ListError::IndexOutOfBounds { index, length }) => {
        println!("Index {} is out of bounds (length: {})", index, length);
    },
    Err(ListError::EmptyList) => println!("List is empty"),
}

Memory Pool

If you're creating/destroying lots of nodes, use the memory pool:

let mut list = DoubleLinkedList::with_capacity(100);

if let Some((available, total)) = list.pool_stats() {
    println!("Pool: {}/{} nodes available", available, total);
}

Examples

Basic stuff

let mut list = DoubleLinkedList::new();

list.push(1)?;
list.push(2)?;
list.push(3)?;

assert_eq!(list.len(), 3);
assert_eq!(list.first(), Some(1));
assert_eq!(list.last(), Some(3));

let item = list.pop();
let front_item = list.pop_front();

Functional programming

let numbers: DoubleLinkedList<i32> = (1..=5).collect();

let doubled = numbers.map(|x| x * 2);
let evens = numbers.filter(|x| x % 2 == 0);
let sum = numbers.reduce(|acc, x| acc + x, 0);

assert!(numbers.every(|x| *x > 0));
assert!(numbers.any(|x| *x > 3));

Bulk insertions

let mut list: DoubleLinkedList<i32> = (1..=5).collect();

// Insert multiple values at once
let values = vec![100, 200, 300];
let inserted_count = list.insert_many_at_index(2, values)?;
println!("Inserted {} items", inserted_count);

// Works with any iterator
let more_values = (400..=500);
list.insert_many_at_index(0, more_values)?;

Cursor operations (the cool part)

let mut list: DoubleLinkedList<i32> = (1..=5).collect();

list.move_cursor_at_index(2)?;
list.insert_after_cursor(100)?;
list.move_cursor_to_next()?;
list.insert_after_cursor(200)?;

Thread safety

use std::sync::{Arc, Mutex};

let shared_list = Arc::new(Mutex::new(DoubleLinkedList::new()));

let list_clone = Arc::clone(&shared_list);
std::thread::spawn(move || {
    list_clone.lock().unwrap().push(42).unwrap();
});

Creating from iterators

let list: DoubleLinkedList<i32> = (1..=10).collect();

let vec = vec![1, 2, 3];
let list: DoubleLinkedList<i32> = vec.into_iter().collect();

Performance

Most operations are O(1) or O(n). Cursor operations are O(1) after positioning. The memory pool helps with allocation performance.

Check out BENCHMARKS.md for detailed comparisons with Vec and std::collections::LinkedList.

How it works

It's a circular doubly-linked list with a sentinel node. The cursor sits between nodes and lets you do O(1) insertions/removals at any position once you're there.

Root ↔ Node1 ↔ Node2 ↔ Node3 ↔ Root
                 ↑
               cursor

Based on my JavaScript version at touskar/doubly_linked_list, but with proper Rust error handling and memory management.

License

MIT