Re: simulation of doubly linked lists in OCaml?

[Xavier Leroy <Xavier.Leroy@inria.fr>]

> I wonder if it is possible to simulate by datatype constructors a
> doubly linked list in OCaml/

In addition to the implementation that Dennis Gang Chen posted, you
might also be interested in the following implementation of circular
doubly linked lists.  It's really sweet.

- Xavier Leroy

type 'a cdllist =
  { data: 'a; mutable prev: 'a cdllist; mutable next: 'a cdllist }

let create d =
  let rec l = { data = d; prev = l; next = l } in l

let insert_before d list =
  let newcons = { data = d; prev = list.prev; next = list } in
  list.prev.next <- newcons;
  list.prev <- newcons;
  newcons

let insert_after list d =
  let newcons = { data = d; prev = list; next = list.ext } in
  list.next.prev <- newcons;
  list.next <- newcons;
  newcons

let remove list =
  list.prev.next <- list.next;
  list.next.prev <- list.prev

let iter f list =
  let rec iter_rec l =
    f l.data;
    if l.next != list then iter_rec l.next
  in iter_rec list