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

Daniël Mantione daniel.mantione at freepascal.org
Wed Dec 14 21:44:50 CET 2005

Op Wed, 14 Dec 2005, schreef 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 ?

Sorry to disappoint, but this doesn't look a very good idea to me; it 
would kill code that for example tries to sort a list. There will be also 
a lot of code that iterates using index[].

Programmers need both list like datastructures and array like data 
structures. It is part of converting mathematical abstraction principles 
like a sequence where every operation is O(1), to actual datastructures 
that are to be used inside a compiler. Programmers need both of them, not 
one or the other.


More information about the fpc-devel mailing list