CODEWITHSUNDEEP
listocamlcircular-reference
GraphLearner
GraphLearner

Reputation: 327

Creating instances of a doubly linked list

I have been given the following implementation of a doubly linked list:

type 'a elem = {v : 'a; mutable next : 'a lista; mutable prev : 'a lista}
and 'a lista = 'a elem option;;

Using this implementation I'm trying to make some example lists. A one element list is easy to make:

let bla_1 = Some {v = 1; next = None; prev = None};;

And I guess an empty list would be two None nodes. But I don't know how to make lists with more elements.

Upvotes: 1

Views: 462

Answers (1)

coredump
coredump

Reputation: 38809

If you want to build a list with two elements x and y, you have to ensure you have two values of type 'a elem pointing to each other (not counting the intermediate option type 'a lista). Eventually, you need to have a circular structure where:

  • lx is bound to { v = x; next = Some ly; prev = None },
  • and ly is bound to { v = y; next = None; prev = Some lx}

You can have mutually recursive values in OCaml (thanks octhacron):

let rec x = { v = 0; next = Some y; prev = None} 
    and y = { v = 1; next = None; prev = Some x}

But this gets hard to use to build more complex lists. And that's why you have mutable fields: you can build nodes and then connect them by changing their next and prev fields. For example, you first define lx with the next field set to None, and only after you know what is ly, you can replace the value pointed by lx.next by Some ly.

Here below is a function that converts a regular list into a doubly-linked list; when calling itself recursively, it builds nodes; when returning from a recursive call, it modifies the next node so that it points back through its prev field to the current one: 

let rec to_dbl_list = function
    [] -> None
  | x::xs ->
     let node = { v = x; prev = None ; next = (to_dbl_list xs)} in
     let current = Some node in
     (match node.next with
        None -> ()
      | Some next -> (next.prev <- current)) ;
     current ;;

And so:

# to_dbl_list [1; 2; 3];;
- : int lista =
Some
 {v = 1;
  next =
   Some
    {v = 2; next = Some {v = 3; next = None; prev = <cycle>}; prev = <cycle>};
  prev = None}

Upvotes: 4

Related Questions