'Chunked' Linked List?

I know about Vector / immutabe::Vector. I am looking for O(1) push and O(1) iterator. I don't need fast indexing.

In my current understanding of Vec's push behaviour, when we hit the capacity and try to push item (n+1), it reallocates a Vector of capacity size 2*n, and moves over the first n items.

I am looking for something else -- where when it hits capacity, it just allocates a 4KB or 8KB or ... page, so the structure ends up being a "linked list of chunks", where each chunk is a fixed capacity array.

Is there a builtin for this ?

1 Like

The blist crate has a simple implementation of something like this, which internally uses a LinkedList<VecDeque>.

1 Like