Circular Doubly Linked List

A high-performance, memory-safe Circular Doubly Linked List implementation written in Rust. This crate provides a safe API wrapper around unsafe core operations, following patterns similar to Rust's standard library collections.

Table of Contents

1. Overview
2. Features
3. Installation
4. Quick Start
5. API Documentation
6. Safety Guarantees
7. Performance
8. Use Cases
9. Testing
10. Contributing
11. License

Overview

A circular doubly linked list is a data structure where each node contains:

• A data element of type T
• A pointer to the next node in the sequence
• A pointer to the previous node in the sequence

The list is "circular" because the last node points back to the first node, and the first node points back to the last node, forming a closed loop. This design enables O(1) access to both ends of the list and efficient rotation operations.

Features

• O(1) insertion and deletion at both front and back ends
• O(1) access to front and back elements via explicit head and tail pointers
• O(1) rotation operations (left and right)
• Safe API wrappers around unsafe core pointer operations
• Full iterator support (Iter, IterMut, IntoIter)
• Double-ended iteration support (DoubleEndedIterator)
• no_std compatible (does not require the Rust standard library)
• Comprehensive test coverage with edge case handling
• Implements standard traits (Clone, Debug, Extend, FromIterator, IntoIterator, Default)

📦 Installation

Add this to your Cargo.toml:

[dependencies]
circular_doubly_linked_list = "0.1.0"

Or install via cargo:

cargo add circular_doubly_linked_list

Quick Start

use circular_doubly_linked_list::CircularDoublyLinkedList;

fn main() {
    // Create a new list
    let mut list = CircularDoublyLinkedList::new();
    
    // Push elements to the front
    list.push_front(3);
    list.push_front(2);
    list.push_front(1);
    
    // Push elements to the back
    list.push_back(4);
    list.push_back(5);
    
    // Iterate through the list
    for item in list.iter() {
        println!("{}", item);
    }
    // Output: 1, 2, 3, 4, 5
    
    // Access front and back elements
    assert_eq!(list.front(), Some(&1));
    assert_eq!(list.back(), Some(&5));
    
    // Pop elements from both ends
    assert_eq!(list.pop_front(), Some(1));
    assert_eq!(list.pop_back(), Some(5));
    
    // Check current length
    assert_eq!(list.len(), 3);
}

API Documentation

Core Operations

Creation

// Create a new empty list
let list: CircularDoublyLinkedList<i32> = CircularDoublyLinkedList::new();

// Create with capacity hint (doesn't pre-allocate)
let list = CircularDoublyLinkedList::with_capacity(100);

// Create using Default trait
let list = CircularDoublyLinkedList::default();

Insertion

let mut list = CircularDoublyLinkedList::new();

// Push to front (O(1))
list.push_front(1);
list.push_front(2);

// Push to back (O(1))
list.push_back(3);
list.push_back(4);

// Insert at specific position (O(n))
list.insert_after(1, 100); // Insert 100 after position 1

Access

let mut list = CircularDoublyLinkedList::new();
list.push_back(10);
list.push_back(20);
list.push_back(30);

// Immutable access (O(1))
assert_eq!(list.front(), Some(&10));
assert_eq!(list.back(), Some(&30));

// Mutable access (O(1))
if let Some(front) = list.front_mut() {
    *front = 100;
}

if let Some(back) = list.back_mut() {
    *back = 300;
}

Removal

let mut list = CircularDoublyLinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);

// Pop from front (O(1))
assert_eq!(list.pop_front(), Some(1));

// Pop from back (O(1))
assert_eq!(list.pop_back(), Some(3));

// Remove at position (O(n))
assert_eq!(list.remove_at(0), Some(2));

// Remove from empty list
assert_eq!(list.pop_front(), None);

Rotation

let mut list = CircularDoublyLinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);

// Rotate left: [1, 2, 3] → [2, 3, 1]
list.rotate_left();

// Rotate right: [2, 3, 1] → [1, 2, 3]
list.rotate_right();

Iterator Support

