什么时候在数组/数组列表上使用链表?

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

248208 次浏览
小开

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

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

小开

数组具有O(1)随机访问，但是向数组中添加或删除内容的代价非常高。

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

小开
最佳答案

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

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

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

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

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

数组在以下情况下更可取:

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

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

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

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

数组列表(就像。net中的那些)给你数组的好处，但动态地为你分配资源，所以你不需要太担心列表的大小，你可以删除任何索引上的项目，而不需要任何努力或重新排列元素。在性能方面，数组列表比原始数组慢。

小开

嗯，我猜数组列表可以用在以下情况下:

  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的旧实现，但所有方法都是同步的。对于多线程环境中的共享列表，这不是正确的方法。

HashMap

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

< >强TreeSet 插入/删除/包含在O(log N)

< >强HashSet 插入/删除/包含/大小在O(1)

小开

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

2)搜索(get方法)操作在Arraylist (O(1))中是快速的，但在LinkedList (O(n))中不是，所以如果有更少的添加和删除操作和更多的搜索操作要求，Arraylist将是你最好的选择。

小开

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

对于一个数组，如果你从列表的顶部移除一些东西复杂度是o(n)因为数组元素的所有下标都要移位。

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

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

我认为在链表和数组中搜索都是o(log n)因为你可能会使用二分搜索。

小开

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

  • 搜索

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

那么，这背后有什么好处呢?

数组是连续的内存块,大部分人会在第一次加载到缓存访问这使它相对剩余快速访问元素的数组,我们访问数组中的元素位置的引用也会增加从而少抓了,在缓存中缓存位置指的是操作,从而执行更快比在内存中,基本上在数组,我们最大化的机会顺序元素访问的缓存。在链表不一定是连续的内存块,不能保证项目按顺序出现在彼此附近的列表实际上是安排在内存中,这意味着更少的缓存命中率如更多缓存遗漏,因为我们需要从内存中读取每一个访问链表元素的增加所花费的时间访问它们和降解性能如果我们做更多的随机存取操作又名搜索,数组将快速如下解释。

  • 插入

这是简单和快速的LinkedList的插入是O(1)操作在LinkedList (Java)阵列相比,考虑数组充满的情况下,我们需要将内容复制到新数组如果数组完全使一个元素插入ArrayList O (n)在坏的情况下,而ArrayList还需要更新其指数年底如果你插入一些除了数组,链表的我们不必调整它,你只需要更新指针。

  • 删除

它的工作原理类似于插入，在LinkedList中比在array中更好。

小开

我做了一些基准测试，发现list类实际上比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)

数组列表适用于写一次读多次或追加程序，但不适用于从前面或中间进行添加/删除。

小开

在现实中，内存局部性对实际处理的性能有很大的影响。

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

如果存在按顺序访问数组的方法，则这是迄今为止性能最好的方法。如果性能很重要，那么至少应该考虑将此作为设计目标。

小开

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

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

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

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

小开

这个问题的简单答案可以用以下几点来给出:

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

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

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


提交答案