Struct deepmesa_lists::linkedlist::list::LinkedList

pub struct LinkedList<T> { /* private fields */ }

A fast doubly linked list that owns the nodes and can pre-allocate memory for performance. This linked list allows pushing and popping elements at either end or in the middle in constant time.

The API is the same as std::collections::LinkedList however this list also allows pushing and popping elements from the middle of the list in constant time.

Getting Started

To get started add the deepmesa dependency to Cargo.toml and the use declaration in your source.

[dependencies]
deepmesa = "0.1.0"

use deepmesa::lists::LinkedList;

let mut list = LinkedList::<u8>::with_capacity(10);
for i in 0..10 {
    list.push_front(i);
}

for e in list.iter() {
    println!("{}", e);
}

Memory Management

This list manages memory via an internal freelist of nodes. When a new element is added to the list, a preallocated node is acquired from the freelist. When an element is removed from the list, the node is returned to the freelist. This ensures that memory is not allocated and deallocated on every push and pop which makes the list fast.

All memory for the list is allocated on the heap using the default allocator. Additional memory is allocated by the freelist when a new element is added to the list and the capacity is filled.

When the list is dropped, all memory is deallocated and any elements stored in the list are dropped. If the Drop trait on an element panics the list will deallocate all allocated memory because elements are removed from the list and dropped only after all memory is deallocated.

Capacity & Reallocation

The capacity of the list is the number of elements it can hold before allocating new memory. The length of the list is the number of elements it holds. When the length equals the capacity, and a new element is added to the list, the list will allocate additional memory.

The amount of memory allocated when the capacity is exhausted depends on how the list is constructed. If the list is constructed using new() or with_capacity() with a non-zero capacity then the capacity is doubled on every allocation.

If the list is constructed using with_capacity() with a capacity of zero, then the list will not preallocate any memory on construction. In this case, when a new element is added to the list, additional memory will be allocated for the new elememt unless the freelist has available memory from previous remove operations.

use deepmesa::lists::LinkedList;
// create a list with capacity 0
let mut list = LinkedList::<u8>::with_capacity(0);
assert_eq!(list.len(), 0);
assert_eq!(list.capacity(), 0);
// Pushing elements will cause an allocation every time
for i in 0..10 {
    assert_eq!(list.len(), i);
    assert_eq!(list.capacity(), i);
    list.push_head(1);
}

// Removing an element will not cause a deallocation
list.pop_head();
assert_eq!(list.len(), 9);
assert_eq!(list.capacity(), 10);

// Now that capacity exceeds the length of the list no memory will
// be allocated unless existing capacity is exhausted
list.push_head(1);
assert_eq!(list.len(), 10);
assert_eq!(list.capacity(), 10);

// any further additions to the list will again allocate new
// memory for each element added.
list.push_head(1);
assert_eq!(list.len(), 11);
assert_eq!(list.capacity(), 11);

It is recommended to use with_capacity() whenever possible and specify how big the list is expected to get.

Handles

The push_head(), push_tail() push_next() and push_prev() methods return handles to the nodes pushed to the linked list. The handles are implemented as structs of type (Node<T>)(Node) that wrap a raw pointer to node. However since Node<T> does not implement the Deref trait, these raw pointers cannot be dereferenced directly. Handles can only be used by passing them as arguments to the next(), next_mut(), prev(), prev_mut(), prev_node(), next_node(), node(), node_mut(), has_next(), has_prev(), pop_next(), pop_prev(), pop_node, push_next, push_prev(), allows adding, removing and mutating elements in the middle of the list in O(1) time.

Handles can be copied, cloned and passed around by value or reference without regard to the lifetime of the list. When an element is removed from the list, the handle associated with that node becomes invalid forever. Passing an invalid handle to the list is safe since all methods that accept a reference to a handle return None if the handle is invalid.

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
list.push_head(1);
let middle = list.push_head(100);
list.push_head(2);
// get the value of the node in the middle of the list in O(1)
// time.
assert_eq!(list.node(&middle), Some(&100));
// remove the middle node in O(1) time
list.pop_node(&middle);
// once the middle node is removed, the handle is invalid
assert_eq!(list.node(&middle), None);
assert_eq!(list.len(), 2);

Node<T> implements the Default trait so you can store default (invalid) handles in a struct and assign them later.

