首页 > 代码库 > ArrayList和LinkedList的区别

ArrayList和LinkedList的区别

2024-07-13 22:53:26   229人阅读

1.ArrayList和LinkedList的大致区别
(1).ArrayList是基于动态数组的数据结构，LinkedList基于链表的数据结构。 
ArrayList：elementData[size]存储，动态增加时是50%，有可能造成内存的浪费。
LinkedList：多少个size就内部创建出对应的Node对象(保存数据，previous，next)，比较消耗内存空间。


(2).对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。 
--get(index)
ArrayList(ok)：直接访问索引的数组，elementData[index]
LinkedList：判断index小于size，则从第一个开始next到个index的Node。index大于size，则从最后一个开始previous到index的Node


--set(index,newValue)
ArrayList(ok)：elementData[index] = newValue。
LinkedList：同样通过上面的遍历方式找到index的Node，再进行newValue的赋值。




(3).对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。 
--add(obj)，remove(obj)：从前面开始添加/删除元素的性能差不多。
ArrayList(ok)：elementData[size++] = obj;
LinkedList(ok)：直接通过last的标示找到最后一个Node，新建一个Node关联到最后一个Node。
--实例：
public class TestList {
private static long test(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 50000; i++)
list.add(new Object());
return System.currentTimeMillis() - start;
}


public static void main(String[] args) {
System.out.println("ArrayList耗时：" + test(new ArrayList()));
System.out.println("LinkedList耗时：" + test(new LinkedList()));
}
}
--执行结果：
ArrayList耗时：2
LinkedList耗时：3


--add(index,obj)，remove(index)：在前面开始添加元素。
ArrayList：通过System.arraycopy，创建一个新数组，在index位置留空，再elementData[index] = element;
LinkedList(ok)：通过上面的方法查找到index的Node，再将obj新建成Node关联到index的Node。
--实例：
list.add(0, new Object());
--执行结果：
ArrayList耗时：296
LinkedList耗时：3




(4).高效的随机元素访问
ArrayList：implements RandomAccess
for (int i=0, i<list.size(); i++)
list.get(i);


LinkedList：每次get(i)，都会按上面的方式遍历一次，所以不如通过it.next()的查询快速
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();




2.总结
ArrayList：添加或删除>后面的数据，查询>支持随机访问，且使用for遍历
LinkedList：添加或删除>前面或中间的数据，查询>顺序访问，且使用iterator遍历
当操作是在一列数据的后面添加数据而不是在,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；
当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了


联系
我们