Re: Question about data structures

[John Cowan <cowan@ccil.org>]

On Sun, Nov 22, 2020 at 10:43 PM Taylan Kammer <taylan.kammer@gmail.com>
wrote:

Since your main concern seems to be appending, you could simply use a
> linked list where you keep a reference to the last cons pair (tail) of
> the list, so appending is simply a matter of a 'set-cdr!' operation on
> the tail.
>

SRFI 117, List Queues, does exactly that.

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

And the recent SRFI 214, Flexvectors, provides exactly this.

Packaging these two SRFIs for Guile would be a Good Thing.



John Cowan          http://vrici.lojban.org/~cowan        cowan@ccil.org
The present impossibility of giving a scientific explanation is no proof
that there is no scientific explanation. The unexplained is not to be
identified with the unexplainable, and the strange and extraordinary
nature of a fact is not a justification for attributing it to powers
above nature.  --The Catholic Encyclopedia, s.v. "telepathy" (1913)