# Data structure for inserting and removing in the middle?

When an ordered list, say a path in a graph, is given as

``````a = [1, 2, 3, 4, 5]
``````

I need to add a new node in the middle to make it

``````a = [1, 2, 3, 10, 4, 5]
``````

or remove an element in the middle to make it

``````a = [1, 3, 10, 4, 5]
``````

For this kind of operation, which would be the best way or best data structure?

Thereâ€™s an implementation in DataStructures.jl:

https://juliacollections.github.io/DataStructures.jl/stable/

I suppose it depends on what your definition of â€śbestâ€ť is

because this works just fine, although it reallocates every time

``````julia> a = vcat(a[1:3], [10], a[4:5])
[1,2,3,10,4,5]
julia> a = vcat(a[1:1], a[3:6])
[1,3,10,4,5]
``````

and will max out at double the space of `a` but GC will keep it at the length of `a `
whereas a double-linked-list will always take double the space as you need to store a link for each entry.

That said, I guess your MWE is simpler than your actual code.

2 Likes

Note that this could be written using `insert!`.

The question in general really does boil down to how youâ€™re using the datastructure. Are you reading much more often than writing? The `Vector` approach with `insert!` is probably a good fit. Are you writing more often than reading? Some kind of linked list may be more suitable, due to not having to move elements after the index you inserted, at the cost of losing cache coherence of neighboring elements.

1 Like

Oh, yes, thatâ€™s an improvement as it uses the implementation of Array to potentially reduce the number of allocations

A silly solution would be to use the keys of a Dict to be the ordering and then space them out, renumbering if you run out of slots.

Which is how one did line numbering in BASIC in the 80s

``````julia> a = Dict(10=>1, 20=>2, 30=>3, 40=>4, 50=>5);

julia> map(k->a[k], sort(collect(keys(a))))
5-element Vector{Int64}:
1
2
3
4
5

julia> a[25] = 10;

julia> map(k->a[k], sort(collect(keys(a))))
6-element Vector{Int64}:
1
2
10
3
4
5

julia> delete!(a, 20);

julia> map(k->a[k], sort(collect(keys(a))))
5-element Vector{Int64}:
1
10
3
4
5

``````