何时通过ArrayList使用LinkedList?
我一直只使用一个:
List<String> names = new ArrayList<>();
我使用接口作为可移植性的类型名称,以便当我提出这些问题时,我可以重写我的代码。
什么时候应该LinkedList
用完,ArrayList
反之亦然?
TL; DR ArrayList
与ArrayDeque
在优选的多更多的用例比LinkedList
。不知道 – 刚开始ArrayList
。
LinkedList
并且ArrayList
是List接口的两个不同的实现。LinkedList
用双链表实现它。ArrayList
用动态调整大小的数组来实现它。
与标准链表和数组操作一样,各种方法将具有不同的算法运行时。
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倍的尺寸)被分配,而旧的阵列被复制到新的一个,因此添加到ArrayList
是O(n)的在最坏的但平均情况不变。
所以根据你打算做的操作,你应该选择相应的实现。迭代任何一种List几乎同样便宜。(迭代迭代在ArrayList
技术上更快,但除非你对性能敏感,否则不应该担心这一点 – 它们都是常量。)
LinkedList
当您重新使用现有的迭代器插入和删除元素时,使用a的主要好处就会产生。这些操作可以在O(1)中通过仅在本地修改列表完成。在数组列表中,数组的其余部分需要移动(即复制)。另一方面,LinkedList
在O(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)