Crate circular_doubly_linked_list 

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.

Overview

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

• A data element
• A pointer to the next node
• A pointer to the previous node

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.

Features

• O(1) insertion and deletion at both ends
• O(1) access to front and back elements
• Safe API wrappers around unsafe core operations
• Iterator support (forward and backward)
• no_std compatible (with optional features)
• Comprehensive test coverage

Example Usage

use circular_doubly_linked_list::CircularDoublyLinkedList;

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
assert_eq!(list.front(), Some(&1));
assert_eq!(list.back(), Some(&5));

// Pop elements
assert_eq!(list.pop_front(), Some(1));
assert_eq!(list.pop_back(), Some(5));

Safety

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

• Use-after-free
• Double-free
• Data races
• Null pointer dereferences

Performance Characteristics

Operation	Time Complexity
push_front	O(1)
push_back	O(1)
pop_front	O(1)
pop_back	O(1)
front	O(1)
back	O(1)
insert	O(1)*
remove	O(1)*
len	O(1)
is_empty	O(1)

* With a valid cursor/iterator position

Structs

CircularDoublyLinkedList

A circular doubly linked list with explicit head and tail pointers.

IntoIter

An owning iterator over a CircularDoublyLinkedList.

Iter

An immutable iterator over a CircularDoublyLinkedList.

IterMut

A mutable iterator over a CircularDoublyLinkedList.