> 技术文档 > JAVA中LinkedList和ArrayList的区别

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:高频头尾操作/中间插入删除/实现队列栈结构