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.
DListLink
DList
DListNode
for DListNode<T> where <T>
for DList<T> where <T>
for DList<T> where <T: Copy>
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_vec
- Creates a new dlist from a vector of elements, maintaining the same ordernew_dlist_node
- Creates a new dlist node with the given data.DListLink
type DListLink<T> = Option<@mut DListNode<T>>
DList
pub struct DList<T> {
size: uint,
hd: DListLink<T>,
tl: DListLink<T>,
}
DListNode
pub struct DListNode<T> {
data: T,
linked: bool,
prev: DListLink<T>,
next: DListLink<T>,
}
DListNode<T>
where <T>
next_link
fn next_link(@mut self) -> DListLink<T>
Get the next node in the list, if there is one.
next_node
fn next_node(@mut self) -> @mut DListNode<T>
Get the next node in the list, failing if there isn't one.
prev_link
fn prev_link(@mut self) -> DListLink<T>
Get the previous node in the list, if there is one.
prev_node
fn prev_node(@mut self) -> @mut DListNode<T>
Get the previous node in the list, failing if there isn't one.
DList<T>
where <T>
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.
len
fn len(@mut self) -> uint
Get the size of the list. O(1).
is_empty
fn is_empty(@mut self) -> bool
Returns true if the list is empty. O(1).
push_head
fn push_head(@mut self, data: T)
Add data to the head of the list. O(1).
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).
push
fn push(@mut self, data: T)
Add data to the tail of the list. O(1).
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).
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).
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).
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).
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).
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).
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).
pop_n
fn pop_n(@mut self) -> DListLink<T>
Remove a node from the head of the list. O(1).
pop_tail_n
fn pop_tail_n(@mut self) -> DListLink<T>
Remove a node from the tail of the list. O(1).
peek_n
fn peek_n(@mut self) -> DListLink<T>
Get the node at the list's head. O(1).
peek_tail_n
fn peek_tail_n(@mut self) -> DListLink<T>
Get the node at the list's tail. O(1).
head_n
fn head_n(@mut self) -> @mut DListNode<T>
Get the node at the list's head, failing if empty. O(1).
tail_n
fn tail_n(@mut self) -> @mut DListNode<T>
Get the node at the list's tail, failing if empty. O(1).
remove
fn remove(@mut self, nobe: @mut DListNode<T>)
Remove a node from anywhere in the list. O(1).
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).
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).
reverse
fn reverse(@mut self)
Reverse the list's elements in place. O(n).
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).
each_node
fn each_node(@mut self, f: &fn(@mut DListNode<T>) -> bool) -> bool
Iterate over nodes.
assert_consistent
fn assert_consistent(@mut self)
Check data structure integrity. O(n).
DList<T>
where <T: Copy>
pop
fn pop(@mut self) -> Option<T>
Remove data from the head of the list. O(1).
pop_tail
fn pop_tail(@mut self) -> Option<T>
Remove data from the tail of the list. O(1).
peek
fn peek(@mut self) -> Option<T>
Get data at the list's head. O(1).
peek_tail
fn peek_tail(@mut self) -> Option<T>
Get data at the list's tail. O(1).
head
fn head(@mut self) -> T
Get data at the list's head, failing if empty. O(1).
tail
fn tail(@mut self) -> T
Get data at the list's tail, failing if empty. O(1).
DList
fn DList<T>() -> @mut DList<T>
Creates a new, empty dlist.
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).
from_elem
fn from_elem<T>(data: T) -> @mut DList<T>
Creates a new dlist with a single element
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
new_dlist_node
fn new_dlist_node<T>(data: T) -> @mut DListNode<T>
Creates a new dlist node with the given data.