数字处理：为什么你应该再也不要在代码中使用链表了
4.86/5 (73投票s)
大多数编程资源在比较链表和向量时都是错误的。在这里，你可以阅读并理解它们是如何错误的，以及为什么链表（在大多数情况下）应该被避免。
我的过错 - 请在继续之前阅读
让我们再次看看标题。它包含了一个非常重要的前缀。标题说：
数字处理：为什么你应该再也不要在代码中使用链表了.
数字处理这个前缀是整篇文章的关键。如果标题的"数字处理："部分被忽略，可能会被理解为通用建议，即永远不要使用链表，但这并非本文的目的。
本文的重点是解释为什么链表如此不适合数字处理任务。数字处理是什么将很快解释。即使如此，当然总会有规则的例外，所以标题也不能百分之百准确。
上述标题是夸张。它强烈地强调了一个目的，但故意言过其实。由于我对它有复杂的情感，一些读者显然也有同感，那么可能的标题更改可以是：
为什么你应该再也不要在代码中使用链表进行数字处理
不过，我决定保留它，因为它更改起来可能会更令人困惑。一些读者也评论说，他们认为这个标题恰到好处。所以我们就这样吧。
那么，我最初为什么会做出像为文章加上夸张标题这样不寻常的代码项目行为呢？老实说，因为这个信息需要传达出去。我的印象是，使用链表进行数字处理的性能影响并不为人所熟知，这就是我决定写这篇文章的原因。
我希望通过这个我的过错 ，你能超越任何最初的困惑（这都是我的错），看到核心问题：链表的缺点在处理一系列数字处理问题时的表现。
目录
- 我的过错 - 请在继续之前阅读
- 引言
- 现实生活中
- 目录
- 免责声明
- 范围
- 在线资源
- 重要内容来了
- 引用局部性 I
- 代码
- 引用局部性 II
- 魔鬼代言人
- 魔鬼代言人 I - 复制成本
- 魔鬼代言人 II：线性，排序插入（带有智能链表）
- 魔鬼代言人 III：碎片化内存使向量成为一个大忌
- 魔鬼代言人 IV：带有合并或排序的算法
- 魔鬼代言人 V：在第一个位置插入
- 现在该做什么？
Java和C#- 结论
- 参考文献
- 历史
引言
本文将解释为什么链表在处理数字处理方面不是一个理想的选择。
数字处理在这里指的是对原始数字或POD数据进行处理、排序、插入、删除以及简单地进行操作。本文是关于为什么链表不适合这些任务，并且实际上应该避免。本文是以一种态度写的，但有事实和证明作为支撑。欢迎您，甚至鼓励您，来验证这些说法，所有代码和证明都可以在线访问或下载。
目的是要清楚地展示一些显而易见的例子来证明观点。本文不是为了涵盖其建议的所有特殊情况和例外。
这些显而易见的例子对某些读者来说是边缘情况，对其他读者来说是常见的编程任务。一些读者认为本文的重点是常识，而另一些读者则认为这是一个笑话，当他们意识到这实际上是现实时感到震惊。我尤其建议后者不要轻易否定本文，而是花时间研究它。你可能会获得新的见解。
现实生活中
数字处理任务有时与我下面的例子相似，有时则不然。它们可能存在于航空电子技术、心脏手术设备、监视技术等各种领域 [...] 随便你怎么称呼。当你继续阅读时，要记住的是，本文中使用的数字处理是指存储、检索、删除和排序的数字和POD数据。没什么奇怪的，非常普遍，而且总是易于复制的类型。
在我职业生涯中，曾有几次遇到过性能问题，其中一些时间关键的区域由于链表的数字处理而导致性能不佳。我曾在从实时、嵌入式、内存受限的PowerPC系统到x86 PC应用程序等一系列领域中见过这些与链表相关的性能问题。
当时，这对参与者来说是完全出乎意料的。这让他们感到惊讶，因为对他们来说，数学复杂度模型已经证明了它是一种非常高效的数据结构，适用于这个或那个用途。认为它慢是糟糕的，但也可以接受，因为根据同样的数学推理，其他数据结构会更慢。
不幸的是，对于一组给定的问题，这些数学模型很可能让你误入歧途。盲目遵循数据结构和算法的Big-O复杂度可能会让你得出一个完全错误的结论。
Big-O符号并没有说明一个（带算法的数据结构）与另一个相比的表现如何。Big-O只会告诉你随着n的增加，性能会如何下降。所以，从抽象的Big-O角度比较一个内存密集型数据结构和一个对缓存友好的数据结构是没有意义的。这并非新事物，但由于书籍和在线资源很少或从未提及这一点，所以很多人不知道，或者至少倾向于忘记。
免责声明
万一我的我的过错和引言没有涵盖。让我说清楚：本文并非不赞成链表在其他类型的用法，例如当它包含指向其他类型的指针的类型，大型且昂贵的复制类型（是的，POD也可以太大）时。
本文并非关于链表特别有用的特定使用模式——因为确实有几种这样的模式。稍后在评论区可以找到几个好坏参半的例子。本文是一个有主见的文章，但有事实依据。它并不全面否定链表，除了在一个特定领域：数字处理。
将使用其他类型的容器来与链表进行比较。目的不是吹捧这些容器，而是展示链表不足的领域。甚至会使用这些容器以明显次优的方式，它们仍然远远优于链表。
本文中的代码示例和容器名称来自C++。Java中的std::vector被称为ArrayList，C++中的链表称为std::list，在Java中则称为LinkedList。
好了，免责声明够了，我们开始吧。
范围
你应该使用什么数据结构？你应该避免什么数据结构？
想象一下，你必须使用一个数据结构。它没什么特别的，只是一个存储原始数字，或者偶尔使用一次，偶尔晚些时候使用的POD数据载体。
这些项目会被插入，然后间歇性地删除。它们会具有某种内部顺序或意义，并据此进行排列。有时插入和删除会在开头或结尾，但大多数时候你必须找到位置，然后在中间进行插入或删除。一个绝对的要求是，元素的插入和删除要高效，最好是O(1)。
那么，你应该使用什么数据结构？
在线资源
在这种时候，最好仔细查阅书籍和/或在线资源，以验证你最初的猜测是否正确。在这种情况下，你可能会回想起向量通常在访问项目方面速度很快，但在修改运算符方面可能很慢，因为插入/删除不在末尾的项目会导致数组的一部分内容被移位。当然，你也知道当向量已满时插入会触发大小调整。会创建一个新的数组存储，并将向量中的所有项目复制或移动到新的存储中。这看起来直观地很慢。
另一方面，链表在访问项目方面可能很慢（O(n)），但插入/删除基本上只是切换指针，所以这些O(1)操作非常有吸引力。我查阅了几种不同的在线资源，然后做出了我的决定。就用链表吧……
哔——。错误。一个红色的地精跳到我面前，拦住我。他毫不含糊地告诉我，我错了。大错特错。.
www.cplusplus.com/reference/stl/list 关于 std::list[...] 与其他标准序列容器（vector 和 deque）相比，列表在容器内任何位置的插入、提取和移动元素方面通常表现更好，因此在大量使用这些操作的算法（如排序算法）中也表现更好。
www.cplusplus.com/reference/stl/vector 关于 std::vector[...] 向量通常在访问元素以及在序列末尾添加或删除元素方面效率最高。[...] 对于涉及在末尾以外的位置插入或删除元素的*操作，它们的性能不如 deque 和 list。
http://en.wikipedia.org/wiki/Sequence_container_(C%2B%2B)#List 向量在删除或插入非末尾元素方面效率不高。此类操作的复杂度为 O(n)（参见 Big-O notation），而链表的复杂度为 O(1)。这被访问速度所抵消——向量中随机元素的访问复杂度为 O(1)，而通用链表的复杂度为 O(n)，链接树的复杂度为 O(log n)。
在这个例子中，大多数插入/删除肯定不会在末尾，这一点已经确定。那么，这是否意味着链表会比向量更有效，对吗？我决定仔细查看Wikipedia、Wiki.Answers和Wikibooks on Algorithms。它们似乎都同意，我不明白那个RED GNOME在抱怨什么。
我休息一下，看Bjarne Stroustrup的Going Native 2012主题演讲。在视频的1:44处和幻灯片43，发生了一些有趣的事情。我明白了RED GNOME想告诉我什么。一切都说得通了。当然。我早就该知道了。啊哈。引用局部性。
重要内容来了
链表在插入/删除元素时比向量快，这并不重要。在稍大的范围内，这完全不相关。在插入/删除元素之前，必须找到正确的位置。而找到该位置与向量相比非常慢。事实上，如果对向量和链表都进行线性搜索，那么向量的线性搜索将完全、彻底、毫无悬念地击败链表。
- 向量的额外移动，**复制开销**在时间上很便宜。它非常便宜，如果与遍历链表的巨大开销相比，可以完全忽略。
为什么？你可能会问。为什么线性搜索对向量来说如此高效，而对所谓的哦，那么慢的链表线性搜索却不是？难道链表的O(n)不应该与向量的O(n)相当吗？
在一个理想的世界里也许可以，但在现实中却不是！Wiki.Answers和其他在线资源在这里是错误的！因为它们提供的建议似乎是在非末尾插入/删除很常见时使用链表。这是糟糕的建议，因为它们似乎完全忽视了引用局部性的影响。
引用局部性 I
链表中的项目位于不连续的内存区域。遍历链表时，缓存行无法得到有效利用。有人可以说，链表对缓存线不友好，或者链表最大化了缓存行错过。不连续的内存使得遍历链表变慢，因为会大量使用RAM的获取。
另一方面，向量就是要把数据放在相邻的内存中。插入或删除一个项目可能意味着数据必须移动，但这对向量来说很便宜。非常便宜（是的，我喜欢这个词）。向量，凭借其相邻的内存布局，最大化了缓存利用率并最小化了缓存行错过。这就是全部的区别，而这个区别非常巨大，我很快就会向你展示。
让我们通过插入随机值来测试这一点。我们将保持数据结构有序，为了找到正确的位置，我们将对向量和链表都使用线性搜索。当然，这是使用向量的愚蠢方式，但我想展示相邻内存向量与不连续内存链表相比有多高效。
代码
/* NumbersInVector &randoms is pre created random values that are stored in a
std::vector. This way the same random values can be used for testing and comparing the
vector to the linked-list.
Example:
0, 1, 8, 4, 1 will get sorted to:
0, 1, 1, 4, 8 */
template <typename Container>
void linearInsertion(const NumbersInVector &randoms, Container &container)
{
std::for_each(randoms.begin(), randoms.end(),
[&](const Number &n)
{
auto itr = container.begin();
for (; itr!= container.end(); ++itr)
{
if ((*itr) >= n) { break; }
}
container.insert(itr, n); // sorted insert
});
}
/* Measure time in milliseconds for linear insert in a std container */
template <typename Container>
TimeValue linearInsertPerformance(const NumbersInVector &randoms, Container &container)
{
g2::StopWatch watch;
linearInsertion(std::cref(randoms), container);
auto time = watch.elapsedMs().count();
return time;
}
使用C++11可以轻松进行时间跟踪（我之前在这里写过的StopWatch）。现在只需要创建随机值，并跟踪几组随机数的测量时间。我们从10个数字的短集一直测量到500,000个。这将提供一个很好的视角。
void listVsVectorLinearPerformance(size_t nbr_of_randoms)
{
std::uniform_int_distribution distribution(0, nbr_of_randoms);
std::mt19937 engine((unsigned int)time(0)); // Mersenne twister MT19937
auto generator = std::bind(distribution, engine);
NumbersInVector values(nbr_of_randoms);
// Generate n random values and store them
std::for_each(values.begin(), values.end(), [&](Number &n)
{ n = generator();});
NumbersInList list;
TimeValue list_time = linearInsertPerformance(values, list);
NumbersInVector vector;
TimeValue vector_time = linearInsertPerformance(values, vector);
std::cout << list_time << ", " << vector_time << std::endl;
}
调用此方法处理多达500,000个值，我们就有足够的值来绘制图表，这正是Bjarne Stroustrup在Going Native 2012上所讲的。对于删除项目，我们得到一个类似的曲线，但时间不是那么密集。我已经收集了一些在IdeOne.com上和x64 Windows7及Ubuntu Linux笔记本上进行的定时结果供您参考。
你能看到底部的红色区域吗？图表没有显示错误。那个红色区域是向量的时间测量。链表进行500,000次排序插入花费了大约1小时47分钟。向量执行相同数量的元素则需要1分18秒。
您可以自己测试。代码附在本文章中。对于快速测试，您可以尝试在pastebin和在线编译器IdeOne上进行较小的（最多15秒）测试，最多包含40,000个元素：http://ideone.com/62Emz
引用局部性 II
处理器和缓存架构显然对结果有很大影响。在Linux操作系统上，可以通过以下方式检索缓存级别信息：
grep . /sys/devices/system/cpu/cpu*/cache/index*/*
在我的x64四核笔记本上，每个核心对拥有2个L1缓存，每个32KBytes，缓存行大小为64字节。2个L2缓存，每个256KBytes。所有核心共享3MB L3缓存。
四核Intel i5的概念图
我认为比较我的四核与一台更简单、更旧的计算机很有趣。使用CPU-Z免费软件，我从我旧的双核Windows7 PC上获得了信息，它拥有2个L1缓存，每个32KBytes，1个L2缓存，2048KBytes。用一小组值测试两者都清楚地显示了缓存的重要性（忽略不同的总线带宽和CPU速度）。
x86老式双核PC
x64四核Intel i5
魔鬼代言人
当然，总会有例外、特殊情况和反对使用向量或不使用链表的建议。如果我们能忽略明显无关的情况，而只关注POD或数字处理，那么仍然有一些有效的问题需要解决。
魔鬼代言人 I - 复制成本
对于向量，传统上认为的开销，即复制、移动和调整大小（包括内存分配和复制）是某些人（参考 [2] 到 [7]）选择链表而不是向量的充分理由。
上面已经表明，向量的可感知低效率实际上非常便宜，与遍历链表的成本相比。链表的项目插入是便宜的，但要到达插入点，必须在不连续的内存中进行一次昂贵的遍历。
上面的例子有些极端。整数示例突显了链表的另一个糟糕特性。链表需要3倍于整数大小来表示一个项目，而向量只需要1倍。所以，对于小数据类型，使用链表更加没有意义。
但是，如果复制成本没有那么便宜会怎么样？如果修改向量的成本增加？
对于大型类型，您可能会看到与上面相同的行为，但时间会有所不同。随着类型大小的增加，变得更昂贵，链表最终将优于需要移动和复制大量对象的向量。使用C++移动运算符也许会改变这种情况。我没有用移动运算符进行测试，所以这取决于您自己去尝试。
随着POD大小的增加，复制成本也会增加。复制和移动的开销将带来影响。缓存架构和缓存的行大小也会产生影响。如果POD大小大于缓存行大小，则与用于较小POD大小相比，缓存使用将是次优的。
在某个POD大小下，这种额外的开销甚至会比链表的慢速遍历更耗时。此时，选择使用向量比选择链表更糟糕，即使在本文前面使用的场景中也是如此。
下图显示了这一点。测试了200、4000和10,000个元素。每张图代表一个固定数量的元素，其中POD的字节大小在增加。
观察链表和向量性能之间的交叉点。在交叉点处，对于该数量的元素，性能从有利于向量转变为有利于链表。
从图表中可以看出，对于相同数量的元素，POD大小对链表性能几乎没有影响。对于向量来说，POD大小至关重要。复制成本随着大小成比例增加。
链表的效率受限于RAM访问成本，因此几乎不受POD大小的影响。然而，随着项目数量的增加，RAM访问的总成本会更高，并且需要更大的POD（字节）才能使链表优于向量。
数据收集在Google文档中，也以Excel格式提供下载。可以在ideone.com上快速查看ideone.com/W9vpT，下载中也提供。
魔鬼代言人 II：线性，排序插入（带有智能链表）
对上面显示的线性，排序插入的常见反对意见是，由于链表的线性已知很慢，应该保留到最后一个插入位置的迭代器。这样平均而言，线性搜索可以受益于O(n/2)而不是O(n)。
测试时，它显示了缓存架构对相邻内存结构性能的巨大影响。第一次测试运行在ideon.com/XprUU。ideone在线编译器具有未知的缓存架构，并且由于它同时服务多个运行，因此缓存利用率可能不可预测，并且RAM使用量很大。
在这种可能缓存利用不足的情况下，智能链表明显胜出。至少直到一定数量的元素。在向量赶上智能链表之前，它最多需要6000个元素。这让我大吃一惊！但当我用已知的缓存架构测试它时，也就说得通了。
在具有已知缓存架构的计算机上，即我的x64笔记本，具有L1、L2和L3缓存，进行了相同的测试。它立即显示了缓存利用率对相邻内存结构的优势。智能链表和向量在100个元素之前保持同步，在500个元素时，差异约为20%，并且在稳步增长。
如果你查看其数据表，可以看到在ideone.com/XprUU和x64笔记本上运行的性能数据。
在具有不同缓存架构的其他计算机上，以及使用其他语言（Java、C#等）时，结果会有所不同。
魔鬼代言人 III：碎片化内存使向量成为一个大忌
对于碎片化内存，或者内存可能碎片化的系统，或者对于巨大的向量，那么使用向量列表可能更有益。有几种不同的类型可供选择：展开链表[12]或std::deque是两种。
我没有测试碎片化内存场景，因为我实在想不出一种方法来强制内存轻松碎片化。在32位双核PC和64位四核PC上，我从未遇到过分配异常，即使是500,000个项目比较测试的倍数。
魔鬼代言人 IV：带有合并或排序的算法
是的，那又怎样？前面提到的在线资源指出，容器的合并或排序是链表优于向量的地方。很抱歉地说，但对于具有现代缓存架构的计算机来说，情况并非如此。至少在数字处理领域是这样，而sort不是最常用的吗？
再次，这些资源在给你糟糕的建议。
从数学角度来看，是的，在计算big-O复杂度时有意义。问题在于，（至少在我看到的）数学模型是有缺陷的。至少在通过big-O复杂度值来做选择方面是有缺陷的，这还不够好。
计算机缓存、RAM和内存架构完全被忽略，只考虑数学上简单的复杂度。
为了说明这一点，下面进行了一些简单的排序测试。
void listVsVectorSort(size_t nbr_of_randoms)
{
std::uniform_int_distribution<int> distribution(0, nbr_of_randoms);
std::mt19937 engine((unsigned int)time(0)); // Mersenne twister MT19937
auto generator = std::bind(distribution, engine);
NumbersInVector vector(nbr_of_randoms);
NumbersInList list;
std::for_each(vector.begin(), vector.end(), [&](Number& n)
{ n = generator(); list.push_back(n); } );
TimeValue list_time;
{ // list measure sort
g2::StopWatch watch;
list.sort();
list_time = watch.elapsedUs().count();
}
TimeValue vector_time;
{ // vector measure sort
g2::StopWatch watch;
std::sort(vector.begin(), vector.end());
vector_time = watch.elapsedUs().count();
}
std::cout << nbr_of_randoms << "\t\t, " << list_time << "\t\t, " << vector_time << std::endl;
}
我在Google表格的“sort comparison”标签页上进行了排序测试。我使用了std::sort（向量）与std::list::sort。
当然，这是两种不同的算法，很可能使用了不同的算法，所以这次测试可能是一个冒险。无论如何，这可能很有趣，因为两种算法都处于最佳状态，而这正是链表应该获胜的地方。不出所料，情况并非如此。
std::sort（向量）轻松击败了std::list::sort。完整的代码附在这里，可以在http://ideone.com/tLUeK找到。
下图显示了从10到1,000个元素的排序性能。链表的成本总是更高。两者都显示出随着元素数量的增加，成本呈比例增加，但链表的斜率更陡。随着元素数量的增加，链表的排序每项成本将明显高于向量。
在具有更好CPU缓存架构的现代x64计算机上测试这一点，将进一步增加std::list和向量之间的差异。
随着元素数量的不断增加，这种最初的性能视角并没有改变。下图显示了从10到100,000个元素，但其比例特性与10到1,000个元素时几乎相同。
相应的合并测试没有进行。但是，对于两个已排序结构的合并，合并后结构仍然排序，那么这又涉及到遍历，而链表又不行了。
魔鬼代言人 V：在第一个位置插入
一位读者在下面的评论中写道：
“[如果]你的插入总是发生在索引0或中间的某个位置。无论列表增长多大，操作都是在常数时间O(1)内完成的。对于向量，它是O(log(n))。数组越大，插入越慢。”另一位读者在我的博客上写道：
“[一个]非常常见的例子是在列表的开头添加元素。使用LinkedList这将是一个相当简单的操作（只需交换一些指针），而ArrayList [Java版动态数组] 将很难进行这种插入（移动整个数组）”
复制并粘贴我自己的文章评论回答给第一位读者：
“你上面写的是完全准确的。你不是第一个提到这一点的人，虽然它是如此正确，但也如此错误。让我解释一下。
你描述的场景非常可信。事实上，将一个数据放在另一个旧数据的前面，依此类推，可能是数据收集最常见的任务？
在这种场景下，对链表进行索引为“index 0”的插入是有意义的。这对于向量没有意义。
向量的默认插入应该通过
push_back完成。沿增长方向插入。这显然是为了避免移动整个前一部分。C++对此有充分的说明，std::vector[^]有push_back和insert，但完全缺少函数.push_front所以，我们不要天真地看待这个问题，对吧？在向量上使用
push_back，并将其与在链表上的index 0处插入进行比较，这可能是程序员会选择的有效选项。你同意吗？向量上的
push_back不需要为每个新元素都移动所有内容。当向量已满需要调整大小时的开销仍然适用。
这三种插入的代码和性能比较可以在http://ideone.com/DDEJF上看到。它比较了常见的链表操作：在“index 0”处插入 vs std::vector push_back vs 一个天真的std::vector“ push_front
From: http://ideone.com/DDEJF. Times are given in microseconds [us]
elements, list, vector, vector (naive)
10, 3, 6, 1
100, 7, 3, 13
500, 43, 7, 83
1000, 70, 10, 285
2000, 149, 27, 986
10000, 928, 159, 22613
20000, 1578, 284, 97330
40000, 3138, 582, 553636
100000, 7802, 1179, 3555756
Exiting test,. the whole measuring took 4266 milliseconds (4seconds or 0 minutes)
现在该做什么？
Donald Knuth就优化发表了以下声明：
“我们应该忘记小的效率，比如大约97%的时间：过早优化是万恶之源”.
这意味着“过早优化”是指软件开发者认为他们在对代码进行性能改进，但不知道它是否真的需要，或者是否会大大提高性能。所做的更改导致设计不再像以前那样干净，不正确或难以阅读。代码过于复杂或晦涩。这显然是一种反模式。
另一方面，我们有极端过早优化反模式的逆运算，这称为过早悲观化。过早悲观化是指程序员选择已知性能比其他技术差的技术。通常这是出于习惯或仅仅是原因。
示例1：始终复制参数而不是使用const引用。
示例2：使用后置增量++运算符而不是前置增量++。例如 value++而不是++value。
对于原生类型，前置或后置增量的成本可以忽略不计，但对于类类型，性能差异可能会产生影响。因此，总是使用value++是一个坏习惯，当用于其他类型的集合时，实际上会降低性能。出于这个原因，最好只进行前置增量。代码与后置增量一样清晰，并且性能永远不会更差。
在性能优势很小的情况下使用链表（例如只有10个元素，很少被访问）与使用向量相比仍然更差。这是一个你应该远离的坏习惯。
为什么要在有其他选择的情况下使用性能差的容器？这些选择同样清晰易用，并且不影响代码的可读性。
远离过早优化，但一定要避免落入过早悲观化的陷阱！你应该遵循最佳（最优）解决方案，当然，还要运用常识，而不必试图优化和混淆代码和设计。应该避免使用链表等次优技术，因为显然有更好的替代方案。
Java和C#
本文发布时，有一条评论大致是这样的：
这可能对C++来说是真的，但对Java或C#来说，这并不那么重要。
选择这些语言不是为了速度，而是为了更快的开发时间[等等，等等]。].
这可能是真的，但实际上，由于速度方面的问题很可能像C++代码一样影响Java和C#，所以它仍然可能很重要。
我得到了一位友好读者的帮助来进行Java的尝试。在其他读者（参考评论）提出一些修改建议后，我有一个类似的线性搜索，然后插入的例子：http://ideone.com/JOJ05。
在Java中，C++ std::list的等价物称为LinkedList。C++的动态数组std::vector在Java中称为ArrayList。这些库之间有一个很大的区别，Java的LinkedList和ArrayList都只能包含对象。这意味着包含Integer对象的ArrayList的相邻内存提升会略有降低。为了访问和比较值进行搜索，有一个额外的间接访问，从引用到值。
为了了解这对ArrayList造成了什么差异，我加入了一个DynamicIntArray，以便有一个真正对缓存友好的结构进行比较。DynamicIntArray使用int，而不是Integer对象。
对于Java，LinkedList立即表现出其性能不如ArrayList。在ideone.com的测试（http://ideone.com/JOJ05）中，LinkedList的性能比最佳数组容器慢1.5到3倍。
在我的x64超极本上，缓存架构不同，对缓存友好的结构得到了很好的提升。LinkedList比DynamicIntArray慢1.5倍到15倍，用于相同范围的元素。
Integer对象导致ArrayList变慢
在ideone.com上，使用Integer对象而不是int的额外间接开销导致ArrayList比更快的DynamicIntArray慢了大约30%。在我的x64笔记本上，ArrayList的完成时间大约是DynamicIntArray的两倍（仍然比ideone.com快）。
我的博客上展示了更多Java特定的测试，但在这里不适合。如果你想阅读更多关于它的内容（过滤、排序、big-O讨论），你可以在这里阅读。
结论
本文并非要歧视链表的所有用途。但它确实展示了链表在数字处理领域的不足。
传统上，是的，即使是现在，书籍和在线资源几乎总是完全忽视计算机架构以及这对引用局部性概念的影响。这些资源计算算法的big-O效率，并提出建议，这些建议简直是错误的，因为内存密集型和对缓存友好的结构之间存在巨大差异。实际上，缓存架构有巨大的影响。
上面我展示了C++ std::vector的一些愚蠢用法。没有使用快速的[]运算符或某种树状结构，而是让场景的设置尽可能不损害std::list，事实上，有些甚至被设计成有利于链表。它表明，对于小型、易于复制的数据、原始数字或POD，应优先选择相邻内存结构而不是不连续内存结构。动态数组（如Vector）所带来的新分配、复制、移动的可感知开销，与链表中访问元素时涉及的非常非常慢的RAM获取相比，几乎可以忽略不计。
在数字处理方面，向量或其他相邻内存结构应为默认选择，而非链表。当然，每个新情况都需要进行分析，并相应地选择数据结构和算法。明智地应用你从本文中学到的知识，只有在链表能带来数组结构难以获得的益处时才使用它。
请记住，链表的性能问题通常不是你软件的主要性能问题。但为什么要在可以轻松使用动态向量的情况下，使用一个明显次优的数据结构呢？代码的可读性相同，而将链表用于数字处理对我来说是过早悲观化的一个明显例子。
既然我们在数字处理的领域，为什么不利用你对链表缺点的理解，暂时远离链表呢？至少在你确定需要它之前。你的代码会因此受益，性能会保持不变或更好，有时甚至会好很多。
反馈
我建议查看下面的评论，也许自己也留下一个。有很多意见，甚至一些有趣的例外情况，以及由同样聪明的编码员提出的非常聪明的评论。多亏了他们，我在回应他们的担忧时，本文得到了改进。
最后，一个小小的请求。拜托，在我因为这篇固执的文章被攻击得体无完肤之前，为什么不试着在ideone.com或类似网站上运行一些示例代码，证明我是错的，并教育我。我活着就是为了学习=)
哦，是的。我知道，谢谢你的指正。还有其他容器，但这次我专注于链表与向量的比较。
参考文献
- Bjarne Stroustrup在GoingNative 2012上的主题演讲
- cplusplus.com std::list 参考
- cplusplus.com std::vector 参考
- Wikipedia关于序列容器
- Wiki.Answers: 链表与向量的区别
- WikiBooks: （链表 vs 向量）的优缺点
- Wikipedia: 链表 vs 动态数组
- Wikipedia: 关于优化和Donald Knuth
- CodeProject: 预分配的数组列表，作者Vinod Vijayan
- George Aristy的博客回复 性能比较：链表 vs. 向量 [Java]
- Future Chips: 你真的应该使用链表吗？
- MSDN博客: 展开的链表
- KjellKod.Wordpress 本文的初始博客版本： 现已镜像
- KjellKod.Wordpress Java后续文章（在读者提出改进建议后）
历史
- 2012年3月5日 从博客文章 http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/重新发布
- 2012年3月6日 更新标题和初始问题场景说明……面临并拨开迷雾，以澄清一些困惑并更好地证明观点。
- 2012年4月19日 拖延已久的改版。我的过错、引言、免责声明、结论和总体“拨开迷雾”。这应该能消除许多先前的误解……代码示例也被添加和更新了。
- 2012年8月18-21日 “魔鬼代言人V”+ Java部分更新和布局及文本的微小改动。Java版根据KjellKod.WordPress的改进建议和“博客回复”进行了更新（Java大对决）