Recommended data structure in Julia for efficient append

Question

What is the ideal list-like data structure in Julia?

I want an indexible, growable, collection with a constant-time append operation.

The standard data structure seems to be Array with the push! operation. Is this constant time?

Answer 1

As Harlan said, push! is amortized constant time. See the description of C++'s similar data structure for arguments why: Amortized analysis of std::vector insertion

If you want a legitimately constant time data structure, you probably want to implement a linked list. I've seen lots of sample implementations, but nothing that's ready for production.

Answer 2

Repeatedly calling push! is not constant time, but it's pretty fast. It does an occasional exponential reallocation of the buffer. See the C source for appending to an array: https://github.com/JuliaLang/julia/blob/master/src/array.c#L564

Answer 3

Difference lists let you append, prepend, and concatenate in constant time. I pushed an implementation yesterday here. It's really just a few lines of code but I made it fancier by adding in support for iteration and display.

You create a difference list with the dl function, like this: dl(1, 2, 3) or make a difference list for anything you can iterate with todl(items).

You can concatenate any number of difference lists in constant time with the concat function, like this: concat(dl(1, 2), dl(3, 4)).

You can use pushfirst and push to add to the start and end in constant time.

Difference lists can iterate so you can use them in for-loops and splats and easily convert them to arrays.

I'm waiting for it to get published as a Julia package but you can just use the DifferenceLists.jl file directly.