Unity List的底层实现及部分方法的底层实现

目录

底层实现

常用方法

优点和缺点

        优点

        缺点

底层实现

Unity 的 List 类型使用了一个连续的内存块来存储元素，并通过数组的索引来访问和操作这些元素。当我们向 List 中添加元素时，如果当前的内部数组容量不足以容纳新的元素，Unity 会自动分配更大的内存块，并将旧的元素复制到新的内存中，这个过程被称为扩容。通常情况下，每次扩容时，Unity 会将内部数组的大小增加一倍，以减少频繁的扩容操作。

常用方法

• Add(item)：向 List 的末尾添加一个元素。如果当前的容量不足以容纳新的元素，会触发扩容操作。底层实现会将新元素追加到内部数组的末尾，并更新列表的长度。
• Remove(item)：从 List 中移除指定的元素。底层实现会遍历整个 List，找到第一个匹配的元素并将其删除。此操作可能会导致后续元素的前移，因此时间复杂度为 O(n)。
• Insert(index, item)：在指定的索引位置插入一个元素。底层实现会将索引位置之后的元素向后移动一位，为新元素腾出空间，并将其放置在正确的位置上。此操作可能会导致后续元素的后移，因此时间复杂度为 O(n)。
• Clear()：清空 List 中的所有元素。底层实现会将列表的长度设置为 0，但不会释放内部数组的内存。
• Contains(item)：判断 List 是否包含指定的元素。底层实现会遍历整个 List，逐个比较元素和目标元素。此操作的平均时间复杂度为 O(n)。
• Find(Predicate<T> match)：根据指定的条件在 List 中查找符合条件的第一个元素，并返回该元素。底层实现会遍历整个 List，逐个比较元素和条件。此操作的平均时间复杂度为 O(n)。
• FindAll(Predicate<T> match)：根据指定的条件在 List 中查找符合条件的所有元素，并返回一个新的 List。此操作会遍历整个 List，逐个比较元素和条件。时间复杂度为 O(n)。
• ForEach(Action<T> action)：对 List 中的每个元素执行指定的操作。底层实现使用简单的循环来遍历并逐个应用操作函数。
• RemoveAt(index)：移除指定索引位置处的元素。底层实现会将索引之后的元素向前移动一位，覆盖需要删除的元素，并更新列表的长度。此操作会导致后续元素的前移，因此时间复杂度为 O(n)。
• ToArray()：将 List 中的元素复制到一个新的数组中，并返回该数组。底层实现会创建一个新的数组，并将 List 中的元素逐个复制到新数组中。

此外，List 还提供了一些用于排序和反转列表的方法：

• Sort()：对 List 中的元素进行排序。Unity 使用快速排序算法来实现这个方法，具有较高的效率。排序的时间复杂度为 O(n log n)。
• Reverse()：反转 List 中元素的顺序。底层实现会将第一个元素与最后一个元素交换位置，以此类推，直到完成整个列表的反转。

优点和缺点

        优点

1. 动态调整大小：List 具有自动扩容的能力，可以根据需要动态调整内部数组的大小，以适应元素的添加或删除操作。这使得 List 可以灵活地处理不确定数量的元素。

2. 随机访问：由于底层使用数组实现，List 支持通过索引进行随机访问，即可以直接访问任意位置的元素。这种随机访问的特性使得对元素的读取和写入操作非常高效，时间复杂度为 O(1)。

3. 线性迭代：使用 for 循环等方式可以对 List 进行线性迭代，以遍历其中的元素。这种迭代的方式比较简单且高效。

        缺点

1. 元素插入和删除效率低：由于底层是连续内存块，当需要在中间位置插入或删除一个元素时，会引发一系列元素的后移或前移操作，导致时间复杂度为 O(n)。因此，频繁的插入和删除操作可能会影响性能。

2. 内存开销：List 在内存上以连续的数组形式存储元素，如果需要存储大量元素，而其中只有很少一部分是活动的，可能会造成一定的内存浪费。

3. 不支持快速查找：由于 List 是基于数组实现的，它并不提供像字典（Dictionary）那样快速的查找功能。对于需要频繁进行查找操作的场景，使用 List 可能会导致性能下降。

综上所述，List 作为动态数组的实现，在处理元素的添加、删除和随机访问时具有显著的优势，但在频繁的插入和删除操作以及快速查找需求方面可能存在一些缺点。根据具体的使用情况和性能需求，我们可以选择合适的数据结构来满足开发的要求。