use deepmesa::lists::LinkedList;
use deepmesa::lists::linkedlist::Node;
struct MyStruct<T> {
    handle: Node<T>
};
let mut s = MyStruct::<u8> {
    handle: Node::<u8>::default()
};
let mut list = LinkedList::<u8>::with_capacity(10);
// The default handle is invalid
assert_eq!(list.node(&s.handle), None);
// push a new element and store the handle
s.handle = list.push_head(1);
assert_eq!(list.node(&s.handle), Some(&1));

Iterators

The list supports iterators that can traverse the list in either direction by reversing the iterator at any time.

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
for i in 0..10 {
    list.push_head(i);
}
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&9));
assert_eq!(iter.next(), Some(&8));
assert_eq!(iter.next(), Some(&7));
//now reverse the iterator
iter = iter.reverse();
assert_eq!(iter.next(), Some(&8));
assert_eq!(iter.next(), Some(&9));
assert_eq!(iter.next(), None);

Performance

Benchmarks against std::collections::LinkedList show a performance gain of almost 2x in push operations when memory is allocated upfront. Similar results are observed in pop operations as well.

Implementations

impl<T> LinkedList<T>

pub fn new() -> LinkedList<T>

Creates an empty linked list with a default capacity.

Examples

use deepmesa::lists::LinkedList;
let list = LinkedList::<u8>::new();

pub fn with_capacity(capacity: usize) -> LinkedList<T>

Creates an empty linked list with the specified capacity. The list will continue to reallocate additional memory by doubling the capacity everytime the capacity is exceeded.

However the list will not deallocate memory when elements are removed.

If the capacity is set to 0, and the list is full, then new memory will be allocated for one new element everytime an element is added to the list.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
for i in 0..10 {
    // All these are pushed without any allocations
    list.push_front(i);
}

assert_eq!(list.len(), 10);
assert_eq!(list.capacity(), 10);

// This will result in an allocation and the capacity will be doubled
list.push_front(1);
assert_eq!(list.len(), 11);
assert_eq!(list.capacity(), 20);

// A list with a capacity of 0 will allocate on every push
let mut list = LinkedList::<u8>::with_capacity(0);
list.push_front(1);
assert_eq!(list.len(), 1);
assert_eq!(list.capacity(), 1);

list.push_front(1);
assert_eq!(list.len(), 2);
assert_eq!(list.capacity(), 2);

pub fn iter(&self) -> Iter<'_, T>

Returns a bidirectional iterator over the list

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::new();
list.push_front(1);
list.push_front(2);
list.push_front(3);
list.push_front(4);
list.push_front(5);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&5));
assert_eq!(iter.next(), Some(&4));
assert_eq!(iter.next(), Some(&3));
iter = iter.reverse();
assert_eq!(iter.next(), Some(&4));
assert_eq!(iter.next(), Some(&5));
assert_eq!(iter.next(), None);

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Returns a bidirectional iterator over the list with mutable references that allows the value to be modified

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::new();
list.push_front(1);
list.push_front(2);
list.push_front(3);

for e in list.iter_mut() {
    *e += 100;
}

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&103));
assert_eq!(iter.next(), Some(&102));
assert_eq!(iter.next(), Some(&101));
assert_eq!(iter.next(), None);

pub fn clear(&mut self)

Removes and drops all the elements from this list. This has no effect on the allocated capacity of the list.

This method should complete in O(n) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
list.push_front(1);
list.push_front(2);
list.push_front(3);

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

list.clear();
assert_eq!(list.len(), 0);
assert_eq!(list.capacity(), 10);

pub fn front(&self) -> Option<&T>

Returns a reference to the front (head) of the list or None if the list is empty. This method simply calls self.head()

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.front(), None);

list.push_front(1);
assert_eq!(list.front(), Some(&1));

pub fn back(&self) -> Option<&T>

Returns a reference to the back (tail) of the list or None if the list is empty. This method simply calls self.tail()

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.back(), None);

list.push_back(1);
assert_eq!(list.back(), Some(&1));

pub fn front_mut(&mut self) -> Option<&mut T>

Returns a mutable reference to the front (head) of the list or None if the list is empty. This method simply calls self.head_mut()

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.front(), None);

list.push_front(1);
assert_eq!(list.front(), Some(&1));
match list.front_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(list.front(), Some(&5));

pub fn back_mut(&mut self) -> Option<&mut T>

