circular_doubly_linked_list 0.1.0

# 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](#overview)
2. [Features](#features)
3. [Installation](#installation)
4. [Quick Start](#quick-start)
5. [API Documentation](#api-documentation)
6. [Safety Guarantees](#safety-guarantees)
7. [Performance](#performance-characteristics)
8. [Use Cases](#use-cases)
9. [Testing](#testing)
10. [Contributing](#contributing)
11. [License](#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`:

```toml
[dependencies]
circular_doubly_linked_list = "0.1.0"
```

Or install via cargo:

```bash
cargo add circular_doubly_linked_list
```

## Quick Start

```rust
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

```rust
// 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

```rust
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

```rust
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

```rust
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

```rust
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

```rust
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

```rust
// 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:

| Issue | Prevention |
|-------|------------|
| **Use-after-free** | Nodes are only accessed while valid |
| **Double-free** | Each node is deallocated exactly once |
| **Data races** | Single-threaded design with no shared mutable state |
| **Null pointer dereferences** | All pointers are `NonNull` and validated |
| **Memory leaks** | `Drop` implementation ensures all nodes are freed |

### 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

| Operation | Time Complexity | Space Complexity |
|-----------|-----------------|------------------|
| `new()` | O(1) | O(1) |
| `push_front()` | O(1) | O(1) |
| `push_back()` | O(1) | O(1) |
| `pop_front()` | O(1) | O(1) |
| `pop_back()` | O(1) | O(1) |
| `front()` | O(1) | O(1) |
| `back()` | O(1) | O(1) |
| `insert_after()` | O(n) | O(1) |
| `remove_at()` | O(n) | O(1) |
| `len()` | O(1) | O(1) |
| `is_empty()` | O(1) | O(1) |
| `clear()` | O(n) | O(1) |
| `rotate_left()` | O(1) | O(1) |
| `rotate_right()` | O(1) | O(1) |

## Use Cases

### Queue (FIFO)

```rust
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)

```rust
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)

```rust
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

```rust
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:

```bash
# 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:

```bash
# Generate documentation
cargo doc

# Open in browser
cargo doc --open
```

Online documentation is available at [docs.rs](https://docs.rs/circular_doubly_linked_list).

## 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](LICENSE) file for details.

at your option.