223

我使用了很多列表和数组，但我还没有遇到过这样的场景：数组列表不能像使用链表一样容易，如果不是更容易的话。我希望有人能给我一些链接列表何时明显更好的例子。

4

15 回答 15

304

在以下情况下，链表优于数组：

  1. 您需要从列表中进行恒定时间的插入/删除（例如在时间可预测性绝对关键的实时计算中）

  2. 您不知道列表中有多少项目。使用数组，如果数组变得太大，您可能需要重新声明和复制内存

  3. 您不需要随机访问任何元素

  4. 您希望能够在列表中间插入项目（例如优先级队列）

在以下情况下最好使用数组：

  1. 您需要对元素进行索引/随机访问

  2. 您提前知道数组中的元素数量，以便为数组分配正确的内存量

  3. 按顺序遍历所有元素时，您需要速度。您可以在数组上使用指针数学来访问每个元素，而您需要根据链表中每个元素的指针来查找节点，这可能会导致页面错误，从而导致性能下降。

  4. 记忆是一个问题。填充数组比链表占用更少的内存。数组中的每个元素只是数据。每个链表节点都需要数据以及一个（或多个）指向链表中其他元素的指针。

数组列表（如 .Net 中的那些）为您提供数组的好处，但为您动态分配资源，因此您无需过多担心列表大小，您可以轻松删除任何索引处的项目或重新洗牌周围的元素。在性能方面，arraylists 比原始数组慢。

于 2008-12-26T07:12:04.860 回答
67

数组有 O(1) 的随机访问，但是添加东西或从中删除东西真的很昂贵。

链表在任何地方添加或删除项目并进行迭代真的很便宜，但随机访问是 O(n)。

于 2008-12-26T07:08:06.723 回答
34 
Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

ArrayLists 适用于一次写入多次读取或附加程序，但不适合从前面或中间添加/删除。

于 2017-08-01T08:52:25.423 回答
16

为了补充其他答案，大多数数组列表实现在列表末尾保留额外容量，以便可以在 O(1) 时间内将新元素添加到列表末尾。当超出数组列表的容量时，会在内部分配一个新的更大的数组，并复制所有旧元素。通常，新数组的大小是旧数组的两倍。这意味着在这些实现中，平均而言，将新元素添加到数组列表的末尾是一个 O(1) 操作。所以即使你事先不知道元素的个数，数组列表在添加元素方面可能仍然比链表更快，只要你在最后添加它们。显然，在数组列表的任意位置插入新元素仍然是 O(n) 操作。

访问数组列表中的元素也比链表更快，即使访问是顺序的。这是因为数组元素存储在连续的内存中并且可以轻松缓存。链表节点可能分散在许多不同的页面上。

如果您知道要在任意位置插入或删除项目，我建议仅使用链表。几乎所有其他事情，数组列表都会更快。

于 2008-12-26T09:13:52.273 回答
7

如果您需要在中间插入项目并且不想开始调整数组大小和移动东西，那么列表的优势就会出现。

你是对的，通常情况并非如此。我遇到过一些非常具体的案例，但不是太多。

于 2008-12-26T07:07:49.517 回答
4

这完全取决于您在迭代时执行的操作类型，所有数据结构都在时间和内存之间进行权衡，并且根据我们的需要，我们应该选择正确的 DS。所以在某些情况下，LinkedList 比数组更快，反之亦然。考虑数据结构的三个基本操作。

  • 搜索

由于数组是基于索引的数据结构搜索 array.get(index) 将花费 O(1) 时间，而 linkedlist 不是索引 DS 所以你需要遍历 index ，其中 index <=n ， n 是链表的大小，所以当随机访问元素时，数组比链表更快。

Q.那么这背后的美丽是什么？

由于数组是连续的内存块，它们中的大块将在第一次访问时加载到缓存中，这使得访问数组的剩余元素相对较快，就像我们访问数组中的元素一样，引用的局部性也会增加，因此捕获较少未命中，缓存局部性是指在缓存中的操作，因此与在内存中相比执行得更快，基本上在数组中，我们最大化了顺序元素访问在缓存中的机会。虽然链接列表不一定在连续的内存块中，但不能保证在列表中顺序出现的项目实际上在内存中彼此靠近排列，这意味着更少的缓存命中，例如

  • 插入

这在 LinkedList 中既简单又快速，因为与数组相比，LinkedList（在 Java 中）中的插入是 O(1) 操作，考虑数组已满的情况，如果数组已满，我们需要将内容复制到新数组，这使得插入在最坏的情况下，将元素放入 O(n) 的 ArrayList 中，而 ArrayList 还需要更新其索引，如果您在除数组末尾之外的任何位置插入内容，则在链表的情况下，我们不需要调整它的大小，您只需要更新指针。

  • 删除

