讨论帖：为什么数组的查询效率较高，增删的效率很低，而链表却刚好相反

rt，大家一起来讨论下吧！ --------------------编程问答-------------------- 因为数组有数组下标也就是序号，所以查询非常方便，只要你指定要哪个下标号码的值就行。
增删效率低也是因为需要维护这个序号。
链表不维护序号，所以增删直接操作，将前面指向他后面一个操作就完成了。但查询效率就低啊，得全链表扫描。 --------------------编程问答-------------------- 哈哈，这个还要讨论吗？
--------------------编程问答--------------------

引用 1 楼  的回复:

因为数组有数组下标也就是序号，所以查询非常方便，只要你指定要哪个下标号码的值就行。
增删效率低也是因为需要维护这个序号。
链表不维护序号，所以增删直接操作，将前面指向他后面一个操作就完成了。但查询效率就低啊，得全链表扫描。

好像有道理哈。但是如果在一组乱序的数组中查找到某个数的位置，不知道下标的情况下，不都还得遍历整个数组和整个链表？ --------------------编程问答--------------------

引用 1 楼  的回复:

因为数组有数组下标也就是序号，所以查询非常方便，只要你指定要哪个下标号码的值就行。
增删效率低也是因为需要维护这个序号。
链表不维护序号，所以增删直接操作，将前面指向他后面一个操作就完成了。但查询效率就低啊，得全链表扫描。

就是这个 --------------------编程问答--------------------

引用 3 楼  的回复:

引用 1 楼  的回复:
因为数组有数组下标也就是序号，所以查询非常方便，只要你指定要哪个下标号码的值就行。
增删效率低也是因为需要维护这个序号。
链表不维护序号，所以增删直接操作，将前面指向他后面一个操作就完成了。但查询效率就低啊，得全链表扫描。

好像有道理哈。但是如果在一组乱序的数组中查找到某个数的位置，不知道下标的情况下，不都还得遍历整个数组和整个链表？

是的，所以这种情况用hashmap之类的。可以快速定位。 --------------------编程问答-------------------- 有它本身的数据结构决定的，诚如一口所说。 --------------------编程问答-------------------- ........

回个贴加点分下次问问题。

对于查找，ls说法都不全，你找之前根本不知道要找的元素位于链表或者数组的那一处地方，因此其实都是遍历操作，那表面上复杂度都是O(n)
真正的问题其实是        计算机组成原理    里讲的局部性原理，链表由于存放的地方在内存中是分散的，因此cpu的基地址寄存器等等必须重新赋值，而数组这一过程是不要的。因此对于查询来说，数组的效率更好。这也是

操作系统中，多个进程产生的多个PCB一般由数组实现的原因，尽管PCB修改删除过程很多。 --------------------编程问答-------------------- 因为数组增删的时候需要移动大量的数据，比如你在位置i删除一个元素，那么之后的元素都需要往前移动，所以效率低下，而链表就不存在这个问题。 --------------------编程问答-------------------- 如果你知道插入排序过程，就好理解了!

补充：Java ,  Java SE