何时通过ArrayList使用LinkedList？

我一直只使用一个：

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

我使用接口作为可移植性的types名称，所以当我提出这样的问题时，我可以重写我的代码。

什么时候应该LinkedList使用ArrayList ，反之亦然？

Answer 1

TL; DR ArrayList和ArrayDeque在比LinkedList更多的用例中是可取的。 不确定 – 只需从ArrayList开始。

---

LinkedList和ArrayList是List接口的两个不同的实现。 LinkedList用一个双向LinkedList实现它。 ArrayList使用dynamicresize的数组来实现它。

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

对于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）是最好的情况（例如index = 0）， O（n / 2）是最坏的情况（list的中间值）}

对于ArrayList<E>

• get(int index)是O（1） <— ArrayList<E>主要好处
• add(E element)是O（1）摊销，但O（n）最坏的情况下，因为数组必须resize和复制
• 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） ，尽pipeO（1）对于index = 0 。

另一方面， ArrayList<E>允许快速的随机读访问，所以你可以在任何时候获取元素。 但是，除了最终目标之外，任何地方都可以join或者删除，这要求将所有后面的要素都转移，要么开放，要么填补空白。 另外，如果添加的元素多于底层数组的容量，则会分配一个新的数组（1.5倍大小），并将旧数组复制到新数组中，因此添加到ArrayList中的O（n）最坏的情况，但平均不变。

所以根据你打算做的操作，你应该select相应的实现。 迭代任何一种List实际上同样便宜。 （在ArrayList上迭代在技术上更快，但除非你真的对性能敏感，否则你不应该担心 – 它们都是常量。

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

使用LinkedList另一个好处是当你从列表的头部添加或者删除时产生的，因为那些操作是O（1） ，而ArrayList是O（n） 。 注意ArrayDeque可能是LinkedList一个很好的替代scheme，用于从头部添加和删除，但不是List 。

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

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

Answer 2

到目前为止，没有人似乎已经解决了这些列表中的每一个的内存占用情况，除了普遍认为LinkedList比ArrayList “多得多”之外，所以我做了一些数字处理以示出两个列表占用N个空引用。

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

注意： ArrayList行显示的大小是用于修剪列表的 – 实际上， ArrayList支持数组的容量通常大于其当前元素数。

注2：（ 感谢BeeOnRope）由于CompressedOops现在是从JDK6中期开始的默认值，64位机器的下面的值基本上与32位的对应值相匹配，除非你明确地closures它。

---

---

结果清楚地表明， LinkedList比ArrayList要多得多，特别是在元素数量非常高的情况下。 如果记忆是一个因素，请避开LinkedLists 。

我使用的公式如下，让我知道如果我做了任何错误，我会解决它。 对于32或64位系统，'b'是4或8，'n'是元素的数量。 注意mods的原因是因为java中的所有对象都占用8个字节的倍数，不pipe是否全部使用。

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糟糕：

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

Answer 4

作为一个在大规模的SOA Web服务上进行了十年左右的运营性能工程的人，我更喜欢LinkedList和ArrayList的行为。 虽然LinkedList的稳态吞吐量更糟，因此可能导致购买更多的硬件 – ArrayList在压力下的行为可能会导致集群中的应用程序以接近同步的方式扩展其arrays，而对于大型arrays，可能会导致缺乏响应在应用程序和中断，而在压力下，这是灾难性的行为。

同样的，你可以从默认的吞吐量terminal垃圾收集器中获得更好的吞吐量，但是一旦你获得了10GB的Java应用程序，你可以在整个GC期间locking应用程序25秒，这会在SOA应用程序中导致超时和失败如果发生太频繁，就会冲击你的SLA。 即使CMS收集器需要更多的资源，并且达不到相同的原始吞吐量，但它是一个更好的select，因为它具有更可预测和更小的延迟。

如果您所指的性能是吞吐量，并且您可以忽略延迟，则ArrayList只是性能的更好select。 根据我在工作中的经验，我不能忽视最糟糕的延迟。

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) 

algorithm：大哦表示法

ArrayLists适用于一次写入或多次写入，但在前面或中间添加/删除不好。

Answer 6

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

LinkedList 几乎总是错误的select，性能明智。 有一些非常特殊的algorithm，LinkedList被调用，但这些非常非常罕见，algorithm通常会特别依赖于LinkedList能够相对快速地插入和删除列表中间的元素，一旦你在那里浏览与一个ListIterator。

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

Answer 7

这是一个效率问题。 LinkedList快速添加和删除元素，但访问特定元素的速度很慢。 ArrayList访问特定元素的速度非常快，但是对于任何一端来说，添加速度可能会很慢，特别是在中间删除的速度较慢。

