何时在Java中使用LinkedList over ArrayList？

我一直只是一个人使用：

List names = new ArrayList(); 

我使用接口作为可移植性的类型名称，因此当我问这些问题时，我可以重新编写代码。

何时应该使用LinkedList而不是ArrayList ，反之亦然？

Answer 1

摘要 ArrayList与ArrayDeque在更多用例中比LinkedList更可取。 如果您不确定 – 只需从ArrayList开始。

---

LinkedList和ArrayList是List接口的两种不同实现。 LinkedList使用双向LinkedList实现它。 ArrayList使用动态重新resize的数组来实现它。

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

对于LinkedList

• get(int index)是O（n） （平均n / 4步）
• add(E element)是O（1）
• add(int index, E element)是O（n） （平均n / 4步），但当index = 0时O（1） <--- LinkedList主要好处LinkedList
• remove(int index)是O（n） （平均n / 4步）
• 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步），但index = 0 O（1） index = 0 。

另一方面， ArrayList允许快速随机读取访问，因此您可以在恒定时间内获取任何元素。 但是，除了末端之外的任何地方添加或移除都需要将所有后面的元素移位，以便打开或填补空白。 此外，如果添加的元素多于底层数组的容量，则会分配一个新数组（大小的1.5倍），并将旧数组复制到新数组，因此添加到ArrayList是O（n）最坏的情况，但平均不变。

因此，根据您打算执行的操作，您应该相应地选择实现。 迭代任何一种List实际上同样便宜。 （迭代一个ArrayList在技​​术上更快，但除非你做的事情对性能非常敏感，否则你不应该担心这一点 – 它们都是常量。）

当您重用现有迭代器来插入和删除元素时，会出现使用LinkedList的主要好处。 然后，可以通过仅在本地更改列表，在O（1）中完成这些操作。 在数组列表中，需要移动 （即复制）数组的其余部分。 另一方面，在LinkedList意味着在最坏情况下遵循O（n） （ n / 2步）中的链接，而在ArrayList ，可以在数学上计算所需位置并在O（1）中访问。

当您从列表的头部添加或删除时，会出现使用LinkedList另一个好处，因为这些操作是O（1） ，而它们是ArrayList O（n） 。 请注意， ArrayDeque可能是LinkedList一个很好的替代品，用于添加和删除头部，但它不是List 。

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

ArrayList的默认初始容量非常小（Java 1.4中的10个 – 1.8）。 但由于底层实现是一个数组，因此如果添加大量元素，则必须调整数组大小。 当您知道要添加大量元素时，为了避免resize的高成本，请构造具有更高初始容量的ArrayList 。

Answer 2

到目前为止，似乎没有人解决这些列表中每个列表的内存占用情况，除了一般认为LinkedList比ArrayList “更多”所以我做了一些数字处理以准确地certificate两个列表占用了多少N个空引用。

由于在它们的相对系统上引用是32位或64位（即使为空），我已经为32位和64位LinkedLists和ArrayLists包含了4组数据。

注意： ArrayList行显示的大小用于修剪列表 – 实际上， 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) 

Answer 3

ArrayList就是你想要的。 LinkedList几乎总是（性能）错误。

为什么LinkedList糟糕：

• 它使用大量小内存对象，因此会影响整个过程的性能。
• 很多小对象都不利于缓存局部性。
• 任何索引操作都需要遍历，即具有O（n）性能。 这在源代码中并不明显，导致算法O（n）比使用ArrayList时慢。
• 获得良好的表现很棘手。
• 即使big-O性能与ArrayList相同，它也可能会明显变慢。
• 在源代码中看到LinkedList是很不耐烦的，因为它可能是错误的选择。

Answer 4

作为一个在非常大规模的SOA Web服务上进行操作性能工程大约十年的人，我更喜欢LinkedList相对于ArrayList的行为。 虽然LinkedList的稳态吞吐量更差，因此可能导致购买更多硬件 – ArrayList在压力下的行为可能导致集群中的应用程序在几乎同步的情况下扩展其arrays，并且对于大型arrays可能导致缺乏响应性在应用程序和停电，而在压力下，这是灾难性的行为。

