A doubly-linked list. Supports O(1) head, tail, count, push, pop, etc.

Safety note

Do not use ==, !=, <, etc on doubly-linked lists -- it may not terminate.

Struct DList

pub struct DList<T> {
    size: uint,
    hd: DListLink<T>,
    tl: DListLink<T>,
}

Struct DListNode

pub struct DListNode<T> {
    data: T,
    linked: bool,
    prev: DListLink<T>,
    next: DListLink<T>,
}

Implementation for DListNode<T> where <T>

Method next_node

fn next_node(@mut self) -> @mut DListNode<T>

Get the next node in the list, failing if there isn't one.

Method prev_node

fn prev_node(@mut self) -> @mut DListNode<T>

Get the previous node in the list, failing if there isn't one.

Implementation for DList<T> where <T>

Method each

fn each(@mut self, f: &fn(v: &T) -> bool) -> bool

Iterates through the current contents.

Attempts to access this dlist during iteration are allowed (to allow for e.g. breadth-first search with in-place enqueues), but removing the current node is forbidden.

Method len

fn len(@mut self) -> uint

Get the size of the list. O(1).

Method is_empty

fn is_empty(@mut self) -> bool

Returns true if the list is empty. O(1).

Method push_head

fn push_head(@mut self, data: T)

Add data to the head of the list. O(1).

Method push_head_n

fn push_head_n(@mut self, data: T) -> @mut DListNode<T>

Add data to the head of the list, and get the new containing node. O(1).

Method push

fn push(@mut self, data: T)

Add data to the tail of the list. O(1).

Method push_n

fn push_n(@mut self, data: T) -> @mut DListNode<T>

Add data to the tail of the list, and get the new containing node. O(1).

Method insert_before

fn insert_before(@mut self, data: T, neighbour: @mut DListNode<T>)

Insert data into the middle of the list, left of the given node. O(1).

Method insert_n_before

fn insert_n_before(@mut self, nobe: @mut DListNode<T>,
                   neighbour: @mut DListNode<T>)

Insert an existing node in the middle of the list, left of the given node. O(1).

Method insert_before_n

fn insert_before_n(@mut self, data: T, neighbour: @mut DListNode<T>) ->
 @mut DListNode<T>

Insert data in the middle of the list, left of the given node, and get its containing node. O(1).

Method insert_after

fn insert_after(@mut self, data: T, neighbour: @mut DListNode<T>)

Insert data into the middle of the list, right of the given node. O(1).

Method insert_n_after

fn insert_n_after(@mut self, nobe: @mut DListNode<T>,
                  neighbour: @mut DListNode<T>)

Insert an existing node in the middle of the list, right of the given node. O(1).

Method insert_after_n

fn insert_after_n(@mut self, data: T, neighbour: @mut DListNode<T>) ->
 @mut DListNode<T>

Insert data in the middle of the list, right of the given node, and get its containing node. O(1).

Method pop_n

fn pop_n(@mut self) -> DListLink<T>

Remove a node from the head of the list. O(1).

Method pop_tail_n

fn pop_tail_n(@mut self) -> DListLink<T>

Remove a node from the tail of the list. O(1).

Method peek_n

fn peek_n(@mut self) -> DListLink<T>

Get the node at the list's head. O(1).

Method peek_tail_n

fn peek_tail_n(@mut self) -> DListLink<T>

Get the node at the list's tail. O(1).

Method head_n

fn head_n(@mut self) -> @mut DListNode<T>

Get the node at the list's head, failing if empty. O(1).

Method tail_n

fn tail_n(@mut self) -> @mut DListNode<T>

Get the node at the list's tail, failing if empty. O(1).

Method remove

fn remove(@mut self, nobe: @mut DListNode<T>)

Remove a node from anywhere in the list. O(1).

Method append

fn append(@mut self, them: @mut DList<T>)

Empty another list onto the end of this list, joining this list's tail to the other list's head. O(1).

Method prepend

fn prepend(@mut self, them: @mut DList<T>)

Empty another list onto the start of this list, joining the other list's tail to this list's head. O(1).

Method reverse

fn reverse(@mut self)

Reverse the list's elements in place. O(n).

Method clear

fn clear(@mut self)

Remove everything from the list. This is important because the cyclic links won't otherwise be automatically refcounted-collected. O(n).

Method each_node

fn each_node(@mut self, f: &fn(@mut DListNode<T>) -> bool) -> bool

Iterate over nodes.

Method assert_consistent

fn assert_consistent(@mut self)

Check data structure integrity. O(n).

Implementation for DList<T> where <T: Copy>

Method pop

fn pop(@mut self) -> Option<T>

Remove data from the head of the list. O(1).

Method pop_tail

fn pop_tail(@mut self) -> Option<T>

Remove data from the tail of the list. O(1).

Method peek

fn peek(@mut self) -> Option<T>

Get data at the list's head. O(1).

Method peek_tail

fn peek_tail(@mut self) -> Option<T>

Get data at the list's tail. O(1).

Method head

fn head(@mut self) -> T

Get data at the list's head, failing if empty. O(1).

Method tail

fn tail(@mut self) -> T

Get data at the list's tail, failing if empty. O(1).

Function DList

fn DList<T>() -> @mut DList<T>

Creates a new, empty dlist.

Function concat

fn concat<T>(lists: @mut DList<@mut DList<T>>) -> @mut DList<T>

Produce a list from a list of lists, leaving no elements behind in the input. O(number of sub-lists).

Function from_elem

fn from_elem<T>(data: T) -> @mut DList<T>

Creates a new dlist with a single element

Function from_vec

fn from_vec<T: Copy>(vec: &[T]) -> @mut DList<T>

Creates a new dlist from a vector of elements, maintaining the same order

Function new_dlist_node

fn new_dlist_node<T>(data: T) -> @mut DListNode<T>

Creates a new dlist node with the given data.