On Wed, 14 Dec 2005, 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. 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. Michael. _______________________________________________ fpc-devel maillist - [email protected] http://lists.freepascal.org/mailman/listinfo/fpc-devel
