ArrayList vs LinkedList

2025年3月17日 | 阅读 7 分钟

引言

在编程世界中，数据结构在高效地组织和管理数据方面发挥着至关重要的作用。在许多编程语言中，ArrayList 和 LinkedList 是最常用的数据结构之二。这两种数据结构的目的相似，但在性能、内存使用和用例方面却存在显著差异。

什么是 ArrayList？

ArrayList 是一种基于动态数组的数据结构。它是 Java 标准集合框架的一部分，并且在许多其他编程语言中也可用。ArrayList 可以动态地调整其容量，允许在初始化时无需固定大小即可添加和删除元素。

内部机制

在内部，ArrayList 使用一个常规数组来存储元素。当元素数量超过数组的当前容量时，它会自动调整大小，方法是创建一个具有更大尺寸的新数组，并将旧数组中的所有元素复制到新数组中。此调整大小过程会产生少量开销，但它确保 ArrayList 可以有效地管理不同数量的元素。

程序

#include <iostream>
#include <vector>
int main() {

    std::vector<int> arrayList; // Creating an ArrayList
    // Adding elements to the ArrayList

    arrayList.push_back(10);
    arrayList.push_back(20);
    arrayList.push_back(30);


    // Accessing elements using index-based random access

    std::cout << "Element at index 1: " << arrayList[1] << std::endl; // Output: 20

    // Iterating through the ArrayList

    std::cout << "ArrayList elements: ";

    for (int i : arrayList) {

        std::cout << i << " ";

    }
    std::cout << std::endl;
    return 0;

}

说明

该程序定义了 main 函数，该函数作为程序的入口点。
在 main 函数内部，声明了一个 std::vector<int> arrayList，用于存储一个整数列表。
程序使用 push_back 向 arrayList 添加元素。将三个整数 10、20 和 30 添加到 arrayList 中。
接下来，程序演示了使用基于索引的随机访问来访问 arrayList 中的元素。
在这种情况下，访问索引 1（即第二个元素，因为索引从 0 开始）处的元素，并使用 std::cout 将其打印到控制台。
然后，程序使用基于范围的 for 循环遍历 arrayList。
此循环逐个迭代 arrayList 中的每个元素，并且循环变量 i 在每次迭代中获取每个元素的值。在循环内部，每个元素都打印到控制台，并用空格分隔。
打印完 arrayList 的所有元素后，程序会在控制台添加一个换行符 (std::endl) 来结束输出。

程序输出

ArrayList 的优点

快速随机访问：ArrayList 通过索引提供对元素的恒定时间访问。由于元素存储在连续的内存块中，因此使用索引访问元素是一个直接操作，其时间复杂度为 O(1)。
高效内存分配：ArrayList 使用单个连续的内存块来存储元素。此功能可减少内存开销，并允许更好的缓存性能，因为元素在内存中是相邻存储的。

ArrayList 的缺点

昂贵的插入和删除：在 ArrayList 的中间插入或删除元素可能会很昂贵。当插入或删除元素时，所有后续元素都需要向右移动，导致时间复杂度为 O(n)。

什么是 LinkedList？

LinkedList 是一种数据结构，由一系列节点组成，每个节点包含一个元素以及指向序列中下一个节点的引用（或指针）。与 ArrayList 不同，LinkedList 不使用连续内存分配。相反，它允许元素分散在不同的内存位置，并且节点通过指针连接。

内部机制

LinkedList 中的每个节点包含两部分：数据（元素）和指向序列中下一个节点的引用。最后一个节点的引用通常设置为 null，以指示列表的末尾。

程序

#include <iostream>
#include <list>
int main() {

    std::list<int> linkedList; // Creating a LinkedList

    // Adding elements to the LinkedList
    linkedList.push_back(10);
    linkedList.push_back(20);
    linkedList.push_back(30);

// Accessing elements (inefficient random access)
    auto it = linkedList.begin();
    std::advance(it, 1);
    std::cout << "Element at index 1: " << *it << std::endl; // Output: 20
  
  // Iterating through the LinkedList
    std::cout << "LinkedList elements: ";
    for (int i : linkedList) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    return 0;

}

说明

