JAVA中LinkedList和ArrayList的区别
目录
一,LinkedList和ArrayList本质的区别
ArrayList是Array(动态数组)的数据结构,LinkedList是Link(链表)的数据结构。
二,LinkedList和ArrayList效率的区别
1.当随机访问List(get和set操作)时,ArrayList比LinkedList的效率更高,因为LinkedList是线性的数据存储方式,所以需要移动指针从前往后依次查找。
当对数据进行增加和删除的操作(add和remove操作)时,LinkedList比ArrayList的效率更高,因为ArrayList是数组,所以在其中进行增删操作时,会对操作点之后所有数据的下标索引造成影响,需要进行数据的移动。
2.从名字就可以看出,ArrayList和LinkedList的区别,ArrayList是基于数组的,LinkedList是基于链表的。所以ArrayList适合查询,LinkedList适合插入。
对于ArrayList,它真正的优点是按下标查询元素,相比于LinkedList,LinkedList也可以按下标查询元素,但是LinkedList需要对底层链表进行遍历,才能找到指定下标的元素,而ArrayList不用,所以这是ArrayList的优点。但是,如果我们讨论的是获取第一个元素,或最后一个元素,ArrayList和LinkedList在性能上是没有区别的,因为LinkedList中有两个属性分别记录了当前链表中的头结点和尾结点,并不需要遍历链表。
ArrayList可以插入到指定下标位置,或者数组末尾,这种插入是很快的,但如果某次插入操作触发了扩容,那么本次插入就增加了额外的扩容成本。
对于LinkedList,如果是插在链表的头部或者是尾部都是很快的,因为LinkedList中有单独的属性记录的链表的头结点和尾结点,不过,如果是插在指定下标位置,那么就需要遍历链表找到指定位置,那么效率会变低。
三,LinkedList和ArrayList方法的区别
1.在LinkedList中提供了增删改查等方法,ArrayList中也有同样的方法 但因为LinkedList类似于链表的缘故,在增加的时候比ArrayList多了下列方法
-
头部操作:
addFirst(E e)
/offerFirst(E e)
:头部插入 -
getFirst()
/peekFirst()
:获取头部元素 -
removeFirst()
/pollFirst()
:移除头部元素 -
尾部操作:
-
addLast(E e)
/offerLast(E e)
:尾部插入 -
getLast()
/peekLast()
:获取尾部元素 -
removeLast()
/pollLast()
:移除尾部元素
-
而ArrayList也有特有的优化方法
虽然两者都支持标准迭代器,但由于底层结构不同,性能表现各异:
ArrayList:
LinkedList:
-
ensureCapacity(int minCapacity)
:手动扩容,避免多次自动扩容开销 -
trimToSize()
:释放多余空间,使容量等于当前大小 -
toArray(T[] a)
:转换为指定类型数组 - 迭代器基于数组索引,随机访问快
- 支持快速随机访问的ListIterator
- 迭代器需要逐个节点访问
- ListIterator双向遍历更高效(因为本身是双向链表)
- 迭代过程中修改结构不会立即抛出ConcurrentModificationException(相比ArrayList)
-
// ArrayList迭代for (int i = 0; i < arrList.size(); i++) { arrList.get(i); // 随机访问高效}// LinkedList迭代(正确方式)for (Iterator it = linkList.iterator(); it.hasNext();) { it.next(); // 顺序访问}
四,LinkedList和ArrayList特点的区别
-
特性 ArrayList LinkedList 底层结构 动态数组 双向链表 随机访问 O(1) O(n) 头部插入/删除 O(n) O(1) 尾部插入/删除 O(1) O(1) 中间插入/删除 O(n) O(n)(遍历)+O(1)(修改) 内存占用 连续内存,可能预留空间 非连续,每个节点多2指针 迭代效率 更适合顺序访问 更适合双向遍历 适用场景 高频随机访问/尾部操作 高频头尾操作/中间插入删除 五,总结
-
1.底层数据结构
-
ArrayList:基于动态数组,内存连续储存
-
LinkedList:基于双向链表,节点包含前后指针
-
2.访问性能
-
ArrayList:随机访问O(1)(直接索引)
-
LinkedList:随机访问O(n)(需遍历)
-
3.插入/删除性能
-
ArrayList:
中间/头部操作O(n)(需移动元素)
-
尾部操作O(1)(扩容时O(n))
-
LinkedList:
-
中间操作O(n)(遍历)+O(1)(修改指针)
-
头尾操作O(1)
-
4.适用场景
-
优先ArrayList:高频随机访问/尾部操作/内存敏感场景
-
优先LinkedList:高频头尾操作/中间插入删除/实现队列栈结构