您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识

为何主流语言中，无任何技巧下直接暴力遍历数组、链表，多数情况链表更快？

数组,链表,地址为何主流语言中，无任何技巧下直接暴力遍历数组、链表，多数情况链表更快？

发布时间：2019-02-08加入收藏来源：互联网点击：

问题补充： 在大部分的主流程序设计语言中(例如C/C++，Java)，链表、数组都存储相同类型的元素。直接以最简陋地方式，一个元素一个元素地依次遍历(不使用任何技巧，例如缓存行对齐)，大部分情况下，链表要比数组遍历速度更快，即使慢，也一点都不明显。有的人提到：可能是连续生成的链表节点在内存中的物理分布比较紧凑导致的。但问题是，数组元素不应该一直都是完全紧凑的嘛？也不应该出现数组比链表慢的情况呀？补充完善一下这个问题吧：①链表的节点都是连续建立并添加的；②在存储元素都是指针/引用的情况下，Cache仍偏心数组吗？③遍历的同时，肯定都是会进行其它操作的，哪有光赋值，不干事的呀？④没有优化！就是传统的循环！⑤在不同数量级下，数组有时会更快点，但是总体分布情况是链表稍快。

回答于 2019-09-11 08:43:50

回答于 2019-09-11 08:43:50

首先搞清楚数组和链表的差异。

数组是在一整块连续的内存中存储数据，每一项数组成员大小相同。保存数组需要记录数组的起始地址、数组成员占用内存大小、数组长度；数组成员中记录了数据、类型。

下面用一个便于理解的方式举个关于数组的例子：

某数组起始位置在内存地址0上，每个数组成员占10byte，那么[0]在内存地址0，[2]在内存地址20，遍历数组的方式是根据数组起始位置+索引*数组成员大小。

链表是存储不需要一整块连续的内存，保存链表只要记录链表表头地址即可；每一项链表成员中保存了数据、数据类型、下一个成员的地址，另双向链表还会保存上一个成员的地址。

下面用一个便于理解的方式举个关于链表的例子：

某链表的表头在内存地址1000，访问它可获得数据和下一项数据地址是1234，遍历链表的方式是依次访问每一链的数据和下一链的地址，下一链的地址是直接获取，不需要计算。

再来说说题主的问题，为什么通常只是遍历那么链表性能略好一些，因为遍历链表时少做了一个加法和一个乘法运算。

那么实际上为啥链表总得很少数组用得很多呢？

原因主要有2条：

一、按索引随机访问成员时数组的效率比链表高很多。即顺序访问链表性能略高于数组，随机访问数组性能远高于链表。整体性能数组胜出。

二、使用数组时数组是连续存储，产生的内存碎片的几率和数量比链表少很多。

最后：所有的编程语言都支持数组，有相当多的编程语言不直接支持链表。因为链表的功能和数组的功能重叠，综合性能略差，而且使用链表要直接接触内存地址，容易产生内存地址越界、数据不安全的情况。

回答于 2019-09-11 08:43:50

Show me the code. 下结论前先要证明你的结论是对的。

据我所知，没有任何一个语言“只是遍历”的话，链表会比数组快。

链表是否连续生成的，不会影响遍历速度。

回答于 2019-09-11 08:43:50

因为，内部要重新计算地址。

获取数组地址，0*4

如果你自己读一次，就偏移一次地址，那么数组会更快。

但是，加入，插入，链表速度无敌。缺点是，链表更吃内存。

回答于 2019-09-11 08:43:50

光说没有凭据，你先把你写的测试程序贴出来才好分析，大概是你的测试程序有问题