Delphi 中的“TList”对象与它的“items[i]”属性有点混淆。此属性暗示 TList 可能会在某种数组中内部索引其所有列表项。
我完全知道，尽管这样的索引属性可以在对象内部任意处理（在这种情况下，例如假设通过线性遍历整个链表直到使用提供的索引命中项目），所以我的问题是：以下哪个替代方案是真实的：
1. TList 确实在某种（动态）数组中对其项目进行内部索引，因此具有任意索引的列表项查找将具有 O(1) 时间复杂度（即常数），而列表项添加将具有 O(n ) 复杂性（即线性），因为在扩展大小时必须重新分配数组。
2. TList 不会在某种（动态）数组中对其项目进行内部索引，因此具有任意索引的列表项查找将具有 O(n) 时间复杂度（即线性），而添加的列表项将具有 O(1 ) 复杂性（即常数）。
3. 另一个第三种选择，在这种情况下，非常欢迎您解释查找（按索引）和插入操作的时间复杂度。
RTL 的源代码可通过购买 Delphi 获得，因此很容易知道实际发生了什么。
在幕后，项目在一个动态数组中进行管理，该数组会随着您向其中添加项目而增长，但其方式比每次添加新项目时简单地增长 1 更智能。这意味着后备数组通常比对象Count中的项目大TList，因此索引是一种O(1)操作，添加通常O(1)也是如此。（特别是因为 FastMM 内存管理器通常可以在数组增长时就地重新分配数组，尤其是在较小的大小时，因此不需要复制。）但是当后备数组必须增长并被内存管理器复制时，它将是一次O(n)手术。
Insert另一方面，一个操作（插入到列表的中间，而不是添加到末尾）是一个O(n)操作，因为它必须将插入点之后的所有内容向前移动一个。
正如@SirRufo 指出的那样，该Capacity属性在这里是相关的：它是支持数组的大小。如果Count = Capacity并且您尝试Add使用新值，那么它将不得不调整数组的大小。
DelphiTList是一个封装数组的类。所以它的操作复杂度和数组一样。随机访问是 O(1)。对于操作的复制部分，插入是 O(n)。与插入相关的内存分配更难分析，并且取决于许多因素。我不确定由于 thois 分析插入的时间复杂度是否真的很容易处理。
顺便说一句，从计算机科学的角度来看，Delphi 的列表类不是列表，这让我一直很沮丧。它们是数组。