The "TList" object in Delphi confuses me a bit with its "items[i]" property. This property hints that the TList might internally index all its list items in some kind of array.
I am fully aware though that such indexed properties can be handled arbitrarily inside objects (in this case e.g. hypothetically by traversing the entire linked list linearly until hitting the item with the provided index), so my question is therefore: Which of the following alternatives is the true one:
1. TList does indeed internally index its items in some kind of (dynamic) array, and list item lookups with arbitrary indexes will therefore have a O(1) time complexity (i.e. constant), whereas list item adds will have a O(n) complexity (i.e. linear), since the array will have to be reallocated when expanded in size.
2. TList does NOT internally index its items in some kind of (dynamic) array, and list item lookups with arbitrary indexes will therefore have a O(n) time complexity (i.e. linear), whereas list item adds will have a O(1) complexity (i.e. constant).
3. Another third alternative, which you in this case are very welcome to explain the time complexity of when it comes to lookup (by index) and insert operations.
The source code to the RTL is available with a purchase of Delphi, so it's easy to tell what's actually going on.
Under the hood, items are managed inside a dynamic array that grows as you add items to it, but in a more intelligent fashion than simply growing by 1 with each new addition. This means that the backing array will usually be larger than the Count of items in the TList object, and so indexing is a O(1) operation and additions are usually O(1) as well. (Especially since the FastMM memory manager can often reallocate an array in-place when it grows, especially at smaller sizes, so there's no copying required.) But when the backing array has to grow and be copied by the memory manager, it will be an O(n) operation.
An Insert operation, on the other hand (inserting into the middle of the list, rather than adding on to the end) is an O(n) operation because it has to move everything after the insertion point forward by one.
As @SirRufo pointed out, the Capacity property is relevant here: it's the size of the backing array. If Count = Capacity and you try to Add a new value, that's when it will have to resize the array.