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