<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
Mattias Gaertner wrote:
<blockquote cite="mid20051214215358.65fceb48@limapholos.matom.wg"
 type="cite">
  <pre wrap="">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.
  </pre>
</blockquote>
Just saw this last statement.  The memory usage is very comparable to
TList, even with bi-directional (doubly-linked) lists, since TLists
tend to grow by leaps.<br>
<br>
For example, assuming a linked list item comprises of only a "next"
pointer, it requires 8 bytes of memory (4 for the structure itself, 4
for the next pointer).  In this case, 10,000 entries occupy 80,008
bytes (80,000 + 4 for pointer to First + 4 for pointer to Last),
distributed around the memory table.  Also keep in mind that the data
payload for the linked list item is usually contained within the
structure itself.<br>
<br>
A TList (stripped down for this case) requires 4 bytes for the list
allocation, plus 4 bytes per list entry.  10,000 entries occupy 80,004
bytes.  Now, two things:<br>
<br>
1. With automatically growing lists you have a very high likelihood of
unused pointers, so while a linked list of 10,000 items is utilizing
all 80,004 bytes of memory, the TList allocated (10,000-TList.Count)*4
unused bytes of memory.<br>
<br>
2. The TList entry only points to the actual data payload, meaning
another 4+<i>n</i> bytes must be allocated to store the data.  This
means an additional 40,000 bytes is required for a TList vs. a linked
list.  On the other hand, this is equalized in a doubly-linked list.<br>
<br>
Disclaimer: this is all based on the Delphi implementation of TList,
and may differ slightly (but probably not much) for the FP lists.<br>
<br>
Sterling<br>
</body>
</html>