# Is Julia Array an array or linked list?

**URL:** <https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954>\
**Category:** New to Julia\
**Tags:** question\
**Created:** [February 21, 2020, 7:42am UTC](https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954 "2020-02-21T07:42:53Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Sijun](https://avatars.discourse-cdn.com/v4/letter/s/b2d939/32.png) [@Sijun](https://discourse.julialang.org/u/Sijun)\
**Post date:** [February 21, 2020, 7:42am UTC](https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954/1 "2020-02-21T07:42:53Z")

</div>

My understanding is that a data structure cannot be an array for random access and a linked list for sequential access at the same time. There must be two different data structures for dedicated purposes.

But the following result shows that Julia `Array` behaves both as an array and a linked list:

`Array` shows constant insertion time at front/end.

```julia
julia> using BenchmarkTools

julia> a = rand(10^3); @btime push!($a, 1);
  7.499 ns (0 allocations: 0 bytes)

julia> a = rand(10^6); @btime push!($a, 1);
  7.400 ns (0 allocations: 0 bytes)

julia> a = rand(10^9); @btime push!($a, 1);
  7.499 ns (0 allocations: 0 bytes)
  
julia> a = rand(10^9); @btime pushfirst!($a, 1);
  6.899 ns (0 allocations: 0 bytes)

julia> a = rand(10^6); @btime pushfirst!($a, 1);
  6.899 ns (0 allocations: 0 bytes)

julia> a = rand(10^5); @btime pushfirst!($a, 1);
  6.899 ns (0 allocations: 0 bytes)

```

Whereas below shows constant random access time:

```julia
julia> a = rand(10^3); @btime $a[Int(end/2)]
  4.499 ns (0 allocations: 0 bytes)
0.7178230501269474

julia> a = rand(10^6); @btime $a[Int(end/2)]
  4.499 ns (0 allocations: 0 bytes)
0.4156162488532731

```

How can this be possible?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 21, 2020, 7:50am UTC](https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954/2 "2020-02-21T07:50:25Z")

</div>

Note that in Julia terminology, you are talking about `Vector`, which is `Array{T,1}` (some languages without [multidimensional arrays](https://docs.julialang.org/en/v1/manual/arrays/) do call vectors arrays, but not Julia).

Julia allows `Vector`s to be extended, and clever overallocation heuristics make it fast.

---

<div class="post-metadata">

**Author:** ![Sijun](https://avatars.discourse-cdn.com/v4/letter/s/b2d939/32.png) [@Sijun](https://discourse.julialang.org/u/Sijun)\
**Post date:** [February 21, 2020, 8:00am UTC](https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954/3 "2020-02-21T08:00:17Z")

</div>

Thank you for the explanation. Yes, I was talking about `Vector`. Right, It is indeed a random access array but with extra efficiency and I just came to know that it takes a lot more time if I try inserting at a middle position, which shows it is basically an array (like in C and Java).

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 21, 2020, 8:10am UTC](https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954/4 "2020-02-21T08:10:33Z")

</div>

Note that you do not need to find out these things indirectly by benchmarking; all the data structures in `Base` are documented (even though for performance models you may have to dig a bit deeper).

If you need other data structures, I would recommend

> **[GitHub - JuliaCollections/DataStructures.jl: Julia implementation of Data...](https://github.com/JuliaCollections/DataStructures.jl)**
>
> Julia implementation of Data structures. Contribute to JuliaCollections/DataStructures.jl development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![ismedina](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ismedina/32/26433_2.png) [@ismedina](https://discourse.julialang.org/u/ismedina)\
**Post date:** [September 4, 2020, 7:37am UTC](https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954/5 "2020-09-04T07:37:49Z")

</div>

Hi! I was also wondering about the data structure behind Julia’s `Vector` and found this discussion very helpful! I wasn’t able to find this info elsewhere.

I have a final question just to dissipate any shadow of doubt: as far as I know, in C++ the elements of a `std::vector` are allocated in a single chunk of memory and you can insert elements with constant time overhead _only at the end_ of it ([vector - C++ Reference](http://www.cplusplus.com/reference/vector/vector/)). On the other hand, a `std::deque` allows insertions in constant time at the beginning and at the end but can have the elements scattered in different chunks of memory ([deque - C++ Reference](http://www.cplusplus.com/reference/deque/deque/)). Both allow for random access, and one could expect vectors to be slightly faster (I don’t know if this is noticeable though).

My question then is: is the data structure behind `Vector` in Julia more like a `std::vector` or like a `std::deque`?

Thanks a lot!!

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 5, 2020, 1:00pm UTC](https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954/6 "2020-09-05T13:00:55Z")

</div>

8 posts were split to a new topic: [1d arrays vs 1-column matrices](https://discourse.julialang.org/t/1d-arrays-vs-1-column-matrices/46101)

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 4, 2020, 10:22am UTC](https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954/7 "2020-09-04T10:22:37Z")

</div>

> [@1d arrays vs 1-column matrices](https://discourse.julialang.org/t/1d-arrays-vs-1-column-matrices/46101/1):
>
> Does this mean that storing vectors as x(n,) rather than x(n,1) has performance benefits?

I am sorry but I don’t understand the question. Generally for `Vector{T}` you don’t get to choose a storage model for a given `T`.

> [@ismedina](#):
>
> My question then is: is the data structure behind `Vector` in Julia more like a `std::vector` or like a `std::deque` ?

`Vector{T}` is not necessarily optimal for `pushfirst!` — again, if you want a deque, use a deque. AFAIK neither is “scattered in different chunks”.

FWIW, I don’t find it helpful to think about the data structure “behind” `Vector` when programming Julia. `Array`s are _the_ data structure _per se_.

---

<div class="post-metadata">

**Author:** ![pfitzseb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pfitzseb/32/45566_2.png) [@pfitzseb](https://discourse.julialang.org/u/pfitzseb)\
**Post date:** [September 4, 2020, 10:26am UTC](https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954/8 "2020-09-04T10:26:00Z")

</div>

FWIW, Julia’s `Array` type is smart about insertions at either end (the usual tactic of growing the array more than requested is applied to both `push!` and `pushfirst!`), but it’s still always a contiguous chunk of memory.

---

<div class="post-metadata">

**Author:** ![ctkelley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ctkelley/32/10684_2.png) [@ctkelley](https://discourse.julialang.org/u/ctkelley)\
**Post date:** [September 5, 2020, 11:26am UTC](https://discourse.julialang.org/t/is-julia-array-an-array-or-linked-list/34954/16 "2020-09-05T11:26:33Z")

</div>

That’s exactly what I needed. Thanks!