Module dlist 

Available on crate feature dlist only.

An intrusive doubly linked list implementation.

This module provides DLinkedList, a doubly linked list where elements embed the list nodes themselves. This design offers memory efficiency and explicit control over allocation, suitable for scenarios like building LRU caches directly within data structures.

Features

• O(1) push and pop from both front and back.
• Generic over pointer types (Box, Arc, NonNull, raw pointers).
• Supports multiple lists for the same item via Tag.

Example

use embed_collections::{dlist::{DLinkedList, DListItem, DListNode}, Pointer};
use std::cell::UnsafeCell;

struct MyItem {
    id: u32,
    data: String,
    node: UnsafeCell<DListNode<MyItem, ()>>, // Node embedded directly
}

impl MyItem {
    fn new(id: u32, data: &str) -> Self {
        MyItem {
            id,
            data: data.to_string(),
            node: UnsafeCell::new(DListNode::default()),
        }
    }
}

// Safety: Implementors must ensure `get_node` returns a valid reference
// to the embedded `DListNode`. `UnsafeCell` is used for interior mutability.
unsafe impl DListItem<()> for MyItem {
    fn get_node(&self) -> &mut DListNode<Self, ()> {
        unsafe { &mut *self.node.get() }
    }
}

let mut list = DLinkedList::<Box<MyItem>, ()>::new();

list.push_back(Box::new(MyItem::new(1, "First")));
list.push_front(Box::new(MyItem::new(2, "Second")));
list.push_back(Box::new(MyItem::new(3, "Third")));

assert_eq!(list.len(), 3);

// List order: (2, "Second") <-> (1, "First") <-> (3, "Third")
assert_eq!(list.pop_front().unwrap().id, 2);
assert_eq!(list.pop_back().unwrap().id, 3);
assert_eq!(list.pop_front().unwrap().id, 1);
assert!(list.is_empty());

Structs

DLinkedList

An intrusive doubly linked list.

DLinkedListDrainer

DLinkedListIterator

DListNode

The node structure that must be embedded in items to be stored in a DLinkedList.

Traits

DListItem

A trait to return internal mutable DListNode for specified list.