# How does one implement cyclic doubly-linked list?

**URL:** <https://discuss.ocaml.org/t/how-does-one-implement-cyclic-doubly-linked-list/9483>\
**Category:** Learning\
**Tags:** doubly-linked-list\
**Created:** [March 8, 2022, 4:29pm UTC](https://discuss.ocaml.org/t/how-does-one-implement-cyclic-doubly-linked-list/9483 "2022-03-08T16:29:10Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Nolord](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nolord/32/3542_2.png) [@Nolord](https://discuss.ocaml.org/u/Nolord)\
**Post date:** [March 8, 2022, 4:29pm UTC](https://discuss.ocaml.org/t/how-does-one-implement-cyclic-doubly-linked-list/9483/1 "2022-03-08T16:29:10Z")

</div>

Is it possible to create a cyclic doubly linked list with this type declaration ?

```auto
type 'a dlist =
  | Nil
  | Cons of 'a dlist Lazy.t * 'a * 'a dlist Lazy.t

```

This could fit for the creation of a singleton list  
`let singl v = let rec cell = Cons (lazy cell, v, lazy cell) in cell`

But I can’t figure out how to cons an element to the list in O(1), as in singly-linked lists.

---

<div class="post-metadata">

**Author:** ![octachron](https://avatars.discourse-cdn.com/v4/letter/o/49beb7/32.png) [@octachron](https://discuss.ocaml.org/u/octachron)\
**Post date:** [March 8, 2022, 5:35pm UTC](https://discuss.ocaml.org/t/how-does-one-implement-cyclic-doubly-linked-list/9483/2 "2022-03-08T17:35:03Z")

</div>

Since your doubly linked list is immutable, it is not possible to add an element to the cycle without making a new copy of the whole cycle. An `O(1)` `cons` is thus impossible.