Returns a mutable reference to the back (tail) of the list or None if the list is empty. This method simply calls self.tail_mut()

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.back(), None);

list.push_back(1);
assert_eq!(list.back(), Some(&1));
match list.back_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(list.back(), Some(&5));

pub fn tail(&self) -> Option<&T>

Returns a reference to the back (tail) of the list or None if the list is empty.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.tail(), None);

list.push_tail(1);
assert_eq!(list.tail(), Some(&1));

pub fn tail_mut(&mut self) -> Option<&mut T>

Returns a mutable reference to the back (tail) of the list or None if the list is empty.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.tail(), None);

list.push_tail(1);
assert_eq!(list.tail(), Some(&1));
match list.tail_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(list.tail(), Some(&5));

pub fn head(&self) -> Option<&T>

Returns a reference to the front (head) of the list or None if the list is empty.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.head(), None);

list.push_head(1);
assert_eq!(list.head(), Some(&1));

pub fn head_mut(&mut self) -> Option<&mut T>

Returns a mutable reference to the front (head) of the list or None if the list is empty.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.head(), None);

list.push_head(1);
assert_eq!(list.head(), Some(&1));
match list.head_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(list.head(), Some(&5));

pub fn next(&self, node: &Node<T>) -> Option<&T>

Returns a reference to the value of the node immediately after the node associated with the specified handle. If the specified handle is invalid or there is no next node, this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
list.push_head(1);
let node = list.push_head(2);

assert_eq!(list.next(&node), Some(&1));

list.pop_tail();
// once the tail is popped, there is no next
assert_eq!(list.next(&node), None);

pub fn next_mut(&mut self, node: &Node<T>) -> Option<&mut T>

Returns a mutable reference to the value of the node immediately after the node associated with the specified handle. If the specified handle is invalid or if there is no next node, this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
list.push_head(1);
let node = list.push_head(2);
assert_eq!(list.next(&node), Some(&1));

match list.next_mut(&node) {
    None => {},
    Some(x) => *x = 100,
}

assert_eq!(list.next(&node), Some(&100));

pub fn prev(&self, node: &Node<T>) -> Option<&T>

Returns a reference to the value of the node immediately preceeding the node associated with the specified handle. If the specified handle is invalid or if there is no preceeding node, this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node = list.push_head(1);
list.push_head(2);

assert_eq!(list.prev(&node), Some(&2));

list.pop_head();
// once the head is popped, there is no prev
assert_eq!(list.prev(&node), None);

pub fn prev_mut(&mut self, node: &Node<T>) -> Option<&mut T>

Returns a mutable reference to the value of the node immediately preceeding the node associated with the specified handle. If the specified handle is invalid or there is no preceeding node, this method returns None. This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node = list.push_head(1);
list.push_head(2);
assert_eq!(list.prev(&node), Some(&2));

match list.prev_mut(&node) {
    None => {},
    Some(x) => *x = 100,
}

assert_eq!(list.prev(&node), Some(&100));

pub fn prev_node(&self, node: &Node<T>) -> Option<Node<T>>

Returns a handle to the node immediately preceeding the node associated with the specified handle. If the specified handle is invalid or if there is no preceeding node, this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node = list.push_head(1);
list.push_head(2);

assert_eq!(list.prev(&node), Some(&2));

list.pop_head();
//once the head is popped there is no prev node
assert_eq!(list.prev(&node), None);

pub fn next_node(&self, node: &Node<T>) -> Option<Node<T>>

Returns a handle to the node immediately preceeding the node associated with the specified handle. If the handle is invalid or if there is no preceeding node, this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
list.push_head(1);
let node = list.push_head(2);

match list.next_node(&node) {
    None => {},
    Some(n) => assert_eq!(list.node(&n), Some(&1)),
}

list.pop_tail();
// Once the tail node is popped, there is no next node
assert_eq!(list.next_node(&node), None);

pub fn node(&self, node: &Node<T>) -> Option<&T>

Returns a reference to the value of the node associated with the specified handle. If the specified handle is invalid this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node = list.push_head(1);

assert_eq!(list.node(&node), Some(&1));

list.pop_head();
// once the node is popped the handle becomes invalid
assert_eq!(list.node(&node), None);

pub fn node_mut(&mut self, node: &Node<T>) -> Option<&mut T>

