# Is there a fixed-length array list with support for push/pop'ing from start?

**URL:** <https://discourse.julialang.org/t/is-there-a-fixed-length-array-list-with-support-for-push-poping-from-start/21434>\
**Category:** General Usage\
**Tags:** question\
**Created:** [March 3, 2019, 9:22pm UTC](https://discourse.julialang.org/t/is-there-a-fixed-length-array-list-with-support-for-push-poping-from-start/21434 "2019-03-03T21:22:22Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![djsegal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djsegal/32/13752_2.png) [@djsegal](https://discourse.julialang.org/u/djsegal)\
**Post date:** [March 3, 2019, 9:22pm UTC](https://discourse.julialang.org/t/is-there-a-fixed-length-array-list-with-support-for-push-poping-from-start/21434/1 "2019-03-03T21:22:22Z")

</div>

The idea is that:

```julia
N = 4

cur_array_1 = zeros(N)

```

is fast, but `push`ing/`pop`ping will start at the end

```julia
> push!(cur_array_1, 1)
[0 0 0 0 1]

```

* * *

A more useful data structure would then be an array list:

```julia
cur_array_2 = []

> push!(cur_array_2, 1)
[1]

```

* * *

This begs the question, is there a fixed-length array-list data structure that stores a `cur_index` to allow `push`ing and `pop`ping from the beginning – i.e. a growing array that is `rpad`ded by 0’s?

```julia
cur_array_3 = ArrayList(N)

> cur_array_3
[0 0 0 0]

> push!(cur_array_3, 42)
[42 0 0 0]

> pop!(cur_array_3)
42

> append!(cur_array_3, [4 , 0 , 2])
[4 0 2 0]

```

// also, what would be the obvious complications of using this data structure?

---

<div class="post-metadata">

**Author:** ![dfdx](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dfdx/32/120_2.png) [@dfdx](https://discourse.julialang.org/u/dfdx)\
**Post date:** [March 3, 2019, 9:45pm UTC](https://discourse.julialang.org/t/is-there-a-fixed-length-array-list-with-support-for-push-poping-from-start/21434/2 "2019-03-03T21:45:16Z")

</div>

First of all, both `zeros()` and `[]` create the same data structure - ordinary Julia array - although with different type parameters:

```julia
julia> typeof(cur_array_1)
Array{Float64,1}

julia> typeof(cur_array_2)
Array{Any,1}

```

Second, arrays in Julia support efficient pushing to both ends of the array:

```julia
julia> using BenchmarkTools

# create 2 arrays of Float64
julia> a1 = Float64[];
julia> a2 = Float64[];

# benchmark pushing to the end
julia> @btime push!($a1, 1.0);
  7.245 ns (0 allocations: 0 bytes)

julia> size(a1)
(10490502,)

julia> @btime pushfirst!($a2, 1.0);
  7.475 ns (0 allocations: 0 bytes)

julia> size(a2)
(10490502,)

```

And you example:

```julia
cur_array_3 = zeros(Int, 4)
pushfirst!(cur_array_3, 42)
# 5-element Array{Int64,1}:
# 42
# 0
# 0
# 0
# 0

```

---

<div class="post-metadata">

**Author:** ![djsegal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djsegal/32/13752_2.png) [@djsegal](https://discourse.julialang.org/u/djsegal)\
**Post date:** [March 3, 2019, 9:46pm UTC](https://discourse.julialang.org/t/is-there-a-fixed-length-array-list-with-support-for-push-poping-from-start/21434/3 "2019-03-03T21:46:15Z")

</div>

My bad, the desired behavior for `cur_array_3` should be:

```julia
cur_array_3 = ArrayList(N)

> push!(cur_array_3, 4)
[4 0 0 0]

> push!(cur_array_3, 0)
[4 0 0 0]

> push!(cur_array_3, 2)
[4 0 2 0]

```

// `pushfirst!` would result in [2 0 4 0] – and increase length by 3 **if** used on an ordinary array

---

<div class="post-metadata">

**Author:** ![dfdx](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dfdx/32/120_2.png) [@dfdx](https://discourse.julialang.org/u/dfdx)\
**Post date:** [March 3, 2019, 10:56pm UTC](https://discourse.julialang.org/t/is-there-a-fixed-length-array-list-with-support-for-push-poping-from-start/21434/4 "2019-03-03T22:56:38Z")

</div>

Ah, I see, thanks for clarification. I don’t know any existing data structure for it, but it seems pretty easy to implement:

```julia
mutable struct ArrayList{T}
    data::Vector{T}
    idx::Int
end

function Base.push!(a::ArrayList, x)
    if a.idx >= length(a.data)           
        error("ArrayList is full, can't push new values")
    else
         a.idx += 1
         a.data[a.idx] = x
    end
end

```

which gives us:

```julia
julia> cur_array_3 = ArrayList(Int, 4)
ArrayList{Int64}([0, 0, 0, 0], 0)

julia> push!(cur_array_3, 4)
4

julia> push!(cur_array_3, 0)
0

julia> push!(cur_array_3, 2)
2

julia> cur_array_3.data
4-element Array{Int64,1}:
 4
 0
 2
 0

```