On Wed, 14 Dec 2005 21:33:34 +0100 Micha Nelissen <[EMAIL PROTECTED]> 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 _______________________________________________ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel