何时在数组/数组列表上使用链表？

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

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

数组具有 O（1） 个随机访问，但添加或删除内容的成本非常高。

链表在任何地方添加或删除项目以及迭代都非常便宜，但随机访问是 O（n）。

在以下情况下，链表比数组更可取：

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

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

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

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

在以下情况下，数组是首选：

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

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

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

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

数组列表（如 .Net 中的数组列表）为您提供了数组的好处，但会动态地为您分配资源，这样您就不需要太担心列表大小，并且可以删除任何索引处的项目，而无需任何努力或重新洗牌元素。在性能方面，数组列表比原始数组慢。

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

1. 您不确定将存在多少个元素
2. 但是您需要通过索引随机访问所有元素

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

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

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

我建议仅在您知道要在任意位置插入或删除项目时才使用链表。对于几乎所有其他内容，数组列表都会更快。

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

这些是 Collection 最常用的实现。

数组列表：

• 插入/删除在末尾，一般为O（1），最坏情况为O（n）

• 在中间插入/删除 O（n）

• 检索任意位置 O（1）

LinkedList：

• 在任意位置插入/删除 O（1）（请注意，如果您有对元素的引用）

• 在中间检索 O（n）

• 检索第一个或最后一个元素 O（1）

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

哈希图

通过O（1）中的键插入/删除/检索

TreeSet 插入/删除/包含 O（log N）

HashSet 在 O（1） 中插入/删除/包含/大小

1）如上所述，与ArrayList（O（n））相比，插入和删除操作在LinkedList中提供了良好的性能（O（1））。因此，如果在应用程序中需要频繁添加和删除，那么 LinkedList 是最佳选择。

2）搜索（获取方法）操作在Arraylist（O（1））中很快，但在LinkedList（O（n））中则不然，因此如果添加和删除操作较少，搜索操作要求较多，则ArrayList将是您最好的选择。

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

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

对于链表，它是 o（1），因为您只需要创建节点，重新分配 head 并将引用分配给 next 作为上一个 head。

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

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

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

• 搜索

由于数组是基于索引的数据结构搜索 array.get（index） 将花费 O（1） 时间，而 linkedlist 不是索引 DS，因此您需要遍历索引，其中索引 <=n ，n 是链表的大小，因此数组在随机访问元素时链表更快。

Q.So 这背后有什么美？

由于数组是连续的内存块，因此在首次访问时，其中的大部分将被加载到缓存中，这使得访问数组的其余元素的速度相对较快，因为我们访问数组中的元素，引用的位置也会增加，因此捕获失误更少，缓存位置是指在缓存中的操作，因此与内存中的操作相比，执行速度要快得多，基本上，在数组中，我们最大限度地提高了缓存中顺序元素访问的机会。虽然链表不一定在连续的内存块中，但不能保证列表中按顺序出现的项目实际上在内存中彼此靠近排列，这意味着更少的缓存命中，例如更多的缓存未命中，因为我们需要从内存中读取链表元素的每次访问，这增加了访问它们所需的时间并降低了性能，因此，如果我们进行更多的随机访问操作，也就是搜索， 数组将很快，如下所述。

• 插入

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

• 删除

它的工作方式类似于插入，在 LinkedList 中比数组更好。

我做了一些基准测试，发现列表类实际上比 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 类使用的东西比数组更好。

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 适用于一次写入多次读取或追加器，但不适用于从前面或中间添加/删除。

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

与随机访问相比，在“大数据”处理中越来越多地使用磁盘流式处理表明，围绕此构建应用程序可以显著提高更大规模的性能。

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

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

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

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

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

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

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

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

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

“我希望有人能给我一些例子，说明链表什么时候明显好（比数组）。

我将假设具有指数扩展策略的动态数组，因此我们不限于固定大小，并且具有有效的追加。基本上，当在除后面以外的任何地方插入/删除任何元素序列时，链表会更好。只有在对元素进行排序并且使用二进制搜索的情况下，数组中的搜索才会在复杂性方面更好。

下表使链表看起来确实非常好，但是大的 O 复杂度忽略了缓存的影响（对于足够小的动态数组，O（N） 操作甚至可能比链表上的等效操作更快）。（动态）数组对缓存更加友好，因此在遍历元素时速度更快（正如其他人已经解释的那样），一个接一个地访问它们。这可能比其他方面更重，使您偏向于（动态）数组。

Operation                       DynamicArray   LinkedList
=========================================================
access front                    O(1)           O(1)
access back                     O(1)           O(1)
access using iterator           O(1)           O(1)
advance iterator by k           O(1)           O(k)
search unsorted,sorted          O(N),O(log(N)) O(N),O(N)
insert/remove at front          O(N)           O(1)
insert/remove at back           O(1)           O(1)
insert before/after iterator    O(N)           O(1)
remove at/before/after iterator O(N)           O(1)
concatenate other of size M     O(M)           O(1)
extract range [it1,it2] to new  O(N)           O(1)

我还经常看到这样的论点，即动态数组使引用无效，而链表则不会。如果这是一个问题，您可以使用指向元素的（动态）指针数组。如果元素很大并且您想避免复制它们，也是如此。