Doubly linked list with initial list and mutation

General Usage
,
1

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,

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?

2

Isn’t this what you want? GitHub - tk3369/CircularList.jl: A circular linked list

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

1 Like
3

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?

4

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.

2 Likes