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

[Sterling Bates]

Micha Nelissen 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.
>
>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
>_______________________________________________
>fpc-devel maillist  -  fpc-devel at lists.freepascal.org
>http://lists.freepascal.org/mailman/listinfo/fpc-
>
My most recent project at work involves a good deal of non-linear access 
to TList items (sorry, not Free Pascal <g>), and this implementation 
would essentially kill the efficiency gains that we achieved by doing 
so.  In addition, the caching overhead (the last requested index, as 
well as next & prev pointers, and corresponding logic) would blow away 
the efficiency of iterating through TList items.  There's no way to work 
around that.

Linked lists are very specialized, and definitely have their place, and 
classes should be built for them.  However, they're definitely their own 
beast, and should be treated as such.  For instance, you made the valid 
point that they grow very easily and without the overhead of having to 
find large contiguous chunks of memory when the list grows, but 
iterating them is relatively slow.  Programmers just need to recognize 
when this is an advantage and when it isn't.

Just my $0.02.