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

Question

rt，大家一起来讨论下吧！

Answer 1

是的，所以这种情况用hashmap之类的。可以快速定位。

Answer 2

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