我一直是一个简单使用的人:
List<String> names = new ArrayList<>();
我使用 interface 作为portability的类型名称,因此当我提出这样的问题时,我可以重新编写我的代码。
什么时候应该LinkedList用完,ArrayList反之亦然?
LinkedList
ArrayList
在更多ArrayList的用例中,总结比. 如果您不确定 - 只需从.ArrayDeque``LinkedList``ArrayList
ArrayDeque``LinkedList``ArrayList
TLDR,在 ArrayList 中访问一个元素需要常数时间 [O(1)],而添加一个元素需要 O(n) 时间[最坏情况]。在 LinkedList 中添加元素需要 O(n) 时间,访问也需要 O(n) 时间,但 LinkedList 比 ArrayList 使用更多内存。
LinkedList并且ArrayList是 List 接口的两种不同实现。LinkedList用双向链表实现它。ArrayList使用动态调整大小的数组来实现它。
与标准链表和数组操作一样,各种方法将具有不同的算法运行时。
为了 LinkedList
get(int index)
index = 0
index = list.size() - 1
getFirst()
getLast()
LinkedList<E>
add(int index, E element)
addFirst()
addLast()
add()
remove(int index)
removeFirst()
removeLast()
Iterator.remove()
ListIterator.add(E element)
注意:许多操作平均需要n/4步,在最佳情况下(例如 index = 0)需要恒定的步数,在最坏情况下需要n/2步(列表中间)
为了 ArrayList
ArrayList<E>
add(E element)
注意:许多操作平均需要n/2步,最佳情况下(列表末尾)的步数恒定,最坏情况下(列表开头)需要n步
LinkedList<E>`允许*使用迭代器*进行恒定时间的插入或删除,但只能顺序访问元素。换句话说,您可以向前或向后遍历列表,但在列表中查找位置所花费的时间与列表的大小成正比。Javadoc 说*“索引到列表中的操作将从开头或结尾遍历列表,以较近者为准”*,因此这些方法平均为*O* *(n)*(*n/4*步),尽管对于.`index = 0
ArrayList<E>,另一方面,允许快速随机读取访问,因此您可以在恒定时间内抓取任何元素。但是从任何地方添加或删除,但最后需要将所有后面的元素转移过来,要么打开一个开口,要么填补空白。另外,如果添加的元素多于底层数组的容量,则会分配一个新数组(大小的 1.5 倍),并将旧数组复制到新数组中,因此添加到 an最坏的情况ArrayList是O(n)情况但平均保持不变。
因此,根据您打算执行的操作,您应该相应地选择实现。迭代任何一种 List 实际上同样便宜。(迭代 anArrayList在技术上更快,但除非你正在做一些真正对性能敏感的事情,否则你不应该担心这一点——它们都是常量。)
LinkedList`当您重新使用现有的迭代器来插入和删除元素时,使用 a 的主要好处就出现了。然后可以通过仅在本地更改列表在*O(1)中完成这些操作。*在数组列表中,数组的其余部分需要*移动*(即复制)。另一方面,在最坏的情况下,按照*O(n)*`LinkedList`中的链接(*n/2*步)寻找方法,而在所需位置可以通过数学计算并在*O(1)*中访问。`ArrayList
LinkedList当您从列表的头部添加或删除时,使用 a 的另一个好处会出现,因为这些操作是O(1) ,而对于,它们是O(n)ArrayList。请注意,这ArrayDeque可能是LinkedList添加和删除头部的一个很好的替代方法,但它不是List.
ArrayDeque
List
此外,如果您有大型列表,请记住内存使用量也不同。a 的每个元素LinkedList都有更多的开销,因为指向下一个和前一个元素的指针也被存储。ArrayLists没有这个开销。但是,ArrayLists无论是否实际添加了元素,都会占用为容量分配的内存。
ArrayLists
an 的默认初始容量ArrayList非常小(Java 1.4 - 1.8 为 10)。但是由于底层实现是一个数组,如果添加很多元素,则必须调整数组的大小。当您知道要添加大量元素时,为避免调整大小的高成本,请ArrayList使用更高的初始容量构建。
如果从数据结构的角度来理解这两种结构,LinkedList 基本上是一个包含头节点的顺序数据结构。Node 是两个组件的包装器:一个 T 类型的值 [通过泛型接受] 和另一个对链接到它的 Node 的引用。所以,我们可以断言它是一个递归数据结构(一个节点包含另一个节点,另一个节点有另一个节点,依此类推......)。如上所述,在 LinkedList 中添加元素需要线性时间。
ArrayList 是一个可增长的数组。它就像一个常规数组。在后台,当添加一个元素并且 ArrayList 已经满载时,它会创建另一个大小大于先前大小的数组。然后将元素从先前的数组复制到新数组,并且要添加的元素也放置在指定的索引处。