类似地，您可以从默认吞吐量终身垃圾收集器中获得更好的应用程序吞吐量，但是一旦获得具有10GB堆的Java应用程序，您可以在完整GC期间锁定应用程序25秒，这会导致SOA应用程序超时和失败并且如果太频繁发生，则会破坏您的SLA。 即使CMS收集器占用更多资源并且无法实现相同的原始吞吐量，但它是一个更好的选择，因为它具有更可预测和更小的延迟。

如果性能的全部意思是吞吐量，并且您可以忽略延迟，那么ArrayList只是性能的更好选择。 根据我的工作经验，我不能忽视最坏情况的延迟。

Answer 5

 Algorithm ArrayList LinkedList seek front O(1) O(1) seek back O(1) O(1) seek to index O(1) O(N) insert at front O(N) O(1) insert at back O(1) O(1) insert after an item O(N) O(1) 

算法：Big-Oh表示法

ArrayLists适合一次写入多次读取或appender，但在前面或中间添加/删除时效果不佳。

Answer 6

是的，我知道，这是一个古老的问题，但我会投入两分钱：

在性能方面，LinkedList 几乎总是错误的选择。 有一些非常具体的算法需要一个LinkedList，但那些非常非常罕见，并且算法通常特别依赖于LinkedList能够相对快速地插入和删除列表中间的元素，一旦你在那里导航使用ListIterator。

有一个常见的用例，其中LinkedList优于ArrayList：队列的那个。 但是，如果您的目标是性能，而不是LinkedList，您还应该考虑使用ArrayBlockingQueue（如果您可以提前确定队列大小的上限，并且可以预先分配所有内存），或者此CircularArrayList实现 。 （是的，它是从2001年开始的，所以你需要对它进行一般化，但我的性能比率与刚刚在最近的JVM中引用的内容相当）

Answer 7

这是一个效率问题。 LinkedList可以快速添加和删除元素，但访问特定元素的速度很慢。 ArrayList可以快速访问特定元素，但添加到任何一端都很慢，特别是在中间删除速度很慢。

Array和ArrayList vs LinkedList vs Vector的内容更加深入， Linked List也是如此 。

Answer 8

正确或不正确：请在本地执行测试并自行决定！

LinkedList编辑/删除比ArrayList更快。

由Array支持的ArrayList ，需要大小的两倍，在大容量应用程序中更糟糕。

下面是每个操作的单位测试结果。时间以纳秒为单位。

---

 Operation ArrayList LinkedList AddAll (Insert) 101,16719 2623,29291 Add (Insert-Sequentially) 152,46840 966,62216 Add (insert-randomly) 36527 29193 remove (Delete) 20,56,9095 20,45,4904 contains (Search) 186,15,704 189,64,981 

---

