Maintainer	[email protected]

Data.STM.LinkedList

Contents

The LinkedList type
The Node type
Query
Construction
- Insertion
- Deletion
Traversal
Conversion

Description

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

Synopsis

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

Unwrap the list head, a special Node with the following properties:

```
next . listHead == start
```
```
prev . listHead == end
```
```
insertBefore v . listHead == append v
```
```
insertAfter v . listHead == prepend v
```
```
value . listHead ==> error
```
```
delete . listHead ==> error
```

The Node type

data Node a Source

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 TVars 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.

Instances

Eq (Node a)

value :: Node a -> aSource

Extract the value of a node.

Query

null :: LinkedList a -> STM Bool Source

O(1). Is the list empty?

length :: LinkedList a -> STM Int Source

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

Construction

empty :: STM (LinkedList a)Source

O(1). Create an empty linked list.

emptyIO :: IO (LinkedList a)Source

O(1). Version of empty that can be used in the IO monad.

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

prev :: Node a -> STM (Maybe (Node a))Source

O(1). Get the previous node. Return Nothing if this is the first item, or if this node has been deleted from its list.

next :: Node a -> STM (Maybe (Node a))Source

O(1). Get the next node. Return Nothing if this is the last item, or if this node has been deleted from its list.

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.