java集合:Arraylist与linkedlist的区别

1、Arraylist与linkedlist的区别

arraylist和linkedlist的区别是：数据结构不同，效率不同，自由性不同，主要控件开销不同。

（1）、数据结构不同

ArrayList是Array(动态数组)的数据结构，LinkedList是Link(链表)的数据结构。

（2）、效率不同

当随机访问List（get和set操作）时，ArrayList比LinkedList的效率更高，因为LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找，重新排序。

@Test

public void test04(){//修改

ArrayList list=new ArrayList();

for (int i=0;i<10;i++){

list.add("李昊哲"+i);

}

System.out.println(list);

list.set(6,"张三");

System.out.println(list);

}

@Test

public void test08(){

LinkedList list=new LinkedList<>();

for (int i=0;i<10;i++){

list.add("李昊哲"+i);

}

System.out.println(list);

list.set(6,"张三");

System.out.println(list);

}

[李昊哲0, 李昊哲1, 李昊哲2, 李昊哲3, 李昊哲4, 李昊哲5, 李昊哲6, 李昊哲7, 李昊哲8, 李昊哲9]

[李昊哲0, 李昊哲1, 李昊哲2, 李昊哲3, 李昊哲4, 李昊哲5, 张三, 李昊哲7, 李昊哲8, 李昊哲9]

当对数据进行增加和删除的操作(add和remove操作)时，LinkedList比ArrayList的效率更高，因为ArrayList是数组，所以在其中进行增删操作时，会对操作点之后所有数据的下标索引造成影响，需要进行数据的移动。

@Test

public void test06() {//插入

ArrayList list = new ArrayList();

for (int i = 0; i < 10; i++) {

list.add("李昊哲" + i);

}

System.out.println(list);

list.add("张三");

System.out.println(list);

}

@Test

public void test07(){

LinkedList list=new LinkedList<>();

for (int i = 0; i < 10; i++) {

list.add("李昊哲" + i);

}

System.out.println(list);

list.add(7,"张三");

System.out.println(list);

}

[李昊哲0, 李昊哲1, 李昊哲2, 李昊哲3, 李昊哲4, 李昊哲5, 李昊哲6, 李昊哲7, 李昊哲8, 李昊哲9]

[李昊哲0, 李昊哲1, 李昊哲2, 李昊哲3, 李昊哲4, 李昊哲5, 李昊哲6, 张三, 李昊哲7, 李昊哲8, 李昊哲9]

（3）自由性不同

ArrayList自由性较低，因为它需要手动的设置固定大小的容量，但是它的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用；而LinkedList自由性较高，能够动态的随数据量的变化而变化，但是它不便于使用。

（4）主要控件开销不同

ArrayList主要控件开销在于需要在lList列表预留一定空间；而LinkList主要控件开销在于需要存储节点信息以及节点指针

ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

对于随机访问get和set，ArrayList绝对优于LinkedList，因为LinkedList要移动指针

对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

ArrayList：内部使用数组的形式实现了存储，实现了RandomAccess接口，利用数组的下标进行元素的访问，因此对元素的随机访问速度非常快。因为是数组，所以ArrayList在初始化的时候，有初始大小10，插入新元素的时候，会判断是否需要扩容，扩容的步长是0.5倍原容量，扩容方式是利用数组的复制，因此有一定的开销；

另外，ArrayList在进行元素插入的时候，需要移动插入位置之后的所有元素，位置越靠前，需要位移的元素越多，开销越大，相反，插入位置越靠后的话，开销就越小了，如果在最后面进行插入，那就不需要进行位移

LinkedList：内部使用双向链表的结构实现存储，LinkedList有一个内部类作为存放元素的单元，里面有三个属性，用来存放元素本身以及前后2个单元的引用，另外LinkedList内部还有一个header属性，用来标识起始位置，LinkedList的第一个单元和最后一个单元都会指向header，因此形成了一个双向的链表结构。

LinkedList是采用双向链表实现的。所以它也具有链表的特点，每一个元素（结点）的地址不连续，通过引用找到当前节点的上一个节点和下一个节点，即插入和删除效率较高，只需要常数时间，而get和set则较为低效。

LinkedList的方法和使用和ArrayList大致相同，由于LinkedList是链表实现的，所以额外提供了在头部和尾部添加/删除元素的方法，也没有ArrayList扩容的问题了。另外，ArrayList和LinkedList都可以实现栈、队列等数据结构，但LinkedList本身实现了队列的接口，所以更推荐用LinkedList来实现队列和栈。