Up
# module Dllist

: sig
###### node functions

###### list conversion

###### enums

A mutable, imperative, circular, doubly linked list library

This module implements a doubly linked list in a mutable or imperitive style (changes to the list are visible to all copies of the list).

#

type 'a node_t

#

exception Empty

#

val add : 'a node_t -> 'a -> unit

`add n a`

Creates a new node containing data `a`

and inserts it into
the list after node `n`

. This is an O(1) operation.

#

val remove : 'a node_t -> unit

Remove node from the list no matter where it is. This is an O(1) operation.

#

val splice : 'a node_t -> 'a node_t -> unit

`splice n1 n2`

Connects `n1`

and `n2`

so that
`next n1 == n2 && prev n2 == n1`

. This can be used to connect two discrete
lists, or, if used on two nodes within the same list, it can be used to
separate the nodes between `n1`

and `n2`

from the rest of the list. In this
case, those nodes become a discrete list by themselves. This is an O(1)
operation.

#

val get : 'a node_t -> 'a

Given a node, get the data associated with that node. This is an O(1) operation.

#

val set : 'a node_t -> 'a -> unit

Given a node, set the data associated with that node. This is an O(1) operation.

#

val iter : ('a -> unit) -> 'a node_t -> unit

`iter f n`

Apply `f`

to every element in the list, starting at `n`

. This
is an O(N) operation.

#

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b node_t -> 'a

Accumulate a value over the entire list. This works like List.fold_left. This is an O(N) operation.

#

val fold_right : ('a -> 'b -> 'b) -> 'a node_t -> 'b -> 'b

Accumulate a value over the entire list. This works like List.fold_right, but since the list is bidirectional, it doesn't suffer the performance problems of List.fold_right. This is an O(N) operation.

#

val of_list : 'a list -> 'a node_t

Converts from a normal list to a Dllist and returns the first node. Raises
`Empty`

if given list is empty. This is an O(N) operation.

end