How to represent a double-ended linked list?

Learning
1

My attempt:

type 'a de_list =
| Empty
| One of 'a
| Left of 'a * 'a de_list
| Right of 'a de_list * 'a

let rec remove_left (de_list: 'a de_list) : 'a de_list * 'a option = (
  match de_list with
  | Empty -> (Empty, None)
  | One element -> (Empty, Some element)
  | Left (element, rest) -> (rest, Some element)
  | Right (rest, element) -> (
    let (new_de_list, removed_element) = remove_left rest in
    (Right (new_de_list, element), removed_element)
  )
)

let rec add_left (de_list: 'a de_list) (element: 'a) : 'a de_list = (
  match de_list with
  | Empty -> One element
  | _ -> Left (element, de_list)
)

(* remove_right, add_right omitted *)
2

There’s a particularly lovely version due to Chris Okasaki:

type 'a de_list = 'a list * 'a list

where the “list” is the concatenation of the first list and the reverse of the second. The idea being that you can push or pop onto the front or back very cheaply, until you’re popping off an empty list, at which point you must reverse the other list before continuing. [hope that was clear]

IIRC Okasaki has a book of “purely functional datastructures” in which this is all laid-out, though I just heard it from a friend a few decades ago.

4 Likes
3

Below is an imperative solution; I would stick with the suggestion from @Chet_Murthy unless you need to be able to drop elements from inside the list.

  type 'a node = {
      value: 'a
    ; mutable prev: 'a node option
    ; mutable next: 'a node option
  }

  type 'a t = {mutable first: 'a node option; mutable last: 'a node option}

  let create () = {first= None; last= None}

  let node x = {value= x; prev= None; next= None}

  let append t n =
    match t.last with
    | None ->
        let node = Some n in
        t.first <- node ;
        t.last <- node
    | Some lst ->
        let node = Some n in
        lst.next <- node ;
        n.prev <- t.last ;
        t.last <- node

  (** [drop] a node [n] from (its) list [t]. The interesting property is
      that we can drop any element from its list that we know. However,
      we don't check that [n] is indeed a member of [t] and it's an
      unchecked error to pass an [n] that is not a member of [t].
      This is similar to a
      pointer-based implementation in C. We infer that we need to update
      the fist, last entry of the list of [n]'s prev or next is [None],
      hence it is the first or last element in the list. *)
  let drop t n =
    let np = n.prev in
    let nn = n.next in
    ( match np with
    | None ->
        t.first <- nn
    | Some x ->
        x.next <- nn ;
        n.prev <- None
    ) ;
    match nn with
    | None ->
        t.last <- np
    | Some x ->
        x.prev <- np ;
        n.next <- None
1 Like
4

+1 for @Chet_Murthy’s suggestion of using a pair of lists to represent dequeues, with “push” and “pop” operations on both ends. Refer to Chris Okasaki’s book, Purely Functional Data Structures, section 5.2, exercise 5.1. There’s an OCaml implementation in the Batteries library, Batteries user guide : BatDeque .

If you need more operations, such as fast concatenation of double-ended lists, consider finger trees (Finger tree - Wikipedia). Again, there’s an implementation in Batteries, Batteries user guide : BatFingerTree .

Blowing my own horn, you might find my lectures on persistent data structures useful: Persistent data structures , in particular lecture 3 (on amortization for queues) and lectures 5 and 6 (for finger trees).

8 Likes
5

Given this definition, it might actually make sense to define it as

type 'a de_list = 'a list * 'a Bwd.t

I.e. the recently-announced ‘semantically backward list’ data type: [ANN] bwd 2.3.0 for backward lists

1 Like