该程序定义了 main 函数，该函数作为程序的入口点。
在 main 函数内部，声明了一个名为 linkedList 的 std::list<int>，用于存储一个整数链表。
程序使用 push_back 向 linkedList 添加元素。使用 push_back 将三个整数 10、20 和 30 添加到链表中，它会在列表末尾插入元素。
为了演示访问 linkedList 中的元素，程序执行基于索引的访问，尽管链表并未针对此类访问进行优化。
创建了一个类型为 std::list<int>::iterator 的变量 it，指向列表的开头（head）。
然后，使用 std::advance 将迭代器 it 向前移动一个位置，模拟访问索引 1（列表中第二个元素）处的元素。然后使用 std::cout 将元素值打印到控制台。
然后，程序使用基于范围的 for 循环遍历 linkedList。
此循环逐个迭代 linkedList 中的每个元素，并且循环变量 i 在每次迭代中获取每个元素的值。在循环内部，每个元素都打印到控制台，并用空格分隔。
打印完 linkedList 的所有元素后，程序会在控制台添加一个换行符 (std::endl) 来结束输出。

程序输出

LinkedList 的优点

高效的插入和删除：在 LinkedList 中添加或删除元素非常高效，尤其是在列表的中间。由于 LinkedList 只需更新指针，因此这些操作的时间复杂度为 O(1)。
内存灵活性：LinkedList 不需要连续内存分配。因此，它可以有效地利用内存来存储不同大小的元素，并且不像 ArrayList 那样需要调整大小操作。

LinkedList 的缺点

缓慢的随机访问：与 ArrayList 不同，LinkedList 不提供基于索引的直接元素访问。要访问特定索引处的元素，LinkedList 必须从列表开头开始遍历，直到找到所需的元素。这会导致按索引访问元素的 O(n) 时间复杂度。
内存开销增加：LinkedList 需要额外的内存来存储每个元素的指针/引用。当元素数量很多时，此开销可能会很大。

性能比较

现在，让我们比较一下 ArrayList 和 LinkedList 在不同场景下的性能

随机访问

ArrayList：O(1) - 恒定时间，因为按索引访问元素涉及简单的指针运算。

LinkedList：O(n) - 线性时间，因为它需要从头开始遍历列表才能到达所需的索引。

在末尾插入

ArrayList：O(1) 摊销 - 大多数情况下，在末尾添加元素只是将其追加到动态数组中，这需要恒定时间。偶尔，ArrayList 可能需要调整大小，这需要 O(1) 时间，但平均而言这种情况很少发生。

LinkedList：O(1) - 在末尾添加元素涉及创建一个新节点并更新最后一个节点的 next 指针，这需要恒定时间。

在中间插入

ArrayList：O(n) - 在中间插入元素需要将所有后续元素向右移动一个位置，这需要线性时间。

LinkedList：O(1) - 在中间插入元素涉及创建一个新节点、更新指针，并且在找到要删除的节点后需要恒定时间。

在末尾删除

ArrayList：O(1) - 删除最后一个元素只需递减 ArrayList 的大小，这需要恒定时间。

LinkedList：O(n) - 要删除最后一个元素，LinkedList 需要遍历列表以找到倒数第二个节点，这需要线性时间。

在中间删除

ArrayList：O(n) - 从中间删除元素需要将所有后续元素向左移动一个位置，这需要线性时间。

LinkedList：O(1) - 在中间删除元素涉及更新指针，并且在找到要删除的节点后需要恒定时间。

用例

选择 ArrayList 的情况

您需要使用基于索引的检索快速随机访问元素。

列表的大小是已知的或不经常更改，这允许您设置初始容量以最大程度地减少调整大小操作。

内存消耗是一个问题，因为 ArrayList 通常比 LinkedList 使用的内存少。

选择 LinkedList 的情况

需要频繁插入或删除元素，尤其是在列表的中间。

您有大量元素，并且内存使用量不是主要问题。

您正在处理不同大小的元素，并希望优化内存利用率。

结论

总之，在 ArrayList 和 LinkedList 之间进行选择最终取决于您应用程序的特定需求和特性。ArrayList 通过基于索引的访问 (O(1)) 提供快速访问时间，适用于读密集型或搜索密集型任务。但是，当在列表的中间或开头添加或删除元素时，它的插入和删除速度较慢 (O(n))。

另一方面，LinkedList 通过简单地重新排列节点引用来提供快速的插入和删除 (O(1))。这使其非常适合涉及频繁修改列表的场景。但是，它的访问速度较慢 (O(n))，因为必须按顺序遍历元素才能找到特定元素。

如果您的应用程序优先考虑快速读取操作和随机访问，则 ArrayList 可能是更好的选择。反之，如果您需要高效的插入和删除，并且可以容忍较慢的访问时间，那么 LinkedList 可能更合适。请记住，还应考虑内存消耗，因为 LinkedList 由于存储指向下一个节点的引用的开销较高。

下一主题N 元树的直径

ArrayList vs LinkedList

引言

什么是 ArrayList？

内部机制