这是代码：

 import org.junit.Assert; import org.junit.Test; import java.util.*; public class ArrayListVsLinkedList { private static final int MAX = 500000; String[] strings = maxArray(); ////////////// ADD ALL //////////////////////////////////////// @Test public void arrayListAddAll() { Watch watch = new Watch(); List stringList = Arrays.asList(strings); List arrayList = new ArrayList(MAX); watch.start(); arrayList.addAll(stringList); watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds } @Test public void linkedListAddAll() throws Exception { Watch watch = new Watch(); List stringList = Arrays.asList(strings); watch.start(); List linkedList = new LinkedList(); linkedList.addAll(stringList); watch.totalTime("Linked List addAll() = "); //2623,29291 Nanoseconds } //Note: ArrayList is 26 time faster here than LinkedList for addAll() ///////////////// INSERT ///////////////////////////////////////////// @Test public void arrayListAdd() { Watch watch = new Watch(); List arrayList = new ArrayList(MAX); watch.start(); for (String string : strings) arrayList.add(string); watch.totalTime("Array List add() = ");//152,46840 Nanoseconds } @Test public void linkedListAdd() { Watch watch = new Watch(); List linkedList = new LinkedList(); watch.start(); for (String string : strings) linkedList.add(string); watch.totalTime("Linked List add() = "); //966,62216 Nanoseconds } //Note: ArrayList is 9 times faster than LinkedList for add sequentially /////////////////// INSERT IN BETWEEN /////////////////////////////////////// @Test public void arrayListInsertOne() { Watch watch = new Watch(); List stringList = Arrays.asList(strings); List arrayList = new ArrayList(MAX + MAX / 10); arrayList.addAll(stringList); String insertString0 = getString(true, MAX / 2 + 10); String insertString1 = getString(true, MAX / 2 + 20); String insertString2 = getString(true, MAX / 2 + 30); String insertString3 = getString(true, MAX / 2 + 40); watch.start(); arrayList.add(insertString0); arrayList.add(insertString1); arrayList.add(insertString2); arrayList.add(insertString3); watch.totalTime("Array List add() = ");//36527 } @Test public void linkedListInsertOne() { Watch watch = new Watch(); List stringList = Arrays.asList(strings); List linkedList = new LinkedList(); linkedList.addAll(stringList); String insertString0 = getString(true, MAX / 2 + 10); String insertString1 = getString(true, MAX / 2 + 20); String insertString2 = getString(true, MAX / 2 + 30); String insertString3 = getString(true, MAX / 2 + 40); watch.start(); linkedList.add(insertString0); linkedList.add(insertString1); linkedList.add(insertString2); linkedList.add(insertString3); watch.totalTime("Linked List add = ");//29193 } //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly. ////////////////// DELETE ////////////////////////////////////////////////////// @Test public void arrayListRemove() throws Exception { Watch watch = new Watch(); List stringList = Arrays.asList(strings); List arrayList = new ArrayList(MAX); arrayList.addAll(stringList); String searchString0 = getString(true, MAX / 2 + 10); String searchString1 = getString(true, MAX / 2 + 20); watch.start(); arrayList.remove(searchString0); arrayList.remove(searchString1); watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds } @Test public void linkedListRemove() throws Exception { Watch watch = new Watch(); List linkedList = new LinkedList(); linkedList.addAll(Arrays.asList(strings)); String searchString0 = getString(true, MAX / 2 + 10); String searchString1 = getString(true, MAX / 2 + 20); watch.start(); linkedList.remove(searchString0); linkedList.remove(searchString1); watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds } //Note: LinkedList is 10 millisecond faster than ArrayList while removing item. ///////////////////// SEARCH /////////////////////////////////////////// @Test public void arrayListSearch() throws Exception { Watch watch = new Watch(); List stringList = Arrays.asList(strings); List arrayList = new ArrayList(MAX); arrayList.addAll(stringList); String searchString0 = getString(true, MAX / 2 + 10); String searchString1 = getString(true, MAX / 2 + 20); watch.start(); arrayList.contains(searchString0); arrayList.contains(searchString1); watch.totalTime("Array List addAll() time = ");//186,15,704 } @Test public void linkedListSearch() throws Exception { Watch watch = new Watch(); List linkedList = new LinkedList(); linkedList.addAll(Arrays.asList(strings)); String searchString0 = getString(true, MAX / 2 + 10); String searchString1 = getString(true, MAX / 2 + 20); watch.start(); linkedList.contains(searchString0); linkedList.contains(searchString1); watch.totalTime("Linked List addAll() time = ");//189,64,981 } //Note: Linked List is 500 Milliseconds faster than ArrayList class Watch { private long startTime; private long endTime; public void start() { startTime = System.nanoTime(); } private void stop() { endTime = System.nanoTime(); } public void totalTime(String s) { stop(); System.out.println(s + (endTime - startTime)); } } private String[] maxArray() { String[] strings = new String[MAX]; Boolean result = Boolean.TRUE; for (int i = 0; i < MAX; i++) { strings[i] = getString(result, i); result = !result; } return strings; } private String getString(Boolean result, int i) { return String.valueOf(result) + i + String.valueOf(!result); } } 

Answer 9

ArrayList本质上是一个数组。 LinkedList实现为双链表。

get很清楚。 对于ArrayList ，O（1），因为ArrayList允许使用索引进行随机访问。 对于LinkedList ，O（n），因为它需要首先找到索引。 注意：有不同版本的add和remove 。

LinkedList在添加和删除方面更快，但在get中更慢。 简而言之，如果出现以下情况，应首选LinkedList ：

1. 没有大量的随机访问元素
2. 有大量的添加/删除操作

=== ArrayList ===

• 添加（E e）
  • 在ArrayList的末尾添加
  • 需要内存调整成本。
  • O（n）最差，O（1）摊销
• add（int index，E element）
  • 添加到特定的索引位置
  • 需要转移和可能的内存调整成本
  • 上）
• remove（int index）
  • 删除指定的元素
  • 需要转移和可能的内存调整成本
  • 上）
• 删除（对象o）
  • 从此列表中删除指定元素的第一个匹配项
  • 需要首先搜索元素，然后转移和可能的内存resize成本
  • 上）

=== LinkedList ===

• 添加（E e）

  • 添加到列表的末尾
  • O（1）

• add（int index，E element）

  • 插入指定位置
  • 需要先找到位置
  • 上）
• 去掉（）
  • 删除列表的第一个元素
  • O（1）
• remove（int index）
  • 删除具有指定索引的元素
  • 需要先找到元素
  • 上）
• 删除（对象o）
  • 删除指定元素的第一个匹配项
  • 需要先找到元素
  • 上）

这是programcreek.com的图（ add和remove是第一种类型，即在列表末尾添加元素并删除列表中指定位置的元素。）：

Answer 10

ArrayList is randomly accessible, while LinkedList is really cheap to expand and remove elements from. For most cases, ArrayList is fine.

Unless you’ve created large lists and measured a bottleneck, you’ll probably never need to worry about the difference.

Answer 11

1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).

