单链表查询效率为什么比数组高

Question

单链表查询指定元素的时间复杂度是O(n),数组查询指定元素的时间复杂度也是O(n),两者的查询效率有什么区别？请老师指点，谢谢。

Answer 1

城南大师兄 2019-10-27 14:17:29

单链表和数组从数据结构而言，实际上是一样的，不过从内存分配上就不一样了，因为数组的内存排布是连续的，而链表中每个节点的内存是随机的，所以从这个角度来说数组要比单链表快

Answer 2

阿俊XX 2019-11-01 01:26:31

     数组的数据结构是由一块连续存储的内存地址组成，声明一个位数为9的string数组，则对应初始化一个类似于[null(0)，null(1)…]的内存地址。对数组的访问是通过连续存储地址的索引来获取，查询为o(1)的复杂度，但如果要删除一个元素，或者在已有元素中插入元素，时间复杂度则为o(n)。因为需要对当前索引以后的元素依次后移，如果你有10 0万的元素，做删除操作，光想想就令人可怕!        而链表恰恰解决了这个问题，至始至终链表是由一个头节点不断指向尾节点而存在的数据结构，1–>6–>5–>7–>9–>4–>2–>NULL, 如果要删除7这个节点，只需要讲5的next 指针指向7的下级元素 9即可，就形成了一个新的链表。如果要新增同理，链表的删除，新增，修改操作，都只修改上级next指针，而不修改所有下级next指针，则复杂度为o(1)，当然世界上没有一种完美的数据结构，如果有就没有其他数据结构存在的必要了。链表的短板就是查询速度，如果要查询一组10万个元素组成的链表中的第5万位，则需要从1一直查到5万位，时间复杂度o(n)可想而知，然而数组依靠了他它连续存储的内存空间中的索引特性，实现了o(1)的查找。           那么如果一个容器结合了链表与数组然后扬长避短岂不是天下无敌，而HashMap则是这样强大的容器，jdk1.8以后为了应对hash碰撞攻击，还新增了强大的红黑树结构，除了线程不安全，近乎完美，同学们加油学吧。

Answer 3

煎鱼侠 2020-07-22 14:44:41

指定查询元素的效率没有太大区别，如果是数组按游标查询效率高，比如array[3]  这个查询的效率就是o(1)