Data structure for inserting and removing in the middle?

New to Julia
,
1

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?

2

Maybe a doubly linked list?

There’s an implementation in DataStructures.jl:

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

(see under Mutable Linked List)

3

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
4

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.

It’s a tradeoff which is “best”, depending on your context.

1 Like
5

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

6

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