Returns a mutable reference to the value of the node associated with the specified handle. If the specified handle is invalid this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node = list.push_head(1);

assert_eq!(list.node(&node), Some(&1));

match list.node_mut(&node) {
    None => {},
    Some(x) => *x = 100,
}

assert_eq!(list.node(&node), Some(&100));

pub fn head_node(&self) -> Option<Node<T>>

Returns a handle to the head (front) of the list or None if the list is empty.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node = list.push_head(1);

match list.head_node() {
    None => {},
    Some(x) => assert_eq!(list.node(&x), Some(&1)),
}

list.pop_head();
assert_eq!(list.head_node(), None);

pub fn tail_node(&self) -> Option<Node<T>>

Returns a handle to the tail (back) of the list or None if the list is empty.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node = list.push_tail(1);

match list.tail_node() {
    None => {},
    Some(x) => assert_eq!(list.node(&x), Some(&1)),
}

list.pop_tail();
assert_eq!(list.tail_node(), None);

pub fn has_next(&self, node: &Node<T>) -> Option<bool>

Returns true if the node associated with the specified handle has a next node and false if it does not. If the specified handle is invalid this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node1 = list.push_head(1);
let node2 = list.push_head(2);

assert_eq!(list.has_next(&node1), Some(false));
assert_eq!(list.has_next(&node2), Some(true));

list.pop_head();
assert_eq!(list.has_next(&node1), Some(false));
// once the head is popped node2 becomes an invalid handle
assert_eq!(list.has_next(&node2), None);

pub fn has_prev(&self, node: &Node<T>) -> Option<bool>

Returns true if the node associated with the specified handle has a previous node and false if it does not. If the specified handle is invalid this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node1 = list.push_head(1);
let node2 = list.push_head(2);

assert_eq!(list.has_prev(&node1), Some(true));
assert_eq!(list.has_prev(&node2), Some(false));

list.pop_head();
assert_eq!(list.has_prev(&node1), Some(false));
// once the head is popped node2 becomes an invalid handle
assert_eq!(list.has_next(&node2), None);

pub fn is_empty(&self) -> bool

Returns true if the list is empty and false otherwise.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.is_empty(), true);

list.push_head(1);
assert_eq!(list.is_empty(), false);

pub fn has_head(&self) -> bool

Returns true if the list has a head node and false if the list is empty.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.has_head(), false);
list.push_head(1);
assert_eq!(list.has_head(), true);
list.pop_head();
assert_eq!(list.has_head(), false);

pub fn has_tail(&self) -> bool

Returns true if the list has a tail node and false if the list is empty.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.has_tail(), false);
list.push_tail(1);
assert_eq!(list.has_tail(), true);
list.pop_tail();
assert_eq!(list.has_tail(), false);

pub fn capacity(&self) -> usize

Returns the number of elements the list can hold before new memory is allocated.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.capacity(), 10);

pub fn len(&self) -> usize

Returns the number of elements in the list

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.len(), 0);

list.push_head(1);
assert_eq!(list.len(), 1);

pub fn push_front(&mut self, elem: T)

Adds an element to the front (head) of the list. This method simply calls self.push_head()

This operation should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
list.push_front(1);
assert_eq!(list.front(), Some(&1));

list.push_front(2);
assert_eq!(list.front(), Some(&2));

pub fn push_back(&mut self, elem: T)

Adds an element to the back (tail) of the list. This method simply calls self.push_tail()

This operation should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
list.push_back(1);
assert_eq!(list.back(), Some(&1));

list.push_back(2);
assert_eq!(list.back(), Some(&2));

pub fn pop_head(&mut self) -> Option<T>

Removes and returns the value at the head (front) of the list or None if the list is empty.

This operation should complete in O(1) time

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.pop_head(), None);

list.push_head(1);
list.push_head(2);
assert_eq!(list.pop_head(), Some(2));
assert_eq!(list.pop_head(), Some(1));
assert_eq!(list.pop_head(), None);

pub fn pop_tail(&mut self) -> Option<T>

Removes and returns the value at the tail (back) of the list or None if the list is empty.

This operation should complete in O(1) time

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.pop_tail(), None);

list.push_tail(1);
list.push_tail(2);
assert_eq!(list.pop_tail(), Some(2));
assert_eq!(list.pop_tail(), Some(1));
assert_eq!(list.pop_tail(), None);

