Maintainer | joeyadams3.14159@gmail.com |
---|

Mutable, doubly linked lists for use with STM (software transactional memory). Provides efficient random insertion and removal.

This module is usually imported qualified:

import Data.STM.LinkedList (LinkedList) import qualified Data.STM.LinkedList as LinkedList

- data LinkedList a
- listHead :: LinkedList a -> Node a
- data Node a
- value :: Node a -> a
- null :: LinkedList a -> STM Bool
- length :: LinkedList a -> STM Int
- empty :: STM (LinkedList a)
- emptyIO :: IO (LinkedList a)
- prepend :: a -> LinkedList a -> STM (Node a)
- append :: a -> LinkedList a -> STM (Node a)
- insertBefore :: a -> Node a -> STM (Node a)
- insertAfter :: a -> Node a -> STM (Node a)
- delete :: Node a -> STM ()
- prev :: Node a -> STM (Maybe (Node a))
- next :: Node a -> STM (Maybe (Node a))
- start :: LinkedList a -> STM (Maybe (Node a))
- end :: LinkedList a -> STM (Maybe (Node a))
- toList :: LinkedList a -> STM [a]
- toListRev :: LinkedList a -> STM [a]

# The LinkedList type

data LinkedList a Source

List handle. Used for insertion and traversal starting at the beginning or end of the list.

listHead :: LinkedList a -> Node aSource

# The Node type

List node. Used for insertion, traversal, and removal starting at a given item in the list.

A Node contains an immutable value of type `a`

, and `TVar`

s that point to
the previous and next nodes.

Node equality can be likened to pointer equality in C. Two Node values are considered equal if and only if they were created with the same insertion operation.

# Query

null :: LinkedList a -> STM BoolSource

*O(1)*. Is the list empty?

length :: LinkedList a -> STM IntSource

*O(n)*. Count the number of items in the list.

# Construction

empty :: STM (LinkedList a)Source

*O(1)*. Create an empty linked list.

## Insertion

prepend :: a -> LinkedList a -> STM (Node a)Source

*O(1)*. Add a node to the beginning of a linked list.

append :: a -> LinkedList a -> STM (Node a)Source

*O(1)*. Add a node to the end of a linked list.

insertBefore :: a -> Node a -> STM (Node a)Source

*O(1)*. Insert an item before the given node.

insertAfter :: a -> Node a -> STM (Node a)Source

*O(1)*. Insert an item after the given node.

## Deletion

delete :: Node a -> STM ()Source

*O(1)*. Remove a node from whatever `LinkedList`

it is in. If the node
has already been removed, this is a no-op.

# Traversal

start :: LinkedList a -> STM (Maybe (Node a))Source

*O(1)*. Get the node corresponding to the first item of the list. Return
`Nothing`

if the list is empty.

end :: LinkedList a -> STM (Maybe (Node a))Source

*O(1)*. Get the node corresponding to the last item of the list. Return
`Nothing`

if the list is empty.

# Conversion

toList :: LinkedList a -> STM [a]Source

*O(n)*. Return all of the items in a `LinkedList`

.

toListRev :: LinkedList a -> STM [a]Source

*O(n)*. Return all of the items in a `LinkedList`

, in reverse order.