它像插入一样工作，并且在 LinkedList 中比数组更好。

于 2016-04-16T09:32:25.883 回答
2

这些是 Collection 最常用的实现。

数组列表：

  • 在末尾插入/删除通常 O(1) 最坏情况 O(n)

  • 在中间插入/删除 O(n)

  • 检索任何位置 O(1)

链表：

  • 在任何位置插入/删除 O(1) （注意是否有对元素的引用）

  • 在中间检索 O(n)

  • 检索第一个或最后一个元素 O(1)

矢量：不要使用它。这是一个类似于 ArrayList 的旧实现，但所有方法都是同步的。这不是多线程环境中共享列表的正确方法。

哈希映射

在 O(1) 中按键插入/删除/检索

TreeSet 插入/删除/包含在 O(log N) 中

HashSet 在 O(1) 中插入/删除/包含/大小

于 2015-07-04T13:26:41.007 回答
2

实际上，内存局部性在实际处理中具有巨大的性能影响。

在“大数据”处理与随机访问中，磁盘流的使用越来越多，这表明围绕它构建应用程序可以显着提高更大范围内的性能。

如果有任何方法可以按顺序访问数组，那是迄今为止性能最好的。如果性能很重要，那么至少应该考虑以此为目标进行设计。

于 2018-06-07T04:46:35.613 回答
0

嗯，我猜 Arraylist 可以用于以下情况：

  1. 你不确定会有多少元素出现
  2. 但是您需要通过索引随机访问所有元素

例如，您需要导入和访问联系人列表中的所有元素（您不知道其大小）

于 2008-12-26T07:28:20.257 回答
0

使用链表对数组进行基数排序和多项式运算。

于 2013-01-24T15:30:52.523 回答
0

1) 如上所述，与 ArrayList(O(n)) 相比，LinkedList 中的插入和删除操作提供了良好的性能 (O(1))。因此，如果应用中需要频繁的增删改查，那么LinkedList是最好的选择。

2）搜索（get方法）操作在Arraylist（O（1））中很快，但在LinkedList（O（n））中不快，所以如果添加和删除操作较少，搜索操作要求较多，ArrayList将是您的最佳选择。

于 2015-09-05T12:01:21.537 回答
0

我认为主要区别在于您是否经常需要从列表顶部插入或删除内容。

对于数组，如果从列表顶部删除某些内容，则复杂度为 o(n)，因为数组元素的所有索引都必须移动。

对于链表，它是 o(1)，因为您只需要创建节点，重新分配头并将对 next 的引用分配为前一个头。

在列表末尾频繁插入或删除时，数组更可取，因为复杂度将是 o(1)，不需要重新索引，但对于链表，它将是 o(n)，因为您需要从头开始到最后一个节点。

我认为在链表和数组中搜索都将是 o(log n)，因为您可能会使用二进制搜索。

于 2016-01-31T16:00:36.147 回答
0

我做了一些基准测试，发现列表类在随机插入方面实际上比 LinkedList 更快：

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

链表需要 900 毫秒，列表类需要 100 毫秒。

它创建后续整数的列表。每个新整数都插入到列表中已经存在的随机数之后。也许 List 类使用了比数组更好的东西。

于 2016-05-08T13:33:08.943 回答
0

到目前为止，数组是使用最广泛的数据结构。然而，链表以其独特的方式证明是有用的，其中数组是笨拙的——或者至少可以说是昂贵的。

链表对于在大小可变的情况下实现堆栈和队列很有用。链表中的每个节点都可以在不干扰大多数节点的情况下被推送或弹出。在中间某处插入/删除节点也是如此。然而，在数组中，所有元素都必须移动，这在执行时间方面是一项昂贵的工作。

二叉树和二叉搜索树、哈希表和尝试是其中的一些数据结构 - 至少在 C 中 - 您需要链表作为构建它们的基本成分。

但是，在期望能够通过索引调用任意元素的情况下，应避免使用链表。

于 2020-02-13T15:00:20.477 回答
0

可以使用以下几点给出该问题的简单答案：

  1. 当需要类似类型的数据元素的集合时，将使用数组。而链表是称为节点的混合类型数据链接元素的集合。

  2. 在数组中，可以在 O(1) 时间内访问任何元素。而在链表中，我们需要花费 O(n) 时间从头到所需节点遍历整个链表。

  3. 对于数组，最初需要声明一个特定的大小。但是链表的大小是动态的。

于 2020-07-06T17:45:18.567 回答