Reason: ArrayList maintains an index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side, LinkedList implements a doubly linked list which requires the traversal through all the elements for searching an element.

2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in the worst case (while removing the first element) and O(1) in the best case (While removing the last element).

Conclusion: LinkedList element deletion is faster compared to ArrayList.

Reason: Each of LinkedList’s elements maintains two pointers (addresses), which point to both neighbor elements in the list. Hence removal only requires a change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.

3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in the worst case. The reason is same as explained for remove.

4) Memory Overhead: ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes hence the memory consumption is high in LinkedList comparatively.

There are few similarities between these classes which are as follows:

Both ArrayList and LinkedList are implementations of List interface. They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List. Both these classes are non-synchronized and can be made synchronized explicitly by using Collections.synchronizedList method. The iterator and listIterator returned by these classes are fail-fast (if the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException).

When to use LinkedList and when to use ArrayList?

1) As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)). Hence if there is a requirement of frequent addition and deletion in an application then LinkedList is the best choice.

2) Search (get method) operations are fast in ArrayList (O(1)) but not in LinkedList (O(n)) so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

Answer 12

Joshua Bloch, the author of LinkedList:

Does anyone actually use LinkedList? I wrote it, and I never use it.

Link: https://twitter.com/joshbloch/status/583813919019573248

I’m sorry for the answer for being not that informative as the other answers, but I thought it would be the most interesting and self-explanatory.

Answer 13

If your code has add(0) and remove(0) , use a LinkedList and it’s prettier addFirst() and removeFirst() methods. Otherwise, use ArrayList .

And of course, Guava ‘s ImmutableList is your best friend.

Answer 14

I know this is an old post, but I honestly can’t believe nobody mentioned that LinkedList implements Deque . Just look at the methods in Deque (and Queue ); if you want a fair comparison, try running LinkedList against ArrayDeque and do a feature-for-feature comparison.

