# Data structure for inserting and removing in the middle?

**URL:** <https://discourse.julialang.org/t/data-structure-for-inserting-and-removing-in-the-middle/82032>\
**Category:** New to Julia\
**Tags:** question, data\_structures\
**Created:** [June 1, 2022, 6:45am UTC](https://discourse.julialang.org/t/data-structure-for-inserting-and-removing-in-the-middle/82032 "2022-06-01T06:45:02Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![chkwon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chkwon/32/3632_2.png) [@chkwon](https://discourse.julialang.org/u/chkwon)\
**Post date:** [June 1, 2022, 6:45am UTC](https://discourse.julialang.org/t/data-structure-for-inserting-and-removing-in-the-middle/82032/1 "2022-06-01T06:45:02Z")

</div>

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

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

```

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

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

```

or remove an element in the middle to make it

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

```

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

---

<div class="post-metadata">

**Author:** ![maxkapur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/maxkapur/32/21208_2.png) [@maxkapur](https://discourse.julialang.org/u/maxkapur)\
**Post date:** [June 1, 2022, 6:52am UTC](https://discourse.julialang.org/t/data-structure-for-inserting-and-removing-in-the-middle/82032/2 "2022-06-01T06:52:00Z")

</div>

Maybe a doubly linked list?

> **[Doubly linked list](https://en.m.wikipedia.org/wiki/Doubly_linked_list)**
>
> In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then t...

There’s an implementation in DataStructures.jl:

[https://juliacollections.github.io/DataStructures.jl/stable/](https://juliacollections.github.io/DataStructures.jl/stable/)

(see under Mutable Linked List)

---

<div class="post-metadata">

**Author:** ![lawless-m](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lawless-m/32/30869_2.png) [@lawless-m](https://discourse.julialang.org/u/lawless-m)\
**Post date:** [June 1, 2022, 7:05am UTC](https://discourse.julialang.org/t/data-structure-for-inserting-and-removing-in-the-middle/82032/3 "2022-06-01T07:05:11Z")

</div>

I suppose it depends on what your definition of “best” is

because this works just fine, although it reallocates every time

```julia
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.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [June 1, 2022, 7:56am UTC](https://discourse.julialang.org/t/data-structure-for-inserting-and-removing-in-the-middle/82032/4 "2022-06-01T07:56:36Z")

</div>

> [@lawless-m](#):
>
> because this works just fine, although it reallocates every time

Note that this could be written using [`insert!`](https://docs.julialang.org/en/v1/base/collections/#Base.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.

---

<div class="post-metadata">

**Author:** ![lawless-m](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lawless-m/32/30869_2.png) [@lawless-m](https://discourse.julialang.org/u/lawless-m)\
**Post date:** [June 1, 2022, 7:59am UTC](https://discourse.julialang.org/t/data-structure-for-inserting-and-removing-in-the-middle/82032/5 "2022-06-01T07:59:58Z")

</div>

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

> <https://github.com/JuliaLang/julia/blob/742b9abb4dd4621b667ec5bb3434b8b3602f96fd/base/array.jl#L1393-L1400>

---

<div class="post-metadata">

**Author:** ![lawless-m](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lawless-m/32/30869_2.png) [@lawless-m](https://discourse.julialang.org/u/lawless-m)\
**Post date:** [June 1, 2022, 8:10am UTC](https://discourse.julialang.org/t/data-structure-for-inserting-and-removing-in-the-middle/82032/6 "2022-06-01T08:10:34Z")

</div>

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
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

```