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

General Usage
1

The idea is that:

N = 4

cur_array_1 = zeros(N)

is fast, but pushing/popping will start at the end

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

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

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 pushing and popping from the beginning – i.e. a growing array that is rpadded by 0’s?

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?

2

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

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

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

My bad, the desired behavior for cur_array_3 should be:

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

4

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

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