[fpc-devel] TList or TFPList - a Linked list ?
Michael Van Canneyt
michael at freepascal.org
Wed Dec 14 22:09:55 CET 2005
On Wed, 14 Dec 2005, Micha Nelissen wrote:
> 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.
I strongly disagree here. I use T(FP)List quite a lot, and usually do a good
estimate in setting the capacity. When storing/reading items of a list you
always write/read the count first...
People that have large lists know this and take care of it.
What is more, I think that 1 large memory block (an array) is much more
efficient memory wise than many small blocks.
> Using aggregation possibly, TStringList must benefit from it too.
No way, e.g. the IndexOf for sorted stringlists would be crippled totally.
Inside TList, The Move()/Exchange operations would be a horror, and hence
the listsort as well.
> What do you think about it ?
I think it's a bad idea. TFPList is implemented for speed and does very well.
But, on the bright side: A TLinkedList implementation is more than welcome,
but it should be a separate class. LinkedLists and the regular List are 2
different beasts, that only have in common that they store a lot of pointers.
More information about the fpc-devel