A doubly-linked list. Supports O(1) head, tail, count, push, pop, etc.
Do not use ==, !=, <, etc on doubly-linked lists -- it may not terminate.
DListLinkDListDListNodefor DListNode<T>for DListNode<T>for DList<T>for DList<T>for DList<T>DList - Creates a new, empty dlist.concat - Produce a list from a list of lists, leaving no elements behind in the inputfrom_elem - Creates a new dlist with a single elementfrom_vecnew_dlist_node - Creates a new dlist node with the given data.DListLinktype DListLink<T> = Option<DListNode<T>>DListDList_(@{mut size: uint, mut hd: DListLink<T>, mut tl: DListLink<T>,})DListNodepub DListNode(@{data: T, mut linked: bool, mut prev: DListLink<T>, mut next: DListLink<T>,})DListNode<T>assert_linksfn assert_links()DListNode<T>next_linkfn next_link() -> Option<DListNode<T>>Get the next node in the list, if there is one.
next_nodefn next_node() -> DListNode<T>Get the next node in the list, failing if there isn't one.
prev_linkfn prev_link() -> Option<DListNode<T>>Get the previous node in the list, if there is one.
prev_nodefn prev_node() -> DListNode<T>Get the previous node in the list, failing if there isn't one.
DList<T>new_linkfn new_link(data: T) -> DListLink<T>assert_minefn assert_mine(nobe: DListNode<T>)make_minefn make_mine(nobe: DListNode<T>)linkfn link(before: DListLink<T>, after: DListLink<T>)unlinkfn unlink(nobe: DListNode<T>)add_headfn add_head(nobe: DListLink<T>)add_tailfn add_tail(nobe: DListLink<T>)insert_leftfn insert_left(nobe: DListLink<T>, neighbour: DListNode<T>)insert_rightfn insert_right(neighbour: DListNode<T>, nobe: DListLink<T>)DList<T>lenfn len() -> uintGet the size of the list. O(1).
is_emptyfn is_empty() -> boolReturns true if the list is empty. O(1).
is_not_emptyfn is_not_empty() -> boolReturns true if the list is not empty. O(1).
push_headfn push_head(data: T)Add data to the head of the list. O(1).
push_head_nfn push_head_n(data: T) -> DListNode<T>Add data to the head of the list, and get the new containing node. O(1).
pushfn push(data: T)Add data to the tail of the list. O(1).
push_nfn push_n(data: T) -> DListNode<T>Add data to the tail of the list, and get the new containing node. O(1).
insert_beforefn insert_before(data: T, neighbour: DListNode<T>)Insert data into the middle of the list, left of the given node. O(1).
insert_n_beforefn insert_n_before(nobe: DListNode<T>, neighbour: DListNode<T>)Insert an existing node in the middle of the list, left of the given node. O(1).
insert_before_nfn insert_before_n(data: T, neighbour: DListNode<T>) -> DListNode<T>Insert data in the middle of the list, left of the given node, and get its containing node. O(1).
insert_afterfn insert_after(data: T, neighbour: DListNode<T>)Insert data into the middle of the list, right of the given node. O(1).
insert_n_afterfn insert_n_after(nobe: DListNode<T>, neighbour: DListNode<T>)Insert an existing node in the middle of the list, right of the given node. O(1).
insert_after_nfn insert_after_n(data: T, neighbour: DListNode<T>) -> DListNode<T>Insert data in the middle of the list, right of the given node, and get its containing node. O(1).
pop_nfn pop_n() -> Option<DListNode<T>>Remove a node from the head of the list. O(1).
pop_tail_nfn pop_tail_n() -> Option<DListNode<T>>Remove a node from the tail of the list. O(1).
peek_nfn peek_n() -> Option<DListNode<T>>Get the node at the list's head. O(1).
peek_tail_nfn peek_tail_n() -> Option<DListNode<T>>Get the node at the list's tail. O(1).
head_nfn head_n() -> DListNode<T>Get the node at the list's head, failing if empty. O(1).
tail_nfn tail_n() -> DListNode<T>Get the node at the list's tail, failing if empty. O(1).
removefn remove(nobe: DListNode<T>)Remove a node from anywhere in the list. O(1).
appendfn append(them: DList<T>)Empty another list onto the end of this list, joining this list's tail to the other list's head. O(1).
prependfn prepend(them: DList<T>)Empty another list onto the start of this list, joining the other list's tail to this list's head. O(1).
reversefn reverse()Reverse the list's elements in place. O(n).
clearfn clear()Remove everything from the list. This is important because the cyclic links won't otherwise be automatically refcounted-collected. O(n).
each_nodefn each_node(f: &fn(DListNode<T>) -> bool)Iterate over nodes.
assert_consistentfn assert_consistent()Check data structure integrity. O(n).
DList<T>popfn pop() -> Option<T>Remove data from the head of the list. O(1).
pop_tailfn pop_tail() -> Option<T>Remove data from the tail of the list. O(1).
peekfn peek() -> Option<T>Get data at the list's head. O(1).
peek_tailfn peek_tail() -> Option<T>Get data at the list's tail. O(1).
headfn head() -> TGet data at the list's head, failing if empty. O(1).
tailfn tail() -> TGet data at the list's tail, failing if empty. O(1).
to_vecfn to_vec() -> ~[T]Get the elements of the list as a vector. O(n).
DListfn DList<T>() -> DList<T>Creates a new, empty dlist.
concatfn concat<T>(lists: DList<DList<T>>) -> DList<T>Produce a list from a list of lists, leaving no elements behind in the input. O(number of sub-lists).
from_elemfn from_elem<T>(data: T) -> DList<T>Creates a new dlist with a single element
from_vecfn from_vec<T: Copy>(vec: &[T]) -> DList<T>new_dlist_nodefn new_dlist_node<T>(data: T) -> DListNode<T>Creates a new dlist node with the given data.