Answer 15

Here is the Big-O notation in both ArrayList and LinkedList and also CopyOnWrite-ArrayList :

ArrayList

 get O(1) add O(1) contains O(n) next O(1) remove O(n) iterator.remove O(n) 

LinkedList

 get O(n) add O(1) contains O(n) next O(1) remove O(1) iterator.remove O(1) 

CopyOnWrite-ArrayList

 get O(1) add O(n) contains O(n) next O(1) remove O(n) iterator.remove O(n) 

Based on these you have to decide what to choose. 🙂

Answer 16

Let’s compare LinkedList and ArrayList wrt below parameters:

1. Implementation

ArrayList is the resizable array implementation of list interface , while

LinkedList is the Doubly-linked list implementation of the list interface.

---

2. Performance

• get(int index) or search operation

  ArrayList get(int index) operation runs in constant time ie O(1) while

  LinkedList get(int index) operation run time is O(n) .

  The reason behind ArrayList being faster than LinkedList is that ArrayList uses an index based system for its elements as it internally uses an array data structure, on the other hand,

  LinkedList does not provide index-based access for its elements as it iterates either from the beginning or end (whichever is closer) to retrieve the node at the specified element index.

• insert() or add(Object) operation

  Insertions in LinkedList are generally fast as compare to ArrayList. In LinkedList adding or insertion is O(1) operation .

  While in ArrayList , if the array is the full ie worst case, there is an extra cost of resizing array and copying elements to the new array, which makes runtime of add operation in ArrayList O(n), otherwise it is O(1).

• remove(int) operation

  Remove operation in LinkedList is generally the same as ArrayList ie O(n).

  In LinkedList , there are two overloaded remove methods. one is remove() without any parameter which removes the head of the list and runs in constant time O(1). The other overloaded remove method in LinkedList is remove(int) or remove(Object) which removes the Object or int passed as a parameter. This method traverses the LinkedList until it found the Object and unlink it from the original list. Hence this method runtime is O(n).

  While in ArrayList remove(int) method involves copying elements from the old array to new updated array, hence its runtime is O(n).

---

3. Reverse Iterator

LinkedList can be iterated in reverse direction using descendingIterator() while

there is no descendingIterator() in ArrayList , so we need to write our own code to iterate over the ArrayList in reverse direction.

---

4. Initial Capacity

If the constructor is not overloaded, then ArrayList creates an empty list of initial capacity 10, while

LinkedList only constructs the empty list without any initial capacity.

---

5. Memory Overhead

Memory overhead in LinkedList is more as compared to ArrayList as a node in LinkedList needs to maintain the addresses of the next and previous node. 而

In ArrayList each index only holds the actual object(data).

---

资源

Answer 17

In addition to the other good arguments above, you should notice ArrayList implements RandomAccess interface, while LinkedList implements Queue .

So, somehow they address slightly different problems, with difference of efficiency and behavior (see their list of methods).

Answer 18

See the Java Tutorials – List Implementations .

Answer 19

An array list is essentially an array with methods to add items etc. (and you should use a generic list instead). It is a collection of items which can be accessed through an indexer (for example [0]). It implies a progression from one item to the next.

A linked list specifies a progression from one item to the next (Item a -> item b). You can get the same effect with an array list, but a linked list absolutely says what item is supposed to follow the previous one.

Answer 20

It depends upon what operations you will be doing more on the List.

ArrayList is faster to access an indexed value. It is much worse when inserting or deleting objects.

To find out more, read any article that talks about the difference between arrays and linked lists.

Answer 21

I have read the responses, but there is one scenario where I always use a LinkedList over an ArrayList that I want to share to hear opinions:

Every time I had a method that returns a list of data obtained from a DB I always use a LinkedList.

My rationale was that because it is impossible to know exactly how many results am I getting, there will be not memory wasted (as in ArrayList with the difference between the capacity and actual number of elements), and there would be no time wasted trying to duplicate the capacity.

