# Doubly linked list with initial list and mutation

**URL:** <https://discourse.julialang.org/t/doubly-linked-list-with-initial-list-and-mutation/88375>\
**Category:** General Usage\
**Tags:** question, data\_structures\
**Created:** [October 6, 2022, 10:57pm UTC](https://discourse.julialang.org/t/doubly-linked-list-with-initial-list-and-mutation/88375 "2022-10-06T22:57:31Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![DanielVandH](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielvandh/32/31134_2.png) [@DanielVandH](https://discourse.julialang.org/u/DanielVandH)\
**Post date:** [October 6, 2022, 10:57pm UTC](https://discourse.julialang.org/t/doubly-linked-list-with-initial-list-and-mutation/88375/1 "2022-10-06T22:57:31Z")

</div>

I want to use a doubly linked list that wraps around the indices 1,...,n, so that `next(i) = mod(i+1, n)` and `prev(i) = mod(i-2, n) + 1`. I also then need to modify these values later, setting e.g. `next(prev(π(i))) = next(π(i))` and `prev(next(π(i))) = prev(π(i))`, for some permutation `π` of 1,...,n.

Is there an easy way to do this in Julia? I thought about using DataStructures.jl,

```julia
using DataStructures
n = 9 
idx = 1:9
L = MutableLinkedList{Int64}(idx...)

```

but it’s not clear to me from the documentation how to easily set the `next` and `prev` pointers to be what I need. Am I missing something obvious?

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [October 6, 2022, 11:09pm UTC](https://discourse.julialang.org/t/doubly-linked-list-with-initial-list-and-mutation/88375/2 "2022-10-06T23:09:58Z")

</div>

Isn’t this what you want? [GitHub - tk3369/CircularList.jl: A circular linked list](https://github.com/tk3369/CircularList.jl)

Linked lists are usually slower, except when you really need them. If you need mutation, you might, or not See also:

> **[GitHub - ericphanson/ModularIndices.jl: Modular (periodic) indices for Julia...](https://github.com/ericphanson/ModularIndices.jl)**
>
> Modular (periodic) indices for Julia arrays. Contribute to ericphanson/ModularIndices.jl development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![DanielVandH](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielvandh/32/31134_2.png) [@DanielVandH](https://discourse.julialang.org/u/DanielVandH)\
**Post date:** [October 7, 2022, 12:09am UTC](https://discourse.julialang.org/t/doubly-linked-list-with-initial-list-and-mutation/88375/3 "2022-10-07T00:09:21Z")

</div>

Thanks for this, I’ll take a look at CircularList.jl.

Regarding linked lists: I’ve only just learned about them today, so I don’t know much. I only need it to define the neighbouring vertices of a polygon that are constantly switching, hence the `next`/`prev` definitions I give in my original question. If they are slow as you say, would it be preferable then to just maintain two vectors `next`/`prev` and mutate them as needed?

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [October 7, 2022, 10:19am UTC](https://discourse.julialang.org/t/doubly-linked-list-with-initial-list-and-mutation/88375/4 "2022-10-07T10:19:11Z")

</div>

> [@DanielVandH](#):
>
> Regarding linked lists: I’ve only just learned about them today

You lose direct indexing, so that’s going to be slower, O(n), not O(1). You use push! to add to an Array (or insert!, or pushfirst!, which are slower).

> See sizehint! for notes about the performance model.