pub fn pop_front(&mut self) -> Option<T>

Removes and returns the value at the front (head) of the list or None if the list is empty. This method simply calls self.pop_head()

This operation should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.pop_front(), None);

list.push_front(1);
list.push_front(2);
assert_eq!(list.pop_front(), Some(2));
assert_eq!(list.pop_front(), Some(1));
assert_eq!(list.pop_front(), None);

pub fn pop_back(&mut self) -> Option<T>

Removes and returns the value at the back (tail) of the list or None if the list is empty. This method simply calls self.pop_tail()

This operation should complete in O(1) time

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
assert_eq!(list.pop_back(), None);

list.push_back(1);
list.push_back(2);
assert_eq!(list.pop_back(), Some(2));
assert_eq!(list.pop_back(), Some(1));
assert_eq!(list.pop_back(), None);

pub fn pop_next(&mut self, node: &Node<T>) -> Option<T>

Removes and returns the value of the node immediately after the node associated with the specified handle. If the specified handle is invalid or there is no next node, then this method returns None.

This operation should complete in O(1) time

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);

list.push_head(1);
list.push_head(2);
let node = list.push_head(3);
assert_eq!(list.pop_next(&node), Some(2));
assert_eq!(list.pop_next(&node), Some(1));
assert_eq!(list.pop_next(&node), None);

pub fn pop_prev(&mut self, node: &Node<T>) -> Option<T>

Removes and returns the value of the node immediately preceeding the node associated with the specified handle. If the specified handle is invalid or there is no previous node, then this method returns None.

This operation should complete in O(1) time

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);

let node = list.push_head(1);
list.push_head(2);
list.push_head(3);
assert_eq!(list.pop_prev(&node), Some(2));
assert_eq!(list.pop_prev(&node), Some(3));
assert_eq!(list.pop_prev(&node), None);

pub fn pop_node(&mut self, node: &Node<T>) -> Option<T>

Removes and returns the value of the node associated with the specified handle. If the specified handle is invalid then this method returns None.

This operation should complete in O(1) time

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);

let node = list.push_head(1);
assert_eq!(list.pop_node(&node), Some(1));
assert_eq!(list.pop_node(&node), None);

pub fn push_head(&mut self, elem: T) -> Node<T>

Adds an element to the head (front) of the list and returns a handle to it.

This operation should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node = list.push_head(1);
assert_eq!(list.node(&node), Some(&1));

pub fn push_tail(&mut self, elem: T) -> Node<T>

Adds an element to the tail (back) of the list and returns a handle to it.

This operation should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
let node = list.push_tail(1);
assert_eq!(list.node(&node), Some(&1));

pub fn contains(&self, x: &T) -> bool

where T: PartialEq<T>,

Returns true if the LinkedList contains an element equal to the given value.

This operation should complete in O(n) time

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);

list.push_back(0);
list.push_back(1);
list.push_back(2);

assert_eq!(list.contains(&0), true);
assert_eq!(list.contains(&10), false);

pub fn push_next(&mut self, node: &Node<T>, elem: T) -> Option<Node<T>>

Adds an element immediately after the node associated with the specified handle. Returns the handle to the node thats been added or None if the specified handle is invalid.

This operation should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);

list.push_head(0);
let middle = list.push_head(1);
list.push_head(2);
list.push_next(&middle, 100);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&100));
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), None);

pub fn push_prev(&mut self, node: &Node<T>, elem: T) -> Option<Node<T>>

Adds an element immediately preceedeing the node associated with the specified handle. Returns the handle to the node thats been added or None if the specified handle is invalid.

This operation should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);

list.push_head(0);
let middle = list.push_head(1);
list.push_head(2);
list.push_prev(&middle, 100);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&100));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), None);

pub fn append(&mut self, other: &mut Self)

Moves all nodes from the other list to the end of this list. After this operation completes, the other list is empty and all the nodes from that list have been moved into this one.

All handles to nodes previously returned by other list will become invalid after this operation completes.

This operation has no effect on the allocated capacity of either list.

This operation should compute in O(1) time

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(10);
list.push_back(0);

let mut list2 = LinkedList::<u8>::with_capacity(10);
list2.push_back(1);
list2.push_back(2);

list.append(&mut list2);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), None);

assert_eq!(list.len(), 3);
assert!(list2.is_empty());