As far a ArrayList, I agree that at least you should always use the constructor with the initial capacity, to minimize the duplication of the arrays as much as possible.

Answer 22

An important feature of a linked list (which I didn’t read in another answer) is the concatenation of two lists. With an array this is O(n) (+ overhead of some reallocations) with a linked list this is only O(1) or O(2) 😉

Important : For Java its LinkedList this is not true! See Is there a fast concat method for linked list in Java?

Answer 23

Operation get(i) in ArrayList is faster than LinkedList, because:
ArrayList: Resizable-array implementation of the List interface
LinkedList: Doubly-linked list implementation of the List and Deque interfaces

Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Answer 24

ArrayList and LinkedList both implements List interface and their methods and results are almost identical. However there are few differences between them which make one better over another depending on the requirement.

ArrayList Vs LinkedList

1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n) .

Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.

2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing first element) and O(1) in best case (While removing last element).

Conclusion: LinkedList element deletion is faster compared to ArrayList.

Reason: LinkedList’s each element maintains two pointers (addresses) which points to the both neighbor elements in the list. Hence removal only requires change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.

3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in worst case. Reason is same as explained for remove.

4) Memory Overhead: ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes

hence the memory consumption is high in LinkedList comparatively.

There are few similarities between these classes which are as follows:

• Both ArrayList and LinkedList are implementation of List interface.
• They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List.
• Both these classes are non-synchronized and can be made synchronized explicitly by using Collections.synchronizedList method.
• The iterator and listIterator returned by these classes are fail-fast (if list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException ).

When to use LinkedList and when to use ArrayList?

• As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)) .
  

  Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.

• Search ( get method ) operations are fast in Arraylist (O(1)) but not in LinkedList (O(n))
  

  so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

Answer 25

ArrayList and LinkedList have their own pros and cons.

ArrayList uses contiguous memory address compared to LinkedList which uses pointers toward the next node. So when you want to look up an element in an ArrayList is faster than doing n iterations with LinkedList.

On the other hand, insertion and deletion in a LinkedList are much easier because you just have to change the pointers whereas an ArrayList implies the use of shift operation for any insertion or deletion.

If you have frequent retrieval operations in your app use an ArrayList. If you have frequent insertion and deletion use a LinkedList.

Answer 26

1) Underlying Data Structure

The first difference between ArrayList and LinkedList comes with the fact that ArrayList is backed by Array while LinkedList is backed by LinkedList. This will lead to further differences in performance.

2) LinkedList implements Deque

Another difference between ArrayList and LinkedList is that apart from the List interface, LinkedList also implements Deque interface, which provides first in first out operations for add() and poll() and several other Deque functions. 3) Adding elements in ArrayList Adding element in ArrayList is O(1) operation if it doesn’t trigger re-size of Array, in which case it becomes O(log(n)), On the other hand, appending an element in LinkedList is O(1) operation, as it doesn’t require any navigation.

4) Removing an element from a position

In order to remove an element from a particular index eg by calling remove(index), ArrayList performs a copy operation which makes it close to O(n) while LinkedList needs to traverse to that point which also makes it O(n/2), as it can traverse from either direction based upon proximity.

5) Iterating over ArrayList or LinkedList

Iteration is the O(n) operation for both LinkedList and ArrayList where n is a number of an element.

6) Retrieving element from a position

The get(index) operation is O(1) in ArrayList while its O(n/2) in LinkedList, as it needs to traverse till that entry. Though, in Big O notation O(n/2) is just O(n) because we ignore constants there.

7) Memory

LinkedList uses a wrapper object, Entry, which is a static nested class for storing data and two nodes next and previous while ArrayList just stores data in Array.

So memory requirement seems less in the case of ArrayList than LinkedList except for the case where Array performs the re-size operation when it copies content from one Array to another.

If Array is large enough it may take a lot of memory at that point and trigger Garbage collection, which can slow response time.

