java中何时使用ArrayList和LinkedList

java中何时使用ArrayList和LinkedList
一、概述

我一直简单使用:

List names = new ArrayList<>();

我将接口用作可移植性的类型名称,这样当我问诸如此类的问题时,便可以重新编写代码。

什么时候应该LinkedList使用过ArrayList

二、详解

摘要 ArrayList实现了ArrayDeque,比起LinkedList在更多使用情况。如果你不确定用哪个,请使用ArrayList


LinkedListArrayList是List接口的两种不同的实现。LinkedList用双向链表实现。ArrayList用动态调整大小的数组实现。

与标准链表和数组操作一样,各种方法将具有不同的算法运行时。

对于 LinkedList

  • get(int index)O(n)平均n / 4步),但时为O(1)(在这种情况下,您也可以使用)。的主要好处之一index = 0index = list.size() - 1getFirst()getLast() LinkedList
  • add(int index, E element)O(n)平均n / 4步),但时为O(1)(在这种情况下,您也可以使用)。的主要好处之一index = 0index = list.size() - 1addFirst()addLast()add() LinkedList
  • remove(int index)O(n)平均n / 4步),但时为O(1)(在这种情况下,您也可以使用)。的主要好处之一index = 0index = list.size() - 1removeFirst()removeLast() LinkedList
  • Iterator.remove()O(1)的主要好处之一 LinkedList
  • ListIterator.add(E element)O(1)的主要好处之一 LinkedList

注意:许多操作平均需要n / 4步,在最佳情况下(例如,索引= 0)需要恒定的步数,在最坏情况下(列表的中间)需要n / 2

对于 ArrayList

  • get(int index)O(1)主要优点 ArrayList
  • add(E element)分摊O(1),但最差情况为O(n),因为必须调整数组大小并复制该数组
  • add(int index, E element)O(n)平均n / 2步)
  • remove(int index)O(n)平均n / 2步)
  • Iterator.remove()O(n)平均n / 2步)
  • ListIterator.add(E element)O(n)平均n / 2步)

注意:许多操作平均需要n / 2步,在最佳情况下(列表结束)需要恒定的步数,在最坏情况下(列表开始)需要n

LinkedList允许使用迭代器进行固定时间的插入或删除,但只能顺序访问元素。换句话说,您可以向前或向后浏览列表,但是在列表中查找位置所花费的时间与列表的大小成正比。Javadoc说:“索引到列表中的操作将从开头或结尾遍历列表,以较近者为准”,因此,这些方法平均O(n)n / 4步),尽管O(1)index = 0

ArrayList另一方面,允许快速随机读取访问,因此您可以在固定时间内抓取任何元素。但是,从末端开始的任何地方添加或删除,都需要将后面的所有元素移开,以形成开口或填补空白。另外,如果添加的元素多于基础数组的容量,则会分配一个新数组(大小的1.5倍),并将旧数组复制到新数组中,因此在最坏的情况下将a添加ArrayListO(n)情况,但平均保持不变。

因此,根据您打算执行的操作,您应该相应地选择实现。遍历任何一种List实际上都是很便宜的。(从ArrayList技术上讲,迭代速度更快,但是除非您执行的操作确实对性能敏感,否则您不必为此担心-它们都是常量。)

LinkedList当您重复使用现有迭代器来插入和删除元素时,使用generic的主要好处然后可以通过仅在本地更改列表O(1)中完成这些操作在阵列列表中,阵列的其余部分需要移动(即复制)。另一方面,在最坏的情况下LinkedListO(n)n / 2步)的链接寻找均值,而在ArrayList所需位置可以数学计算并在O(1)中访问

使用的另一个好处LinkedList出现当您从列表的头部添加或删除,因为这些操作是O(1) 而他们是为O(n)进行ArrayList请注意,这ArrayDeque可能是LinkedList从头部添加和移除的一个很好的选择,但不是List

另外,如果列表很大,请记住,内存使用情况也有所不同。a的每个元素LinkedList都有更多的开销,因为还存储了指向下一个和上一个元素的指针。ArrayLists没有这个开销。但是,ArrayLists无论是否实际添加了元素占用的内存都应为该容量分配的内存。

的默认初始容量ArrayList很小(Java 1.4-1.8中为10)。但是由于底层实现是一个数组,因此如果添加很多元素,则必须调整数组的大小。为了避免在确定要添加很多元素时调整大小的高成本,请ArrayList以更高的初始容量构造

如若转载,请注明出处:https://www.javaidea.cn/article/8210.html

(0)
上一篇 2022年2月7日 上午10:03
下一篇 2022年2月7日 上午10:03

相关推荐

发表评论

您的电子邮箱地址不会被公开。