数组与链表的增删效率比较

[caizhigang97]

都说数组的查询效率高，链表的增删效率高。我想这句话不应该是绝对的吧？还是要靠自己实践啊。问题如下： 增删其实不仅仅是增删，它还包括查，增删的过程如下： 增：找到插入该元素的位置，插入该元素 删：找到删除该元素的位置，删除该元素 既然增删包括了查，而在查这一方面，数组效率比链表高，又怎么能肯定地说链表增删效率比数组高呢？

[wayss000]

假如现在数组和链表均有100个元素，你需要向index=10的位置插入一个元素。 对于数组来说，在查完的基础上，需要把原先从第10个到第100个元素均向后移动； 对于链表来说，在查完的基础上，只需要把原先第9个元素的next指向新插入的元素，把新插入的元素指向原先第10个元素。

[miejiededaxiang]

楼主的考虑是正确的，链表的增删也需要遍历，如果是较少数据，增删确实比数组效率高；当数据比较大，在双向链表接近头部和尾部的增删效率比数组高，在接近中间位置的效率是不如数组的。