pub fn make_head(&mut self, node: &Node<T>) -> bool

Moves the node associated with the specified handle to the front (head) of the list. If the node is already at the head of the list then this operation has no effect.

Returns true if the node is successfully moved to the head of the list (or if it was already at the head) and false if the specified handle is invalid.

This operation should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(3);
let hnd0 = list.push_tail(0);
let hnd1 = list.push_tail(1);
let hnd2 = list.push_tail(2);

assert_eq!(list.head(), Some(&0));
list.make_head(&hnd2);
assert_eq!(list.head(), Some(&2));

pub fn make_tail(&mut self, node: &Node<T>) -> bool

Moves the node associated with the specified handle to the back (tail) of the list. If the node is already at the tail of the list then this operation has no effect.

Returns true if the node is successfully moved to the tail of the list (or if it was already at the tail) and false if the specified handle is invalid.

This operation should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(3);
let hnd0 = list.push_tail(0);
let hnd1 = list.push_tail(1);
let hnd2 = list.push_tail(2);

assert_eq!(list.tail(), Some(&2));
list.make_tail(&hnd0);
assert_eq!(list.tail(), Some(&0));

pub fn is_prev(&self, node: &Node<T>, other: &Node<T>) -> Option<bool>

Returns true if the specified node is immediately previous to other and false otherwise. If either of the nodes is invalid, this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(4);
let hnd0 = list.push_tail(0);
let hnd1 = list.push_tail(1);
let hnd2 = list.push_tail(2);
list.pop_tail();
assert_eq!(list.is_prev(&hnd0, &hnd1), Some(true));
assert_eq!(list.is_prev(&hnd1, &hnd0), Some(false));
assert_eq!(list.is_prev(&hnd1, &hnd2), None);

pub fn is_next(&self, node: &Node<T>, other: &Node<T>) -> Option<bool>

Returns true if the specified node is immediately after other and false otherwise. If either of the nodes is invalid, this method returns None.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(4);
let hnd0 = list.push_tail(0);
let hnd1 = list.push_tail(1);
let hnd2 = list.push_tail(2);
list.pop_tail();
assert_eq!(list.is_next(&hnd1, &hnd0), Some(true));
assert_eq!(list.is_next(&hnd0, &hnd1), Some(false));
assert_eq!(list.is_next(&hnd2, &hnd1), None);

pub fn is_head(&self, node: &Node<T>) -> Option<bool>

Returns true if the specified node is the head of the list and false if its not. If the specified node is invalid, then this method returns None

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(4);
let hnd0 = list.push_tail(0);
let hnd1 = list.push_tail(1);
let hnd2 = list.push_tail(2);
list.pop_tail();
assert_eq!(list.is_head(&hnd0), Some(true));
assert_eq!(list.is_head(&hnd1), Some(false));
assert_eq!(list.is_head(&hnd2), None);

pub fn is_tail(&self, node: &Node<T>) -> Option<bool>

Returns true if the specified node is the tail of the list and false if its not. If the specified node is invalid, then this method returns None

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(4);
let hnd0 = list.push_tail(0);
let hnd1 = list.push_tail(1);
let hnd2 = list.push_tail(2);
list.pop_tail();
assert_eq!(list.is_tail(&hnd0), Some(false));
assert_eq!(list.is_tail(&hnd1), Some(true));
assert_eq!(list.is_tail(&hnd2), None);

pub fn swap_node(&mut self, node: &Node<T>, other: &Node<T>) -> bool

Swaps the position in the list of the two nodes and returns true on success. If either node is invalid then this method returns false.

This method should complete in O(1) time.

Examples

use deepmesa::lists::LinkedList;
let mut list = LinkedList::<u8>::with_capacity(4);
let hnd0 = list.push_tail(0);
let hnd1 = list.push_tail(1);
let hnd2 = list.push_tail(2);
list.pop_tail();
assert_eq!(list.swap_node(&hnd0, &hnd1), true);
assert_eq!(list.swap_node(&hnd1, &hnd2), false);
assert_eq!(list.is_head(&hnd1), Some(true));
assert_eq!(list.is_tail(&hnd0), Some(true));

Trait Implementations

impl<T: Debug> Debug for LinkedList<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Drop for LinkedList<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, T> IntoIterator for &'a LinkedList<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut LinkedList<T>

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.