Haskell98
http://okmij.org/ftp/Algorithms.html#purecycliclist
Pure functional, mutationfree, constanttimeaccess doublelinked lists
Note that insertions, deletions, lookups have a worstcase complexity of O(min(n,W)), where W is either 32 or 64 (depending on the paltform). That means the access time is bounded by a small constant (32 or 64).
Pure functional, mutationfree, efficient doublelinked lists
It is always an interesting challenge to write a pure functional and efficient implementation of an imperative algorithm destructively operating a data structure. The functional implementation has a significant benefit of equational reasoning and modularity. We can comprehend the algorithm without keeping the implicit global state in mind. The mutationfree, functional realization has practical benefits: the ease of adding checkpointing, undo and redo. The absence of mutations makes the code multithreadingsafe and helps in porting to distributed or nonsharedmemory parallel architectures. On the other hand, an imperative implementation has the advantage of optimality: mutating a component in a complex data structure is a constanttime operation, at least on conventional architectures. Imperative code makes sharing explicit, and so permits efficient implementation of cyclic data structures.
We show a simple example of achieving all the benefits of an imperative data structure  including sharing and the efficiency of updates  in a pure functional program. Our data structure is a doublylinked, possibly cyclic list, with the standard operations of adding, deleting and updating elements; traversing the list in both directions; iterating over the list, with cycle detection. The code:
uniformly handles both cyclic and terminated lists; does not rebuild the whole list on updates; updates the value in the current node in time bound by a small constant; does not use or mention any monads; does not use any IORef, STRef, TVars, or any other destructive updates; permits the logging, undoing and redoing of updates, checkpointing; easily generalizes to twodimensional meshes.
The algorithm is essentially imperative, thus permitting identity checking and inplace
updates
, but implemented purely functionally. Although the code uses many local, type safe
heaps
, there is emphatically no global heap and no global state.
Version: The current version is 1.2, Jan 7, 2009.
References
HaskellCafe discussion ``Updating doubly linked lists''. January 2009
 type Ref = Int
 data Node a = Node {
 node_val :: a
 node_left :: Ref
 node_right :: Ref
 data DList a = DList {
 dl_counter :: Ref
 dl_current :: Ref
 dl_mem :: IntMap (Node a)
 empty :: DList a
 well_formed :: DList a > Bool
 is_empty :: DList a > Bool
 get_curr_node :: DList a > Node a
 insert_right :: a > DList a > DList a
 delete :: DList a > DList a
 get_curr :: DList a > a
 move_right :: DList a > Maybe (DList a)
 move_right' :: DList a > DList a
 move_left :: DList a > Maybe (DList a)
 move_left' :: DList a > DList a
 fromList :: [a] > DList a
 takeDL :: Int > DList a > [a]
 takeDLrev :: Int > DList a > [a]
 update :: a > DList a > DList a
 toList :: DList a > [a]
Documentation
Because DList contains the pointer
to the current element, DList
is also a Zipper
DList  

well_formed :: DList a > BoolSource
In a wellformed list, dl_current must point to a valid node All operations below preserve wellformedness
get_curr_node :: DList a > Node aSource
auxiliary function
insert_right :: a > DList a > DList aSource
The insert operation below makes a cyclic list The other operations don't care Insert to the right of the current element, if any Return the DL where the inserted node is the current one
delete :: DList a > DList aSource
Delete the current element from a nonempty list We can handle both cyclic and terminated lists The right node becomes the current node. If the right node does not exists, the left node becomes current
move_right :: DList a > Maybe (DList a)Source
move_right' :: DList a > DList aSource
If no right, just stay inplace
move_left' :: DList a > DList aSource
If no left, just stay inplace