Simple Implementation of Double Linked List in Ocaml

In this script, we will give a simple implementation of double linked list in OCaml. We can find more details in the book Introduction to Objective Caml, page 65.

type 'a elem =
  | Nil
  | Elem of 'a * 'a elem ref * 'a elem ref
;;

let nil_elem = Nil ;;   (* create a Nil element *)

let create_element x = Elem (x, ref Nil, ref Nil) ;;

let get = function
  | Elem (x, _, _) -> x
  | Nil -> raise (Invalid_argument "get") ;;

let prev_elem = function
  | Elem (_, prev, _) -> !prev
  | Nil -> raise (Invalid_argument "prev_elem") ;;



(* implement the doubly-linked list, the list itself can be just
 * a reference ot the first element. 
 *)

type 'a dlist = 'a elem ref ;;

let create () = ref Nil ;;

let insert list elem =
  match elem, !list with
  | Elem (_, prev, next), Nil ->
      prev := Nil;
      next := Nil;
      list := elem
  | Elem (_, prev1, next1) , (Elem (_, prev2, _) as head) ->
      prev1 := Nil;
      next1 := head;
      prev2 := elem;
      list  := elem
  | Nil, _ ->
      raise (Invalid_argument "insert")
;;

let remove list elem =
  match elem with
  | Elem (_, prev, next) ->
      (match !prev with
       | Elem (_, _, prev_next) -> prev_next := !next
       | Nil -> list := !next) ;
      (match !next with
       | Elem (_,next_prev, _) -> next_prev := !prev
       | Nil -> ())
  | Nil ->
      raise (Invalid_argument "remove")
;;