何时通过ArrayList使用LinkedList?

我一直只使用一个:

List<String> names = new ArrayList<>();

我使用接口作为可移植性的类型名称,以便当我提出这些问题时,我可以重写我的代码。

什么时候应该LinkedList用完,ArrayList反之亦然?


TL; DR ArrayListArrayDeque在优选的更多的用例比LinkedList。不知道 – 刚开始ArrayList


LinkedList并且ArrayList是List接口的两个不同的实现。LinkedList用双链表实现它。ArrayList用动态调整大小的数组来实现它。

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

对于 LinkedList<E>

  • get(int index)O(n / 4)平均值
  • add(E element)O(1)
  • add(int index, E element)O(n / 4)的平均值,
    O(1)index = 0 <—主要受益LinkedList<E>
  • remove(int index)O(n / 4)平均值
  • Iterator.remove()O(1) <—的主要好处之一LinkedList<E>
  • ListIterator.add(E element)O(1) <—的主要好处之一LinkedList<E>

注:O(n / 4)是平均值,O(1)最好情况(例如索引= 0),O(n / 2)最差情况(列表中)

对于 ArrayList<E>

  • get(int index)O(1) <—的主要好处之一ArrayList<E>
  • add(E element)O(1)分期付款,但O(n)最坏的情况,因为数组必须调整大小并复制
  • add(int index, E element)O(n / 2)平均值
  • remove(int index)O(n / 2)平均值
  • Iterator.remove()O(n / 2)平均值
  • ListIterator.add(E element)O(n / 2)平均值

注:O(n / 2)是平均值,O(1)最好的情况(列表的结尾),O(n)最差的情况(列表的开始)

LinkedList<E>允许使用迭代器进行恒定时间的插入或删除,但只能按顺序访问元素。换句话说,您可以向前或向后走列表,但在列表中查找位置需要与列表大小成比例的时间。Javadoc说:“索引到列表中的操作将从头到尾遍历列表,两者中较近的一个”,所以这些方法平均为O(n / 4),尽管O(1)index = 0

ArrayList<E>另一方面,允许快速的随机读取访问,所以你可以在任何时间获取任何元素。但是,除了最终的目的地之外,添加或删除任何内容都需要将所有后面的元素转移,以便开放或填补空白。此外,如果您比下面阵列的容量添加更多的元件,一个新的数组(1.5倍的尺寸)被分配,而旧的阵列被复制到新的一个,因此添加到ArrayListO(n)的在最坏的但平均情况不变。

所以根据你打算做的操作,你应该选择相应的实现。迭代任何一种List几乎同样便宜。(迭代迭代在ArrayList技术上更快,但除非你对性能敏感,否则不应该担心这一点 – 它们都是常量。)

LinkedList当您重新使用现有的迭代器插入和删除元素时,使用a的主要好处就会产生。这些操作可以在O(1)中通过仅在本地修改列表完成。在数组列表中,数组的其余部分需要移动(即复制)。另一方面,LinkedListO(n / 2)中寻找最差情况下的链接,而在ArrayList期望的位置可以通过数学计算并在O(1)中访问。

LinkedList由于这些操作是O(1),而它们是O(n) for ,因此在添加或从列表头部添加或删除时使用a的另一个好处ArrayList。请注意,这ArrayDeque可能是一个很好的替代方法,LinkedList用于从头部添加和删除,但它不是List

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

an的默认初始容量ArrayList非常小(10个来自Java 1.4 – 1.8)。但是由于底层实现是一个数组,因此如果添加大量元素,则必须调整数组的大小。为了避免在知道要添加大量元素时调整大小的高成本,请使用ArrayList较高的初始容量构建。


到目前为止,似乎没有人能够解决这些列表中每个列表的内存占用情况,除了a LinkedList比“更多”更普遍的共识之外,ArrayList所以我进行了一些数字处理,以准确演示两个列表对N个空引用的占用程度。

由于引用在其相关系统上是32位或64位(即使为空),我已经包含了4组数据,分别是32位LinkedLists和64位ArrayLists

注意:所显示的ArrayList线的尺寸用于修剪列表 – 实际上,an中的后台阵列的容量ArrayList通常大于其当前的元素数量。

注2:( 感谢BeeOnRope)由于CompressedOops现在默认从JDK6开始,所以64位机器的值基本上与32位的机器相匹配,除非你明确地关闭它。

结果清楚地表明,这个数字LinkedList远远超过了ArrayList,特别是在元素数量非常高的情况下。如果记忆是一个因素,请避开LinkedLists

我使用的公式如下,让我知道如果我做错了什么,我会修复它。对于32或64位系统,’b’是4或8,’n’是元素的数量。注意mods的原因是因为java中的所有对象都占用8个字节的倍数,而不管它是否全部使用。

ArrayList

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

添加评论

友情链接:蝴蝶教程