let mut list = CircularDoublyLinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);

// Immutable iteration
for item in list.iter() {
    println!("{}", item);
}

// Mutable iteration
for item in list.iter_mut() {
    *item *= 2;
}

// Consuming iteration
for item in list.into_iter() {
    println!("{}", item);
}

// Reverse iteration
for item in list.iter().rev() {
    println!("{}", item);
}

// Iterator adapters
let sum: i32 = list.iter().filter(|&&x| x % 2 == 0).sum();
let vec: Vec<_> = list.iter().map(|&x| x * 2).collect();

Trait Implementations

// Clone
let list1 = CircularDoublyLinkedList::from_iter([1, 2, 3]);
let list2 = list1.clone();

// Debug
println!("{:?}", list1); // Output: [1, 2, 3]

// Extend
let mut list = CircularDoublyLinkedList::new();
list.extend(vec![1, 2, 3]);

// FromIterator / collect
let list: CircularDoublyLinkedList<i32> = (0..10).collect();

// IntoIterator
let vec: Vec<i32> = list.into_iter().collect();

Safety Guarantees

This implementation uses unsafe code internally for raw pointer manipulation. However, all public APIs are safe and enforce Rust's ownership and borrowing rules. The unsafe blocks are carefully audited to prevent:

Internal Invariants

The following invariants are maintained throughout the list's lifetime:

1. If the list is non-empty, both head and tail point to valid nodes
2. If the list is empty, both head and tail are None
3. If the list has one element, head == tail
4. If the list has multiple elements:
   • tail.next == head (circular forward link)
   • head.prev == tail (circular backward link)
5. The length field accurately reflects the number of nodes

Performance Characteristics

Use Cases

Queue (FIFO)

let mut queue = CircularDoublyLinkedList::new();

// Enqueue
queue.push_back("Task 1");
queue.push_back("Task 2");
queue.push_back("Task 3");

// Dequeue
while let Some(task) = queue.pop_front() {
    println!("Processing: {}", task);
}

Stack (LIFO)

let mut stack = CircularDoublyLinkedList::new();

// Push
stack.push_front("Page 1");
stack.push_front("Page 2");
stack.push_front("Page 3");

// Pop
while let Some(page) = stack.pop_front() {
    println!("Popped: {}", page);
}

Deque (Double-Ended Queue)

let mut deque = CircularDoublyLinkedList::new();

// Add from both ends
deque.push_front(0);
deque.push_back(1);
deque.push_front(-1);
deque.push_back(2);

// Remove from both ends
deque.pop_front();
deque.pop_back();

Circular Buffer

let mut buffer = CircularDoublyLinkedList::new();

// Initialize buffer
for i in 0..5 {
    buffer.push_back(i);
}

// Rotate through all positions
for _ in 0..5 {
    buffer.rotate_left();
    // Process current front element
    println!("Front: {:?}", buffer.front());
}

Testing

Run the test suite:

# Run all tests
cargo test

# Run with output
cargo test -- --nocapture

# Run specific test category
cargo test --test list_tests
cargo test --test iter_tests
cargo test --test integration_tests

Documentation

Generate and view the documentation locally:

# Generate documentation
cargo doc

# Open in browser
cargo doc --open

Online documentation is available at docs.rs.

Contributing

Contributions are welcome! Please follow these guidelines:

Reporting Issues

• Check existing issues before creating a new one
• Provide a clear description of the problem
• Include minimal reproducible examples when possible
• Specify your Rust version and platform

Submitting Pull Requests

1. Fork the repository
2. Create a feature branch (git checkout -b feature/amazing-feature)
3. Make your changes with comprehensive tests
4. Ensure all tests pass (cargo test)
5. Run clippy for linting (cargo clippy)
6. Format your code (cargo fmt)
7. Submit a pull request with a clear description

Code Style

• Follow Rust standard library conventions
• Document all public APIs with rustdoc comments
• Include examples in documentation
• Maintain test coverage for new features

License

This project is licensed under the MIT License - see the LICENSE file for details.

at your option.