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

[Mattias Gaertner]

On Wed, 14 Dec 2005 21:33:34 +0100
Micha Nelissen <micha at neli.hopto.org> wrote:

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

This will break all random access uses. For example sorting a TList.

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

TFPList/TList grows exponentially, which is pretty good for a generic
dynamic array. It results in O(n).

 
> Using aggregation possibly, TStringList must benefit from it too.
> 
> What do you think about it ?

Your trick will only give a constant factor on growing/shrinking the list
memory, gives an extra O(n) factor for sorting a TList, the caching costs
time, and the memory usage will also grow.


Mattias