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

When to use a linked list over an array/array list?

提问by faceless1_14

I use a lot of lists and arrays but I have yet to come across a scenario in which the array list couldn't be used just as easily as, if not easier than, the linked list. I was hoping someone could give me some examples of when the linked list is notably better.

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

回答by Lamar

Linked lists are preferable over arrays when:

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

1. you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)

2. you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big

3. you don't need random access to any elements

4. you want to be able to insert items in the middle of the list (such as a priority queue)

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

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

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

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

Arrays are preferable when:

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

1. you need indexed/random access to elements

2. you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array

3. you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.

4. memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.

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

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

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

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

Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around. Performance-wise, arraylists are slower than raw arrays.

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

回答by Dustin

Arrays have O(1) random access, but are really expensive to add stuff onto or remove stuff from.

数组具有 O(1) 随机访问，但是在其中添加内容或从中删除内容非常昂贵。

Linked lists are really cheap to add or remove items anywhere and to iterate, but random access is O(n).

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

回答by Vpn_talent

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 are good for write-once-read-many or appenders, but bad at add/remove from the front or middle.

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

回答by Jay Conrod

To add to the other answers, most array list implementations reserve extra capacity at the end of the list so that new elements can be added to the end of the list in O(1) time. When the capacity of an array list is exceeded, a new, larger array is allocated internally, and all the old elements are copied over. Usually, the new array is double the size of the old one. This means that on average, adding new elements to the end of an array list is an O(1) operation in these implementations. So even if you don't know the number of elements in advance, an array list may still be faster than a linked list for adding elements, as long as you are adding them at the end. Obviously, inserting new elements at arbitrary locations in an array list is still an O(n) operation.

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

Accessing elements in an array list is also faster than a linked list, even if the accesses are sequential. This is because array elements are stored in contiguous memory and can be cached easily. Linked list nodes can potentially be scattered over many different pages.

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

I would recommend only using a linked list if you know that you're going to be inserting or deleting items at arbitrary locations. Array lists will be faster for pretty much everything else.

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

回答by Uri

The advantage of lists appears if you need to insert items in the middle and don't want to start resizing the array and shifting things around.

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

You're correct in that this is typically not the case. I've had a few very specific cases like that, but not too many.

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

回答by Harleen

It all depends what type of operation you are doing while iterating , all data structures have trade off between time and memory and depending on our needs we should choose the right DS. So there are some cases where LinkedList are faster then array and vice versa . Consider the three basic operation on data structures.

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

• Searching

• 搜索

Since array is index based data structure searching array.get(index) will take O(1) time while linkedlist is not index DS so you will need to traverse up to index , where index <=n , n is size of linked list , so array is faster the linked list when have random access of elements.

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

Q.So what's the beauty behind this ?

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

As Arrays are contiguous memory blocks, large chunks of them will be loaded into the cache upon first access this makes it comparatively quick to access remaining elements of the array,as much as we access the elements in array locality of reference also increases thus less catch misses, Cache locality refers to the operations being in the cache and thus execute much faster as compared to in memory,basically In array we maximize the chances of sequential element access being in the cache. While Linked lists aren't necessarily in contiguous blocks of memory, there's no guarantee that items which appear sequentially in the list are actually arranged near each-other in memory, this means fewer cache hits e.g. more cache misses because we need to read from memory for every access of linked list element which increases the time it takes to access them and degraded performance so if we are doing more random access operation aka searching , array will be fast as explained below.

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

• Insertion

• 插入

This is easy and fast in LinkedList as insertion is O(1) operation in LinkedList (in Java) as compared to array, consider the case when array is full, we need to copy contents to new array if array gets full which makes inserting an element into ArrayList of O(n) in worst case, while ArrayList also needs to update its index if you insert something anywhere except at the end of array , in case of linked list we needn't to be resize it, you just need to update pointers.

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

• Deletion

• 删除

It works like insertions and better in LinkedList than array.

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

回答by Praveen Kumar Verma

Those are the most common used implementations of Collection.

这些是 Collection 最常用的实现。

ArrayList:

数组列表：

• insert/delete at the end generally O(1) worst case O(n)

• insert/delete in the middle O(n)

• retrieve any position O(1)

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

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

• 检索任何位置 O(1)

LinkedList:

链表：

• insert/delete in any position O(1) (note if you have a reference to the element)

• retrieve in the middle O(n)

• retrieve first or last element O(1)

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

• 在中间检索 O(n)

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

Vector: don't use it. It is an old implementation similar to ArrayList but with all methods synchronized. It is not the correct approach for a shared list in a multithreading environment.

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

HashMap

哈希表

insert/delete/retrieve by key in O(1)

通过 O(1) 中的键插入/删除/检索

TreeSetinsert/delete/contains in O(log N)

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

HashSetinsert/remove/contains/size in O(1)

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

回答by user3150186

In reality memory locality has a huge performance influence in real processing.

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

The increased use of disk streaming in "big data" processing vs random access shows how structuring your application around this can dramatically improve performance on a larger scale.

在“大数据”处理与随机访问中越来越多地使用磁盘流显示了围绕此构建应用程序如何可以在更大范围内显着提高性能。

If there is any way to access an array sequentially that is by far the best performing. Designing with this as a goal should be at least considered if performance is important.

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

回答by photonic

Arrays, by far, are the most widely used data structures. However, linked lists prove useful in their own unique way where arrays are clumsy - or expensive, to say the least.

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

Linked lists are useful to implement stacks and queues in situations where their size is subject to vary. Each node in the linked list can be pushed or popped without disturbing the majority of the nodes. Same goes for insertion/deletion of nodes somewhere in the middle. In arrays, however, all the elements have to be shifted, which is an expensive job in terms of execution time.

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

Binary trees and binary search trees, hash tables, and tries are some of the data structures wherein - at least in C - you need linked lists as a fundamental ingredient for building them up.

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

However, linked lists should be avoided in situations where it is expected to be able to call any arbitrary element by its index.

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

回答by Emil Albert

I did some benchmarking, and found that the list class is actually faster than LinkedList for random inserting:

我做了一些基准测试，发现对于随机插入，列表类实际上比 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();
        }
    }
}

It takes 900 ms for the linked list and 100ms for the list class.

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

It creates lists of subsequent integer numbers. Each new integer is inserted after a random number which is already in the list. Maybe the List class uses something better than just an array.

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