A double ended queue in OCaml - what's the idea?

I came across this implementation of a deque:

type 'a elem = { mutable l1 : 'a elem; mutable l2 : 'a elem; v : 'a option }
type 'a queue = { mutable front : 'a elem; mutable back : 'a elem }

let init () =
    let rec g1 = { l1 = g1; l2 = g2; v = None}
    and     g2 = { l1 = g2; l2 = g1; v = None}
    in
        { front = g1; back = g2 }

let is_empty q =
    let f = q.front
    and b = q.back
    in
        f.l2 == b

let put_between p q x =
    let r = { l1 = p; l2 = q; v = Some x }
    in begin
        if p.l1 == q then p.l1 <- r else p.l2 <- r;
        if q.l1 == p then q.l1 <- r else q.l2 <- r
    end

I don't really understand what's the main idea of this realization, the main concept? Could you please explain it to me? Why are we using those records recursive to each other?

To expand slightly on what @Lee says, this is a straightforward mutable implementation of a double-ended queue (or deque), like what you would code up in a language with ordinary pointers (such as C).

There are only a few specific ideas I can see, other than keeping the links straight.

1. There is a header at each end of the deque (what @Lee calls a sentinel). So an empty deque has two nodes in it. Because of two-way linkage, each node points at the other. (This is probably the recursion you're referring to.)

2. Because OCaml is strongly typed, the nodes all have to be the same type, even the headers at the end. Since headers don't have a value in them, you need to use 'a option for the value. In other words, you need to allow nodes with no value in them.

3. Caller of put_between needs to supply two adjacent nodes, but they can be supplied in either order.

4. The code is using "physical equality" (==) to test for identity of nodes. This is a dangerous thing to do in OCaml, but it is correct here. Mutable values can be compared with == with more or less the result you would expect from comparing pointers in an imperative language.

One reason to study OCaml is to learn about functional programming. This code isn't useful for this, since (as I say) it's a mutable implementation. You can see some actual functional deque implementations in Chapter 5 of Chris Okasaki's PhD thesis. (You can also buy his book, which is a perennial favorite.)