Version française
Home     About     Download     Resources     Contact us    
Browse thread
simulation of doubly linked lists in OCaml?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Xavier Leroy <Xavier.Leroy@i...>
Subject: Re: simulation of doubly linked lists in OCaml?
> 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