On Sun, Nov 22, 2020 at 10:43 PM Taylan Kammer <taylan.kam...@gmail.com> wrote: > > Python lists, JDK's ArrayList, and .NET ArrayList, among probably many > other "list" or "array" data structures in popular languages nowadays > use a relatively straightforward data structure that is backed by an > actual array which can have empty slots (e.g. your Python list with 3 > elements might be backed by an array of size 10), and is reallocated > whenever there's no space left. This means that appending an element at > the end is usually dirt cheap, until there's no space left, at which > point the append operation is much heavier for one call, then the > following calls are dirt cheap again, until it's full again... > > Inserting an element at the beginning or middle is also relatively > expensive with those implementations, since all elements need to be > shifted forward to make space for the new element. (Although this might > be done with an operation like C's memcpy which is still actually very > fast.) > > It's called a "dynamic array" by Wikipedia: > > https://en.wikipedia.org/wiki/Dynamic_array > > If you want to go on an adventure, you could implement a Scheme data > structure called DVector that implements this strategy, using plain > Scheme vectors for the backing array.
If anyone is interested in such a data structure, I have an implementation available here: https://git.dthompson.us/chickadee.git/tree/chickadee/array-list.scm I typically use them as object pools to reduce allocation and thus GC pressure in the context of video games. The array-list-push! and array-list-pop! procedures make it easy to use as a dynamically expanding stack. - Dave
