[fpc-devel] TList or TFPList - a Linked list ?

[Micha Nelissen]

Hi,

I've been thinking about adding a linked list implementation to either TList
or TFPList. The basic problem to that is of course
1) space overhead of linked list is quite large
2) Index[..] will be O(N)

For (1) I was thinking about making a linked list of an array of items, for
example 14 pointers (so that 8 bytes are left for next pointer and memory
manager needs on 32 bit platform). 

To solve (2), we can make the observation
that generally people access lists in a linear fashion, and we might cache
the previous and next list entry.

The big advantage is getting rid of the many reallocs needed to grow
the lists, because one usually doesn't set Capacity in advance, but keeps
adding items until done.

Using aggregation possibly, TStringList must benefit from it too.

What do you think about it ?

Micha