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

[Micha Nelissen]

On Wed, 14 Dec 2005 21:53:58 +0100
Mattias Gaertner <nc-gaertnma at netcologne.de> wrote:

> 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.

You may be underestimating the impact of the heap manager. I just checked
the code in lists.inc. When there are less than 128 items, the list is
increased by 8 items. So when adding 1000 (to take a number) items, the list
is copied at least 10, possibly 13 times, 12 -> 28 -> 44 -> 60 -> 76 -> 92
-> 108 -> 124 -> 140 -> 206 -> 325 -> ~500 -> ~780 -> ~1000. For the linked
list case, no memory is copied.

Sure, if you're going to sort a list, you should not use linked list of
course, but an array (or tree maybe).

Due to memory fragmentation, it is debatable whether memory usage will
really grow significantly more for linked list.

Micha