From all the above differences between ArrayList vs LinkedList, It looks ArrayList is the better choice than LinkedList in almost all cases, except when you do a frequent add() operation than remove(), or get().

It’s easier to modify a linked list than ArrayList, especially if you are adding or removing elements from start or end because linked list internally keeps references of those positions and they are accessible in O(1) time.

In other words, you don’t need to traverse through the linked list to reach the position where you want to add elements, in that case, addition becomes O(n) operation. For example, inserting or deleting an element in the middle of a linked list.

In my opinion, use ArrayList over LinkedList for most of the practical purpose in Java.

Answer 27

Both remove() and insert() have a runtime efficiency of O(n) for both ArrayLists and LinkedLists. However, the reason behind the linear processing time comes from two very different reasons:

In an ArrayList, you get to the element in O(1), but actually removing or inserting something makes it O(n) because all the following elements need to be changed.

In a LinkedList, it takes O(n) to actually get to the desired element, because we have to start at the very beginning until we reach the desired index. Actually removing or inserting is constant, because we only have to change 1 reference for remove() and 2 references for insert().

Which of the two is faster for inserting and removing depends on where it happens. If we are closer to the beginning the LinkedList will be faster, because we have to go through relatively few elements. If we are closer to the end an ArrayList will be faster, because we get there in constant time and only have to change the few remaining elements that follow it. When done precisely in the middle the LinkedList will be faster because going through n elements is quicker than moving n values.

Bonus: While there is no way of making these two methods O(1) for an ArrayList, there actually is a way to do this in LinkedLists. Let’s say we want to go through the entire List removing and inserting elements on our way. Usually, you would start from the very beginning for each element using the LinkedList, we could also “save” the current element we’re working on with an Iterator. With the help of the Iterator, we get an O(1) efficiency for remove() and insert() when working in a LinkedList. Making it the only performance benefit I’m aware of where a LinkedList is always better than an ArrayList.

Answer 28

ArrayList extends AbstractList and implements the List Interface. ArrayList is dynamic array.
It can be said that it was basically created to overcome the drawbacks of arrays

The LinkedList class extends AbstractSequentialList and implements List,Deque, and Queue interface.
性能
arraylist.get() is O(1) whereas linkedlist.get() is O(n)
arraylist.add() is O(1) and linkedlist.add() is 0(1)
arraylist.contains() is O(n) and linkedlist.contains() is O(n)
arraylist.next() is O(1) and linkedlist.next() is O(1)
arraylist.remove() is O(n) whereas linkedlist.remove() is O(1)
In arraylist
iterator.remove() is O(n)
whereas In linkedlist
iterator.remove() is O(1)

Answer 29

One of the tests I saw on here only conducts the test once. But what I have noticed is that you need to run these tests many times and eventually their times will converge. Basically the JVM needs to warm up. For my particular use case I needed to add/remove items to a last that grows to about 500 items. In my tests LinkedList came out faster, with linked LinkedList coming in around 50,000 NS and ArrayList coming in at around 90,000 NS… give or take. 请参阅下面的代码。

 public static void main(String[] args) { List times = new ArrayList<>(); for (int i = 0; i < 100; i++) { times.add(doIt()); } System.out.println("avg = " + (times.stream().mapToLong(x -> x).average())); } static long doIt() { long start = System.nanoTime(); List 

Answer 30

When should I use LinkedList ? When working with stacks mostly, or when working with buffers. When should I use ArrayList ? Only when working with indexes, otherwise you can use HashTable with linked list, then you get:

Hash table + linked list

• Access by key O(1),
• Insert by key O(1),
• Remove by key O(1)
• and there is a trick to implement RemoveAll / SetAll with O(1) when using versioning

It seems like a good solution, and in most of the cases it is, how ever you should know: HashTable takes a lot of disc space, so when you need to manage 1,000,000 elements list it can become a thing that matters. This can happen in server implementations, in clients it is rarely the case.

Also take a look at Red-Black-Tree

• Random access Log(n),
• Insert Log(n),
• Remove Log(n)