`Kcas_data.Dllist`

Doubly-linked list.

The interface provides a subset of the operations of the doubly-linked list data structure provided by the lwt-dllist package with some omissions:

- The sequence iterators, e.g.
`iter_l`

,`iter_node_l`

,`fold_l`

,`find_node_opt_l`

, and`find_node_l`

, are not provided. - The
`length`

operation is not provided. - The
`set`

operation is not provided.

A non-compositional `take_all`

operation is added for privatization as well as conversions to a list of nodes (`to_nodes_l`

and `to_nodes_r`

) and to a list of values (`to_list_l`

and `to_list_r`

).

Probably the main reason to use a doubly-linked list like this rather than e.g. a `'a list Loc.t`

is the ability to remove a node without having to potentially iterate through the list:

```
let node_of_x = add_l x list in
(* ... and then later somewhere else ... *)
remove node_of_x
```

A doubly-linked list can also be used as a deque or double-ended queue, but a deque implementation that doesn't allow individual nodes to be removed is likely to be faster.

Type of a doubly-linked list containing `node`

s of type `'a`

.

`val create : unit -> 'a t`

`create ()`

creates a new doubly-linked list.

`val create_node : 'a -> 'a node`

`module Xt : sig ... end`

Explicit transaction log passing on doubly-linked lists.

`val remove : 'a node -> unit`

`remove n`

removes the node `n`

from the doubly-linked list it is part of. `remove`

is idempotent.

`move_l n l`

removes the node `n`

from the doubly-linked list it is part of and then adds it to the left of the list `l`

.

`move_r n l`

removes the node `n`

from the doubly-linked list it is part of and then adds it to the right of the list `l`

.

`val is_empty : 'a t -> bool`

`is_empty l`

determines whether the doubly-linked list `l`

is empty or not.

`add_l v l`

creates and returns a new node with the value `v`

and adds the node to the left of the doubly-linked list `l`

.

`add_r v l`

creates and returns a new node with the value `v`

and adds the node to the right of the doubly-linked list `l`

.

`val take_opt_l : 'a t -> 'a option`

`take_opt_l l`

removes and returns the value of leftmost node of the doubly-linked list `l`

, or return `None`

if the list is empty.

`val take_opt_r : 'a t -> 'a option`

`take_opt_r l`

removes and returns the value of rightmost node of the doubly-linked list `l`

, or return `None`

if the list is empty.

`val take_blocking_l : ?timeoutf:float -> 'a t -> 'a`

`take_blocking_l l`

removes and returns the value of leftmost node of the doubly-linked list `l`

, or blocks waiting for the list to become non-empty.

`val take_blocking_r : ?timeoutf:float -> 'a t -> 'a`

`take_blocking_r l`

removes and returns the value of rightmost node of the doubly-linked list `l`

, or blocks waiting for the list to become non-empty.

`transfer_l l1 l2`

removes all nodes of `l1`

and adds them to the left of `l2`

.

`transfer_r l1 l2`

removes all nodes of `l1`

and adds them to the right of `l2`

.

`val to_list_l : 'a t -> 'a list`

`to_list_l l`

collects the values of the nodes of the doubly-linked list `l`

to a list in left-to-right order.

**NOTE**: This operation is linear time, `O(n)`

, and should typically be avoided unless the list is privatized, e.g. by using `take_all`

.

`val to_list_r : 'a t -> 'a list`

`to_list_r l`

collects the values of the nodes of the doubly-linked list `l`

to a list in right-to-left order.

**NOTE**: This operation is linear time, `O(n)`

, and should typically be avoided unless the list is privatized, e.g. by using `take_all`

.

`to_nodes_l l`

collects the nodes of the doubly-linked list `l`

to a list in left-to-right order.

**NOTE**: This operation is linear time, `O(n)`

, and should typically be avoided unless the list is privatized, e.g. by using `take_all`

.

`to_nodes_r l`

collects the nodes of the doubly-linked list `l`

to a list in right-to-left order.

**NOTE**: This operation is linear time, `O(n)`

, and should typically be avoided unless the list is privatized, e.g. by using `take_all`

.

`take_all l`

removes all nodes of the doubly-linked list `l`

and returns a new doubly-linked list containing the removed nodes.