Re: simulation of doubly linked lists in OCaml?

From: Xavier Leroy (Xavier.Leroy@inria.fr)
Date: Fri Apr 28 2000 - 13:55:43 MET DST

  • Next message: John Max Skaller: "Re: what does "32-bit integer" mean?"

    > 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



    This archive was generated by hypermail 2b29 : Fri Apr 28 2000 - 15:22:17 MET DST