From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA13383 for caml-redist; Fri, 28 Apr 2000 15:16:41 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA00704 for <caml-list@pauillac.inria.fr>; Fri, 28 Apr 2000 13:55:51 +0200 (MET DST)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.8.7/8.8.7) with ESMTP id NAA11455;
	Fri, 28 Apr 2000 13:55:44 +0200 (MET DST)
Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA10987; Fri, 28 Apr 2000 13:55:44 +0200 (MET DST)
Message-ID: <20000428135543.40826@pauillac.inria.fr>
Date: Fri, 28 Apr 2000 13:55:43 +0200
From: Xavier Leroy <Xavier.Leroy@inria.fr>
To: Jan Brosius <jan.brosius@village.uunet.be>, caml-list@inria.fr
Subject: Re: simulation of doubly linked lists in OCaml?
References: <002601bfb050$b47b8790$f902bed4@jannt>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Mailer: Mutt 0.89.1
In-Reply-To: <002601bfb050$b47b8790$f902bed4@jannt>; from Jan Brosius on Thu, Apr 27, 2000 at 03:58:01PM +0200
Sender: weis

> 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