Question

java 中 LinkedList 为什么增删效率高? 难道指定位置插入 就不要查询了吗?

在 LinkedList 中 我们都知道 底层是链表结构, 其特性是 查询慢 修改慢 而增删快 与 ArrayList正好相反,但是 在LinkedList中 你在制定位置插入一个元素 那么 他就不需要查询了吗? 我的意思是他难道不先查询 其位置后再插入元素吗? 如果他先找到位置再进行 添加或删除元素的 话 那不一样慢 吗?
我们都知道 如果在ArrayList中 添加一个元素或删除一个元素 会先找到 位置 然后再操作 如果 是删除一个元素 后面的元素全部向前移动 , 添加一个元素 后面的元素 全部向后推移,这样是慢的.
但是LinkedList 中查询 是慢的 虽然添加会快 但是 添加前不也得查询吗?

Answer 1

import java.util.*;
class s{
public int i;
s(int s){i=s;
}
}
public class display {
public static void main(String args[]){
LinkedList <s> s1=new LinkedList<s>();
for(int i=0;i<10;i++){
s a=new s(i);
Collections.addAll(s1,a);
}

for(s a:s1)
System.out.print(a.i+" ");
}
}

Answer 2

ArrayList是基于数组实现的，而LinkedList是基于链表实现的。ArrayList在存储的时候不仅仅是存储了数据，还给每一个数据存储了一个引用即数组下标，而在LinkedList中是没有下标的。因此，ArrayList可以通过数组下标迅速地找到要查询的数据，LinkedList查询需要重新遍历一次链表，在遍历中逐个查询，知道找到index为止。简单来说，ArrayList可以直接通过数组下标得到元素，而LinkedList则需要根据所给的下标从头部或尾部开始往下标的位置依次获得下一个元素或上一个元素。至于增删，由于ArrayList是以数组下标(引用)＋数据存储的。例如，在一个长度为10的数组中，在数组A[3]位置插入一个数据时，数组会先扩容至长度11，然后A[4]-A[9]的值会推一位，重新赋予数组下标，这时候添增的效率就好变得非常慢。而LinkList中的添加，就不用考虑引用，直接在链尾添加一个数据就行了。删除同理，望采纳，谢谢!

Answer 3

关键是在于index