Array vs ArrayList vs LinkedList vs Vector： – 更深入，如同

链接列表

Answer 8

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

在LinkedList中编辑/删除比ArrayList更快。

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

以下是每个操作的unit testing结果。时间以毫微秒为单位。

---

  ArrayList Linked List 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<String> stringList = Arrays.asList(strings); List<String> arrayList = new ArrayList<String>(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<String> stringList = Arrays.asList(strings); watch.start(); List<String> linkedList = new LinkedList<String>(); 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<String> arrayList = new ArrayList<String>(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<String> linkedList = new LinkedList<String>(); 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<String> stringList = Arrays.asList(strings); List<String> arrayList = new ArrayList<String>(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<String> stringList = Arrays.asList(strings); List<String> linkedList = new LinkedList<String>(); 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<String> stringList = Arrays.asList(strings); List<String> arrayList = new ArrayList<String>(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<String> linkedList = new LinkedList<String>(); 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<String> stringList = Arrays.asList(strings); List<String> arrayList = new ArrayList<String>(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<String> linkedList = new LinkedList<String>(); 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很清楚。 O（1）为ArrayList ，因为ArrayList允许使用索引进行随机访问。 O（n）为LinkedList ，因为它需要先find索引。 注意：有不同版本的add和remove 。

LinkedList添加和删​​除速度更快，但获取速度更慢。 简而言之，在下列情况下， LinkedList应该是首选：

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

=== ArrayList ===

• 加（E e）
• • • • 在ArrayList的末尾添加
• • • • 需要调整内存大小的成本。
• • • • O（n）最差，O（1）摊销
• 加（int index，E元素）
• • • • 添加到特定的索引位置
• • • • 需要转移和可能的内存调整成本
• • • • 上）
• 删除（int索引）
• • • • 删除指定的元素
• • • • 需要转移和可能的内存调整成本
• • • • 上）
• 删除（Object o）
• • • • 从列表中删除第一次出现的指定元素
• • • • 首先需要search元素，然后移动＆可能的内存大小调整成本
• • • • 上）

=== LinkedList ===

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

• 加（int index，E元素）

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

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

Answer 10

ArrayList是可以随机访问的，而LinkedList对于扩展和删除元素是非常便宜的。 对于大多数情况下，ArrayList是好的。

除非你创build了大量的列表，并且测量了一个瓶颈，否则你可能永远都不用担心这个差异。

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 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?

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 application then LinkedList is a 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

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 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

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 15

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 16

Have a look at the below image….

wp-content/uploads/2014/12/ArrayListVsLinkedList.png

Image Source : ArrayList Vs LinkedList In Java.

Answer 17

Here is important different of both

  Array List is better for storing and accessing data. Linked List is better for manipulating data. 

Answer 18

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 19

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 index based system for its elements as it internally uses 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 array is full ie worst case, there is 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 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 parameter . This method traverses the LinkedList until it found the Object and unlink it from the original list . Hence this method run time is O(n).

  While in ArrayList remove(int) method involves copying elements from old array to new updated array , hence its run time 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 node in LinkedList needs to maintain the addresses of next and previous node. 而

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

---

资源

Answer 20

See the Java Tutorials – List Implementations .

Answer 21

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 22

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 betwen arrays and linked lists.

Answer 23

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 24

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 25

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 26

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 27

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 28

Let's look at a convo between a ArrayList and LinkedList :

ArrayList : Hi LinkedList come on, i'm a dynamically resizing array .

LinkedList : Hello bro, i'm a doubly linked list internally .

ArrayList : I will be faster in Storing and Searching [Retrieval – O(1)].

LinkedList : Yeah you are , but when it comes to Manipulation of Data [Manipulation – O(1)] I'm faster than you .

ArrayList : I've less memory Overhead, in each index i've only the actual Data but you possess both the actual Data and Address of Next and Previous nodes,Ha ha ;-p

LinkedList : Bro 😉 i can be both a List and Queue because i implement both List and Deque interfaces whereas you implement only the List interface.

ArrayList : Cool i agree we both are good at certain scenarios.

LinkedList : Yup we both are strong in different scenarios.

We conclude by agreeing :

• When more retrieval is done in your Application go ahead with ArrayList

• When more manipulations are done in your Application your best bet is a LinkedList .

Answer 29

When you want to add an item or delete an item from a list, without bothering about item's location, use ArrayList. It will be faster than linked list. Suppose if you want to add to or delete from a peculiar location in a collection, use linked list

Answer 30

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. Lets 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 elements 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 a 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.