By sdellysse


2008-11-27 01:36:35 8 Comments

I've always been one to simply use:

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

I use the interface as the type name for portability, so that when I ask questions such as these I can rework my code.

When should LinkedList be used over ArrayList and vice-versa?

30 comments

@Jonathan Tran 2008-11-27 01:49:42

Summary ArrayList with ArrayDeque are preferable in many more use-cases than LinkedList. If you're not sure — just start with ArrayList.


LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically re-sizing array.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For LinkedList<E>

  • get(int index) is O(n) (with n/4 steps on average)
  • add(E element) is O(1)
  • add(int index, E element) is O(n) (with n/4 steps on average), but O(1) when index = 0 <--- main benefit of LinkedList<E>
  • remove(int index) is O(n) (with n/4 steps on average)
  • Iterator.remove() is O(1). <--- main benefit of LinkedList<E>
  • ListIterator.add(E element) is O(1) This is one of the main benefits of LinkedList<E>

Note: Many of the operations need n/4 steps on average, constant number of steps in the best case (e.g. index = 0), and n/2 steps in worst case (middle of list)

For ArrayList<E>

  • get(int index) is O(1) <--- main benefit of ArrayList<E>
  • add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
  • add(int index, E element) is O(n) (with n/2 steps on average)
  • remove(int index) is O(n) (with n/2 steps on average)
  • Iterator.remove() is O(n) (with n/2 steps on average)
  • ListIterator.add(E element) is O(n) (with n/2 steps on average)

Note: Many of the operations need n/2 steps on average, constant number of steps in the best case (end of list), n steps in the worst case (start of list)

LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Javadoc says "operations that index into the list will traverse the list from the beginning or the end, whichever is closer", so those methods are O(n) (n/4 steps) on average, though O(1) for index = 0.

ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)

The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n) (n/2 steps) for worst case, whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).

Another benefit of using a LinkedList arise when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList. Note that ArrayDeque may be a good alternative to LinkedList for adding and removing from the head, but it is not a List.

Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.

The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 1.8). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.

@David Rodríguez - dribeas 2008-11-27 07:20:28

Forgot to mention insertion costs. In a LinkedList, once you have the correct position, insertion costs O(1), while in an ArrayList it goes up to O(n) - all elements past the insertion point must be moved.

@Ryan Cox 2008-11-27 12:19:18

Regarding the use of Vector: There really is no need to fall back to Vector. The way to do this is with your preferred List implementation and a call to synchronizedList to give it a synchronized wrapper. See: java.sun.com/docs/books/tutorial/collections/implementations‌​/…

@Alex Beardsley 2009-09-08 18:59:22

Also note that as of Java 6 there's no need to worry about losing performance with a thread-safe class. The JVM is smart enough to optimize those locks away from you if you don't need them.

@Kevin Brock 2010-03-23 00:56:13

Linked list add is not always O(1) [or this should say addLast() is O(1)]. This is only true if done from within a ListIterator. The add methods in Java's LinkList implementation must search through the list if additions are not on the head or tail. So worst case this is O(n/2) (which really is O(n); but I wrote it this way as it searches forward or backward depending on the given index so is only over at most half the list).

@Tom Hawtin - tackline 2010-12-12 21:20:23

@Ken Brock That's add(int,E) vs add(E).

@dhblah 2011-03-11 08:52:23

why LinkedList get is O(n), if you know the position it's O(1), isn't it?

@Jonathan Tran 2011-03-11 19:03:11

No, for a LinkedList, get is still O(n) even if you know the position, because in order to get to that position, the underlying implementation has to walk the linked list's "next" pointers to get to that position's value. There is no such thing as random access. For position 2, walking the pointers might be cheap, but for position 1 million, not so cheap. The point is, it's proportional to the position, which means it's O(n).

@schmmd 2011-04-19 22:00:21

With an ArrayList, your memory is close together which can improve performance.

@Kevin 2011-04-30 12:27:42

@schmmd Then explain why memory is called Random-access Memory?

@Jonathan Tran 2011-05-04 18:07:34

@Kevin memory is random-access. But how do you know which spot in memory to read? For an array/ArrayList, you can calculate the address in memory by multiplying the element size times the position in the array, because they're stored contiguously. But for a LinkedList, you can't do that. Each element stores the address of the next.

@Kevin 2011-05-05 06:44:31

@Johnathan Tran Great comment but, my point was that it shouldn't be a difference if 'memory is close together'.

@Jonathan Tran 2011-05-05 20:25:10

@Kevin It may matter that memory is "close together". Hardware will cache contiguous blocks of memory (dynamic RAM) into faster static RAM in the L1 or L2 cache. In theory and most of the time practically, memory can be treated as random-access. But in reality, reading through memory sequentially will be slightly faster than in random order. For a performance-critical loop, this could matter. They call it "spatial locality" or locality of reference.

@jsravn 2011-12-19 21:01:52

This answer glossed over the worst aspect of LinkedList - significantly more allocations than an ArrayList. This can increase the constant time significantly compared to an ArrayList. Also, Vector is not really thread safe - it must still be safely published due to internal non-guarded state (one of the reasons Vector has been deprecated).

@yingted 2012-05-19 14:36:33

In order to get O(1) time for seeking, you have to call listIterator(0) and always use that for sequential (forwards or backwards) seeking.

@Geek 2012-07-17 11:07:31

@JonathanTran you said removal from a linked list takes O(N) and then you say "LinkedList allows for constant-time insertions or removals" . isn't this contradictory ?

@paulw1128 2012-08-09 12:52:27

@Geek remove from position X is O(N) as the list must be traversed to reach the relevant position before doing the actual remove. Iterator.remove is O(1) because it makes use of the constant-time remove without having to traverse the list (i.e. removing the current element).

@Krzysztof Krasoń 2012-11-16 09:38:32

remove in ArrayList is O(1) if you remove from the end, it's O(n) only if you remove in the middle (so you can implement an efficient stack by using add, remove from the end)

@Giovanni Botta 2013-04-01 15:42:02

Worth noting that contains() takes O(n) in both cases.

@supercat 2014-04-03 23:56:51

If one wishes to remove many items from an ArrayList on a single pass of an iterator, is the total time O(N) or O(N^2)? I know I'd implement it to be the former.

@FlyingGuy 2015-01-20 15:17:18

It all really comes down to the size of the L2 cache. ArrayLists are faster then linked list as long as you are withing the size of the L2 cache. As soon as what you are storing exceeds the size of the L2 cache, it really does not mater that much, go with the linked list.

@Matthias 2015-02-04 21:29:08

I think that, similarly to ArrayList<E>#remove(int index) being O(n - index), you could also argue that LinkedList<E>#remove(int index) is in fact O(index + 1). To see why, consider that removing the first element in a LinkedList could only really be O(1). Who (dis)agrees? [Note that this doesn't mean it is wrong to say that LinkedList<E>#remove(int index) is O(n), because the order of magnitude of index is of course n].

@David Soroko 2015-06-24 14:05:41

Non locality of data hurts the LinkedList even in the case of iterating over the elements: david-soroko.blogspot.co.uk/2015/06/…

@rndStr 2015-08-30 16:52:22

Furthering the discussion of the performance of LinkedList.get, the documentation states that "the list will be treversed from the end, when the position is beyond half way", so "get" would be O(n/2).

@xenoterracide 2015-11-01 06:39:27

having read and I think understand this... I would think LinkedList would be preferred default as I personally thing using get is code smell. I rarely want/need it

@Holger 2016-07-04 09:57:35

There’s no such thing as O(n/2) or O(n/4). The big O notation tells you how an operation scales with larger n. and an operation needing n/2 steps scales exactly like an operation needing n steps, which is the reason why constant summands or factors are removed. O(n/2) and O(n/4) are both just O(n). LinkedList and ArrayList have different constant factors anyway, so it wouldn’t make sence to compare a O(n/2) of one with a O(n/4) of the other, both just denote linearly scaling operations.

@AdamSkywalker 2016-07-14 08:51:55

@Andreas, use theta notation if you want to show that average is N/4, big O is not made for that

@James Lawson 2016-11-27 07:23:59

It's acceptable to add constants to Big-O/Big-Theta to emphasise an additional operation / explain a particular case. For example, when we talk about the complexity of reading from a hash table, you'll often see: O(1 + load factor). Yes, that 1 means nothing asymptotically, but it's useful to emphasise that there is a O(1) lookup followed by O(load factor) to follow any chains for collision hashes. Here, we're writing O(n/4) more to explain what "average" case is. Asymptotically, the factor makes no difference, but it's useful for briefly summarising what "average" means for the operation.

@Mani 2016-12-06 07:20:09

guys when i was going through vector's usage and differences i found that though vector synchronizes it is not thread safe. please refer this

@Groostav 2017-09-14 21:08:05

I think its important to mention: if your implementing something that is pure on the Stack (aka Deque) abstraction, requiring that the performance-critical portions of your work use only push and pop, then LinkedList gives you O(1) performance in compact memory without any amortization, which sounds pretty good to me.

@Sedrick 2017-10-19 16:26:25

Could you update this to include removeIf?

@Haakon Løtveit 2018-02-14 11:37:20

While this is an excellent answer, it seems to me that what you really are saying is that you'd use LinkedList lists to build a large collection of varying size and then iterate over all the elements. Meanwhile, ArrayList lists are faster if you need to look up varying positions and not just iterate. (If you need to insert at random places a tree-like or map-like structure may be better so long as its ordered, like TreeMap)

@Holger 2018-04-12 07:28:52

@Groostav LinkedList is all but “compact memory”. If you need a stack or deque, use ArrayDeque which gives you O(1) performance in truly compact memory.

@Ben Kushigian 2018-08-02 22:22:37

This is already covered somewhat above but to make it explicit, addLast is O(1) as well which is not obvious when discussing linked lists.

@linuxNoob 2018-09-28 15:47:01

What is meant by Iterator.remove() is O(1) for linked list? We still need to create the iterator and iterate over the list right? Shouldn't it be O(n) unless the element to be removed is at the end where the current pointer lies?

@Bill K 2018-12-28 18:20:37

@linuxNoob Iterator.remove() can only operate on the linked list as it's being traversed, so it is always O(1). LinkedList.remove() would be O(n) unless it was the first item you were removing.

@linuxNoob 2018-12-29 20:32:03

@BillK When you say operating on the linked list as its being traversed, it still means traversing through the list one element at a time right? Which means if it's not the current element then I'd have to traverse through the list (potentially unknown number of elements) before I can remove it?

@Bill K 2018-12-29 21:56:26

@linuxNoob Yes. If you are doing an operation (let's say searching for a value) you must traverse the list be it linked or array. If it's a linked list then when you find your target, deleting it is O(1), if it's an array list deleting it is O(n). Moreover if you are scanning a list to delete, say, multiple entries with a certain trait then your operation becomes O(n) for a linked list and O(n^2) for an array list. I once "Fixed" an operation (Insertion sort) taking 6 hours down to seconds by JUST replacing an arraylist with a linked list. (then fixed it better with a sorted set)

@Gayan Weerakutti 2019-01-14 12:54:12

I usually use one over the other based on the time complexities of the operations that I'd perform on that particular List.

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

@Bill K 2019-02-21 18:24:59

The ArrayDeque balances things a bit more towards the arrays since insert/remove front/back are all O(1) the only thing Linked List still wins at is adding/removing while traversing (the Iterator operations).

@Numeron 2011-10-06 06:46:45

Thus far, nobody seems to have addressed the memory footprint of each of these lists besides the general consensus that a LinkedList is "lots more" than an ArrayList so I did some number crunching to demonstrate exactly how much both lists take up for N null references.

Since references are either 32 or 64 bits (even when null) on their relative systems, I have included 4 sets of data for 32 and 64 bit LinkedLists and ArrayLists.

Note: The sizes shown for the ArrayList lines are for trimmed lists - In practice, the capacity of the backing array in an ArrayList is generally larger than its current element count.

Note 2: (thanks BeeOnRope) As CompressedOops is default now from mid JDK6 and up, the values below for 64-bit machines will basically match their 32-bit counterparts, unless of course you specifically turn it off.


Graph of LinkedList and ArrayList No. of Elements x Bytes


The result clearly shows that LinkedList is a whole lot more than ArrayList, especially with a very high element count. If memory is a factor, steer clear of LinkedLists.

The formulas I used follow, let me know if I have done anything wrong and I will fix it up. 'b' is either 4 or 8 for 32 or 64 bit systems, and 'n' is the number of elements. Note the reason for the mods is because all objects in java will take up a multiple of 8 bytes space regardless of whether it is all used or not.

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)

@jontejj 2013-04-17 15:31:56

Quite interesting to see that LinkedList requires as much memory as ArrayList for storing a single element. How unintuitive! What happens if you run your example with -XX:+UseCompressedOops?

@Heath Hunnicutt 2013-09-06 00:18:13

The problem with your math is that your graph greatly exaggerates the impact. You are modelling objects which each contain only an int, so 4 or 8 bytes of data. In the linked list, there are essentially 4 "words" of overhead. Your graph thus gives the impression that linked lists use "five times" the storage of array lists. This is wrong. The overhead is 16 or 32 bytes per object, as an additive adjustment, not a scaling factor.

@Numeron 2013-10-17 06:24:16

None of the ArrayList/LinkedList/Node objects contain only an int, so I dont get what you're saying there. I've reworded 'object overhead' to 'object header' to clarfy - there is an 8 byte header for every object regardless of system, and yes that inlcudes all the Node objects in LinkedList, which are all counted correctly as far as I can tell. Incidentally, in looking at it again, I did find a couple of other problems with my math in LinkedList which actually makes the divide it and ArrayList worse. I'm happy to keep updating it so please dont hesitate to clarify and elaborate furuther.

@BeeOnRope 2013-11-07 05:29:09

It should be noted that CompressedOops is default now in all recent JDKs (7, 8 and updates of 6 for a few years), so 64-bit won't make a difference in ArrayList or LinkedList sizes, unless you've explicitly turned off compressed oops for some reason.

@Ogen 2015-09-05 07:03:47

Is that image of the graph available for commercial use? I'd like to use it.

@apraetor 2017-03-30 19:12:55

@jontejj LinkedList x32 uses as much memory as ArrayList x64 for a single element, according to the plot. That's not quite an apples-to-apples comparison.

@jontejj 2017-04-03 13:49:50

@apraetor I don't understand what you mean? I thought LinkedList would be more efficient for smaller lists, like less than 5 elements.

@apraetor 2017-04-04 14:39:45

@jontejj You commented that a single-element LL and AL use the same memory. That's not strictly true, per the graph. The two lines meeting at 1 element are ALx64 and LLx32 -- those are different animals.

@jontejj 2017-04-05 08:06:49

For any non-zero list, ALx32 uses less memory than LLx32, even for single element lists. I find that interesting. Given that it's trimmed lists, it's not surprising to me anymore though. The more realistic scenario would be to not trim the lists.

@Lior Bar-On 2018-10-19 02:53:16

TL;DR due to modern computer architecture, ArrayList will be significantly more efficient for nearly any possible use-case - and therefore LinkedList should be avoided except some very unique and extreme cases.


In theory, LinkedList has an O(1) for the add(E element)

Also adding an element in the mid of a list should be very efficient.

Practice is very different, as LinkedList is a Cache Hostile Data structure. From performance POV - there are very little cases where LinkedList could be better performing than the Cache-friendly ArrayList.

Here are results of a benchmark testing inserting elements in random locations. As you can see - the array list if much more efficient, although in theory each insert in the middle of the list will require "move" the n later elements of the array (lower values are better):

enter image description here

Working on a later generation hardware (bigger, more efficient caches) - the results are even more conclusive:

enter image description here

LinkedList takes much more time to accomplish the same job. source Source Code

There are two main reasons for this:

  1. Mainly - that the nodes of the LinkedList are scattered randomly across the memory. RAM ("Random Access Memory") isn't really random and blocks of memory need to be fetched to cache. This operation takes time, and when such fetches happen frequently - the memory pages in the cache need to be replaced all the time -> Cache misses -> Cache is not efficient. ArrayList elements are stored on continuous memory - which is exactly what the modern CPU architecture is optimizing for.

  2. Secondary LinkedList required to hold back/forward pointers, which means 3 times the memory consumption per value stored compared to ArrayList.

DynamicIntArray, btw, is a custom ArrayList implementation holding Int (primitive type) and not Objects - hence all data is really stored adjacently - hence even more efficient.

A key elements to remember is that the cost of fetching memory block, is more significant than the cost accessing a single memory cell. That's why reader 1MB of sequential memory is up to x400 times faster than reading this amount of data from different blocks of memory:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Source: Latency Numbers Every Programmer Should Know

Just to make the point even clearer, please check the benchmark of adding elements to the beginning of the list. This is a use-case where, in-theory, the LinkedList should really shine, and ArrayList should present poor or even worse-case results:

enter image description here

Note: this is a benchmark of the C++ Std lib, but my previous experience shown the C++ and Java results are very similar. Source Code

Copying a sequential bulk of memory is an operation optimized by the modern CPUs - changing theory and actually making, again, ArrayList/Vector much more efficient


Credits: All benchmarks posted here are created by Kjell Hedström. Even more data can be found on his blog

@Bill K 2018-12-28 18:26:46

I wouldn't call a queue unique or extreme! A fifo queue is much easier implemented on a LinkedList instead of an ArrayList. It's actually a nightmare on an ArrayList as you have to track your own start, stop and do your own reallocating, you might as well use an array, but a Linked List IS a fifo. I'm not sure about Java's implementation, but a LinkedList can do O(1) for both queue and dequeue operations (Requires a special pointer to the tail element for the remove, which I assume java has but I haven't double-checked.)

@Jose Martinez 2018-08-04 18:52:06

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. See the code below.

public static void main(String[] args) {
    List<Long> 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<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}

@pietz 2016-06-11 20:40:29

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.

@Anjali Suman 2018-06-07 10:33:41

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 e.g. 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.

@Bill K 2018-12-28 18:33:04

I think this is the best stated answer of the entire group here. It's accurate and informative. I would suggest changing the last line--at the end add "aside from queues" which are very important structures that really don't make sense for a linked list at all.

@Abhijeet Ashok Muneshwar 2017-02-10 15:14:02

Let's compare LinkedList and ArrayList w.r.t. 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 i.e 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 i.e 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 i.e. 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. While

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


Source

@Ryan 2013-04-21 00:03:47

ArrayList is essentially an array. LinkedList is implemented as a double linked list.

The get is pretty clear. O(1) for ArrayList, because ArrayList allow random access by using index. O(n) for LinkedList, because it needs to find the index first. Note: there are different versions of add and remove.

LinkedList is faster in add and remove, but slower in get. In brief, LinkedList should be preferred if:

  1. there are no large number of random access of element
  2. there are a large number of add/remove operations

=== ArrayList ===

  • add(E e)
    • add at the end of ArrayList
    • require memory resizing cost.
    • O(n) worst, O(1) amortized
  • add(int index, E element)
    • add to a specific index position
    • require shifting & possible memory resizing cost
    • O(n)
  • remove(int index)
    • remove a specified element
    • require shifting & possible memory resizing cost
    • O(n)
  • remove(Object o)
    • remove the first occurrence of the specified element from this list
    • need to search the element first, and then shifting & possible memory resizing cost
    • O(n)

=== LinkedList ===

  • add(E e)

    • add to the end of the list
    • O(1)
  • add(int index, E element)

    • insert at specified position
    • need to find the position first
    • O(n)
  • remove()
    • remove first element of the list
    • O(1)
  • remove(int index)
    • remove element with specified index
    • need to find the element first
    • O(n)
  • remove(Object o)
    • remove the first occurrence of the specified element
    • need to find the element first
    • O(n)

Here is a figure from programcreek.com (add and remove are the first type, i.e., add an element at the end of the list and remove the element at the specified position in the list.):

enter image description here

@Nerrve 2013-11-05 10:00:00

"LinkedList is faster than add/remove". Wrong, check the answer above stackoverflow.com/a/7507740/638670

@Ajax 2013-04-19 07:26:48

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.

@Rajith Delantha 2012-11-06 14:32:08

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. :)

@kachanov 2013-02-08 00:54:05

>>>> ArrayList add --> O(1) <- not tru. In some cases ArrayList will have to grow to add one more element

@garg10may 2016-09-20 12:05:51

LinkedList remove is not O(1), it would need to search for the element to be removed, therefore worst case O(n) and average O(n/2)

@Ash 2011-09-21 22:59:23

Correct or Incorrect: Please execute test locally and decide for yourself!

Edit/Remove is faster in LinkedList than ArrayList.

ArrayList, backed by Array, which needs to be double the size, is worse in large volume application.

Below is the unit test result for each operation.Timing is given in Nanoseconds.


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

Here's the code:

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);
    }
}

@Danubian Sailor 2013-05-06 14:40:49

ArrayList need not to be doubled, to be precise. Please check the sources first.

@Centril 2014-08-21 09:40:10

It should be noted that your example is flawed... You are removing from string of between: 18 + [2, 12] bytes ("true0false", "true500000false"), on average 25 bytes, which are the sizes of the elements in the middle. It's known that as element byte size increases linked list performs better, as list size increases, a contiguous array(list) will do better. Most importantly, you are doing .equals() on strings - which is not a cheap operation. If you instead used integers, I think there would be a difference.

@Centril 2014-08-21 09:46:05

- and that's probably also why there is so little difference for remove/contains.

@Lii 2015-09-15 09:53:40

"... is worse in large volume application": This is a misunderstanding. LinkedList has far more memory overhead because for every element there is a node object with five fields. On many systems that makes 20 bytes overhead. The average memory overhead per element for ArrayList is one and a half word, which makes 6 bytes, and 8 bytes in the worst case.

@BobMcGee 2016-03-10 18:48:54

I've done a better version of your benchmark here, with results - the append-on-end performance for the arraylist is artificially low for yours, because addAll is giving a storage array of EXACTLY initial size, so the first insert always triggers an arraycopy. Also, this includes warmup cycles to allow for JIT compilation before data is collected.

@Xerus 2018-05-27 20:20:14

Edit/Remove is faster in LinkedList than ArrayList. That's a bit too simplified. It depends heavily on where the removal is happening, if it is at the end then ArrayList will be faster, because there is no extra object that has to be GCed at some point.

@Xerus 2018-05-27 20:21:56

ArrayList, backed by Array, which needs to be double the size, is worse in large volume application. The opposite is true. An array has much less overhead than an additional object created for each element in the list, which is what linkedList does.

@Bill K 2018-09-20 16:11:22

LinkedList has a specific (if short) set of uses. Try performance of deleting WHILE you are iterating over a linked list (iterator.remove()). The performance difference should be immense. Also create a list of a few million items using only "addFirst" and see what you get. (ArrayList obviously shouldn't even have an add first because it's such a dumb thing to do on an arraylist.)

@Holger 2019-05-14 17:05:54

@BillK since Java 8, you can use removeIf(element -> condition) where it fits, which can be significantly faster for an ArrayList, compared to looping and removing via iterator, as it is not required to shift the entire remainder for every individual element. Whether this performs better or worse than LinkedList depends on the particular scenario, as a LinkedList is O(1) in theory, but removing just a single node requires several memory accesses, which can easily exceed the number needed for the ArrayList when removing a significant number of elements.

@Jesse Wilson 2008-11-28 02:04:15

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.

@Porculus 2010-09-10 17:20:32

For small lists, ArrayList.add(0) is still always going to be faster than LinkedList.addFirst().

@leventov 2014-08-22 13:19:16

-1. ArrayDeque is better for this case.

@garg10may 2016-09-20 12:07:08

@Porculus I am constantly hearing this argument that for small lists ArrayList.add(0) will be faster, this small is how much small? 10 elements, 10 million, ?

@Jesse Wilson 2016-09-21 14:53:12

@garg10may small is less than 10.

@PhiLho 2008-11-27 01:47:34

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

@Matthew Schinckel 2008-11-27 01:42:03

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.

@kachanov 2012-05-18 02:53:36

To find out more do not read, just write the code. and you will find out that ArrayList implementation is faster then LinkedList in insertion and deletion.

@Dustin 2008-11-27 01:41:47

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.

@Porculus 2010-09-10 17:21:52

LinkedList is not cheap to add elements to. It is almost always quicker to add a million elements to an ArrayList than to add them to a LinkedList. And most lists in real-world code are not even a million elements long.

@Dustin 2010-09-10 23:03:04

At any given point, you know the cost of adding an item to your LinkedList. The ArrayList you do not (in general). Adding a single item to an ArrayList containing a million items could take a very long time -- it's an O(n) operation plus double the storage unless you preallocated space. Adding an item to a LinkedList is O(1). My last statement stands.

@kachanov 2012-05-13 14:36:09

Adding a single item to an ArrayList is O(1) no matter it is 1 million or 1 billion. Adding an item to a LinkedList is also O(1). "Adding" means ADDING TO THE END.

@Dustin 2012-05-14 05:57:35

You must've read the implementation differently than I do. In my experience, copying a 1 billion element array takes longer than copying a 1 million element array.

@kachanov 2012-05-14 14:25:40

when you add element you add it at the end of the array. there is no copying at all. Copying (shifting) happens when you INSERT into the array.

@Stan R. 2013-03-18 21:51:39

@kachanov you must misunderstand Dustin. Unless you have declared an array of 1 billion items you will eventually need to resize your array in which case you will need to copy all elements into a new bigger array hence sometimes you will get O (N) however with a linked list you will always get O (1)

@kachanov 2013-04-11 00:23:48

@Stan R, you must have misunderstood me. If I declare an arry of 1 billion items and adding 99999th item at the end, there is no copying to a bigger array and no resizing.

@Sabir Khan 2018-03-12 11:17:31

@Dustin:For LinkedList class , I see in Oracle JDK-8 that methods with label - Positional Access Operations are implemented - public E get(int index) , public E set(int index, E element) , public void add(int index, E element) & public E remove(int index) so I am confused about your statement that only ArrayList is randomly accessible. even though you haven't specifically said that LinkedList is not randomly accessible but I guess, you meant that.

@dgtized 2008-11-27 01:39:59

It's an efficiency question. LinkedList is fast for adding and deleting elements, but slow to access a specific element. ArrayList is fast for accessing a specific element but can be slow to add to either end, and especially slow to delete in the middle.

Array vs ArrayList vs LinkedList vs Vector goes more in depth, as does Linked List.

@Randhawa 2018-02-20 21:51:19

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.
Performance
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) andlinkedlist.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)

@Nesan Mano 2017-05-15 18:06:30

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.

@Tom Hawtin - tackline 2008-11-27 14:20:16

ArrayList is what you want. LinkedList is almost always a (performance) bug.

Why LinkedList sucks:

  • It uses lots of small memory objects, and therefore impacts performance across the process.
  • Lots of small objects are bad for cache-locality.
  • Any indexed operation requires a traversal, i.e. has O(n) performance. This is not obvious in the source code, leading to algorithms O(n) slower than if ArrayList was used.
  • Getting good performance is tricky.
  • Even when big-O performance is the same as ArrayList, it is probably going to be significantly slower anyway.
  • It's jarring to see LinkedList in source because it is probably the wrong choice.

@David Turner 2008-11-27 17:50:43

Sorry. marked you down. LinkedList doesn't suck. There are situations where LinkedList is the correct class to use. I agree that there aren't many situations where it is better than an arraylist, but they do exist. Educate people who do silly things!

@Kevin Brock 2010-03-23 00:46:34

Sorry to see you got lots of down-votes for this. There is indeed very little reason to use Java's LinkedList. In addition to the bad performance it also uses lots more memory than the other concrete List classes (every node has two additional pointers and each node is a separate wrapper object with the extra overhead bytes that go with them).

@Porculus 2010-09-10 17:25:59

This is one of the most useful answers here. It's a shame so many programmers fail to understand (a) the difference between abstract data types and concrete implementations, and (b) the real-world importance of constant factors and memory overhead in determining performance.

@Malcolm 2011-08-08 13:43:14

-1: This is a rather blinkered view. Yes, it's true that ArrayList is a very versatile tool. However, it has its limitations. There are cases in which this will cause you trouble, and you will have to use LinkedList. Of course, it is a very specialized solution, and, as any specialized tool, in most cases it is outperformed by a versatile one. But that doesn't mean that it "sucks" or something like that, you just have to know when to use it.

@Mehrdad 2013-01-18 05:07:51

@DavidTurner: They do exist, but I think Tom's point was that if you have to ask, you probably want ArrayList.

@Stan R. 2013-03-18 21:43:18

I would like to point out that most BSTree implementations are a form of a linked list. The point is that while LinkedList class might be very specialized the idea behind the class (the data structure itself) is important to understand.

@bestsss 2013-04-18 23:04:49

@DavidTurner, it does suck. There is almost no single case where ArrayList or ArrayDeque would be worse performance wise. LinkedList is a memory hog and Large LinkedList can kill GC performance. Linked structures are good for concurrency and stuff like LinkedHashMap or LinkedTree but not for lists. Tom, you should probably include the fact the garbage collector has to traverse the list which a lot more expensive than an array backed structure. Side note: That should be the top answer.

@Timothy Shields 2013-04-19 15:47:59

Try writing a high-capacity LRU cache without a doubly-linked list... good luck :)

@Tom Hawtin - tackline 2013-04-19 15:49:04

@TimothyShields Probably wouldn't use LinkedList.

@Timothy Shields 2013-04-19 16:09:35

@TomHawtin-tackline If you want amortized O(1) get and put operations you would. The point is that it's a data structure that has advantages and disadvantages compared to array lists. For the vast majority of tasks, array list is better. But there are instances where a linked list is absolutely the correct choice.

@bestsss 2013-04-19 16:11:20

@TimothyShields, LinkedHashMap/LinkedTree (additional links between nodes besides left/right/parent) are linked structures but not LinkedList. The questions is clearly about j.u.LinkedList vs j.u.ArrayList and LinkedList would almost always a mistake. You'd be very hard pressed to try and find an example where LinkedList actually wins.

@Timothy Shields 2013-04-19 16:13:16

@bestsss I'm very aware that this is about vanilla linked list vs. array list. I was referring to the standard doubly-linked list.

@mauhiz 2013-06-06 03:04:35

for big lists you avoid LinkedLists because of memory bloat, for small lists you use ArrayLists because the resizes are not expensive

@darpet 2013-11-27 12:04:40

There are situations where you would use doubly linked list. Example building text editor. You will not use ArrayList there would you ?

@Tom Hawtin - tackline 2013-11-28 04:38:15

@darpet I don't follow. You're not suggesting a LinkedList<Character> are you?

@kevinarpe 2014-02-04 16:42:10

When I first read this answer, I jerked back in my seat. Then I remembered reading so many of your other answers and your blog. I thought to myself: Maybe this guy has a point. Then I spent a day thinking about it. Maybe we discount how much our VMs, operating systems, and CPUs are optimized for array access (and correspondingly not for linked lists). This alone may be enough to sway my view. Deeper question: Does the same apply for non-VM languages, a la C or C++? The sheer number of comments on this reply tells me there are deeper issues here. Maybe Big-O is different for VM langs?

@TheXenocide 2014-08-20 16:22:33

It seems a lot of people in the managed memory world don't even understand what you mean by cache locality, but this is the correct answer in terms of performance. In terms of readability of implementations for specific algorithms, perhaps a linked list will make more sense for some scenarios, but sequential memory is so optimal--from HDD all the way down to L1 Cache on the CPU--that modern systems do not benefit from the insert/remove times enough to compensate for their aggressive use of pointers. Iterating an array is worlds faster than constantly dereferencing "next" pointers.

@TheXenocide 2014-08-20 16:24:10

I'd say that if you almost never read from the set, a Linked List might benefit you, except even writing to it requires reading from it, so that doesn't hold up.

@bestsss 2014-12-13 05:21:23

@DavidTurner, I can't even think of a single case where LinkedList would be better. It has terrible impact on the GC if you discount the memory footprint, lack of cache locality and extra object creation. GCs have to actually iterate through that LinkedList. Even if you try to implement queue or something alike, you'd be better off with a circular list (ArrayDequeue) not a LinkedList. The vanilla LinkedList is just a bad choice.

@David Soroko 2015-06-25 10:16:23

LinkedList can be better by orders of magnitude, when there are "many" insert/delete operations that "tend" to occur at the "start" of the list. Benchmark to quantify the quoted words, JMH ( openjdk.java.net/projects/code-tools/jmh ) is your friend .

@Stuart Marks 2015-11-28 22:52:21

@DavidSoroko Likely true for LinkedList vs ArrayList. For workloads with large numbers of operations at the front, ArrayDeque is probably preferable. And yes, JMH is your friend.

@djechlin 2015-12-18 00:32:28

It's jarring to see anything anywhere that's the wrong choice. If it's jarring to see something that's the right choice then you really should be jarred.

@Lassi Kinnunen 2016-05-03 22:38:05

if you need to use a linkedlist then it's almost 100% that you should use something else than LinkedList as it comes with java. because it's slow, uses memory and tries to be safe(while also it isn't). arraylist is surprisingly fast for insertions/deletes too. if you want to save the memory, make your object implement the linked list within itself, possibly one way. and never "walk" the java linkedlist with .get(n). it's puzzling why it is even made to use the list interface

@codemania23 2017-10-27 13:14:15

One point which i didn't see anyone mentioning is about how ArrayList needs continuous memory allocation. Think of a hard drive. Do you think ArrayList would work over there? No right, you need a linked list to make use of all the corners of the memory. And to improve performance, there are defragmenters.

@Shailesh Pratapwar 2018-04-06 05:18:47

Downvoted. Only the point no. 3 seems to be valid "Any indexed operation requires a traversal"

@Bill K 2018-09-20 16:16:05

If someone relies on this answer to implement a FIFO then you are going to be their definition of "Bad Programmer" for the rest of their life. My definition of "Bad Programmer" came years ago from someone trying to do an insertion sort into an array list--it indicates that you have no business programming if you follow this advice blindly. Java does an amazing job of managing small objects (They perform similar to C's stack these days) and tuning to how you think a specific VM implementation might work is really dangerous (premature optimization at best)

@Tom Hawtin - tackline 2018-09-20 22:16:14

@BillK You would generally just use java.util.ArrayDeque for a queue, wouldn't you? (Unless concurrent or some other unusual purpose.) Would you write an insertion sort directly on a List? Even so, a carefully implemented implementation ought to do alright on an ArrayList vs LinkedList (Collections.rotate requires creating a subList, unfortunately). Absolutely agree with avoiding VM implementation-specific thinking. Not sure what you are getting at with respect to small objects.

@Bill K 2018-09-21 16:22:44

Sure you would USE an existing Queue based class, but if you were IMPLEMENTING a queue (Say for an assignment), you would almost certainly want to do it with a LinkedList (Implementing a circular queue on an array is much more work and using an ArrayList would be criminally bad code). My point was just that to blindly say always use ArrayList will occasionally (rarely) lead to horrible code. Don't delete from/add to the beginning or middle of an ArrayList. Period.

@Tom Hawtin - tackline 2018-09-22 14:59:16

@BillK If you're doing it for an assignment then it doesn't matter. Deleting/inserting from the start of an ArrayList isn't ideal but i's firstly unlikely and secondly not that bad. You're just shifting some bits up and down - not chasing references all over the shop, as you doing almost anything anything with a LinkedList.

@Holger 2019-05-14 16:33:52

@BillK Your reasoning is strange. If you need a queue for real, you’re using ArrayDeque, not LinkedList. If you get an assignment to implement a queue on your own, you’re using neither, as both, ArrayDeque and LinkedList, are already implementations of the Queue interface. Whereas implementing a linked list on your own has nothing to do with the decision to use the existing LinkedList implementation. A linked list in general doesn’t have to have the issues of this particular implementation class. The biggest problem is that it is not suitable for Java’s List interface.

@Kröw 2019-06-02 01:38:37

What's jarring is seeing so many people against employing a structure that's good for specific scenarios, (which is why it's included in the standard lib). I'm glad this answer got such a minimal amount of upvotes (relative to the top answer of course), but am surprised that it still got over 200.

@Ruslan 2017-03-01 10:47:43

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.

@Nikita Bosik 2018-01-15 15:54:30

I came to this thread solely to check if Joshua's tweet is mentioned. It is :)

@Amitābha 2013-04-25 07:57:38

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.

@Ilya Gazman 2012-06-11 09:08:06

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)

@Numeron 2013-07-29 06:40:10

I wish I could give this more than one -1: LinkedList gives O(N) on all of insert, remove and random access because you have to traverse the list to get to the correct point first. Also it might surprise you to learn that hashmap/table use resizing arrays just like ArrayList and given that the most common usage of lists is to just be indexed by a number, using one of those over an ArrayList is the worst idea.

@Ilya Gazman 2013-10-03 06:58:03

@Numeron you are right, it wasn't clear what I answered. Indeed when you try accessing linked list by index, it will be O(n), how ever I meant inserting to linked list by items. Then it's O(1) and also interacting over all the list it's same as array list.

@Real73 2016-11-02 09:00:23

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.

@Michael Munsey 2010-04-08 20:33:35

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)

Algorithms: Big-Oh Notation

ArrayLists are good for write-once-read-many or appenders, but bad at add/remove from the front or middle.

@Porculus 2010-09-10 17:23:15

You can't compare big-O values directly without thinking about constant factors. For small lists (and most lists are small), ArrayList's O(N) is faster than LinkedList's O(1).

@Maarten Bodewes 2011-08-18 16:35:34

I don't care about small lists performance, and neither does my computer unless it is used in a loop somehow.

@Thomas Ahle 2011-12-30 15:02:56

LinkedList can't really insert in the middle in O(1). It has to run through half the list to find the insertion point.

@kachanov 2012-05-13 14:29:12

LinkedList: insert in middle O(1) - is WRONG! I found out that even insertion into 1/10th position of the LinkedList size is slower than inserting an element into 1/10th position of an ArrayList. And even worse: the end of collection. inserting into last positions (not the very last) of ArrayList is faster then into last positions (not the very last) of LinkedList

@Michael Munsey 2012-05-21 22:43:42

@Anony-Mousse 2013-08-18 08:13:07

@kachanov Inserting in a LinkedList is O(1) if you have an iterator to the insert position, i.e. ListIterator.add is supposedly O(1) for a LinkedList.

@kachanov 2013-09-16 08:21:36

@Anony-Mousse: right. "If you have an iterator to the insert position". But if you don't have it, inseting in a LinkedList is NOT O(1). As you can see the original post, it says: "insert in middle" it does not say "insert in middle where you have a position found by iterator"

@Anony-Mousse 2013-09-16 09:40:23

Bad wording by the author. I'll edit his answer to clarify. Yes, seeking to the arithemetic average of the lists length will take O(N).

@Michael Munsey 2013-09-30 21:21:20

I might would word it as "Insert after a node." You can insert after a given node whether you have an iterator or not. I still think insert in the middle means the same thing, and is clearer.

@Andrei Rînea 2015-01-29 13:08:49

Nice answer. A small thing though : For ArrayList inserting at back is not always O(1). Maybe most of the times. But when it needs to reallocate the internal array a full copy will occur and a cost of O(n) will be incurred.

@Michael Munsey 2015-02-04 00:00:33

True. This is still considered amortized O(1), ie anh.cs.luc.edu/363/notes/06A_Amortizing.html

@Holger 2019-05-14 16:52:49

@Anony-Mousse mind that manipulating a List via an iterator will invalidate all other potentially existing iterators of that list, so it is impossible to keep multiple iterators to interesting spots in a large list; you can keep at most one iterator for manipulations which has to be moved to the next location sequentially. This makes the scenario where you have an iterator pointing to the desired position, to make a manipulation in O(1) an entirely theoretical one. That’s not a deficiency of linked lists in general, it’s just that Java’s Collection API is not really designed for them.

@Anony-Mousse 2019-05-14 18:48:28

@Holger it's easy to imagine workload that involves searching for an insert position first, then inserting at that position. In this case you do have such an iterator, and can avoid searching again.

@Holger 2019-05-15 10:37:17

@Anony-Mousse sure, if your task only involves inserting at the same position over and over again, you have the promised O(1) time complexity when keeping the iterator. It’s just a very unlikely scenario, to have a large list (where the time complexity matters), but only care for a bunch of elements inserted at a particular position. As soon is you start using the list for other purposes, you’ll likely lose anything you gained from that.

@Karussell 2010-03-22 22:32:31

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?

@Kevin Brock 2010-03-23 00:42:31

How is that? This may be true with linked list data structures but not a Java LinkList object. You can't just point a next from one list to the first node in the second list. The only way is to use addAll() which adds elements sequentially, though it is better than looping through and calling add() for each element. To do this quickly in O(1) you would need a compositing class (like org.apache.commons.collections.collection.CompositeCollectio‌​n) but then this would work for any kind of List/Collection.

@Karussell 2010-03-23 12:47:46

yes, true. I edited the answer accordingly. but see this answer for 'how' to do it with LinkedList: stackoverflow.com/questions/2494031/…

@gaijinco 2011-10-03 23:23:00

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.

@chharvey 2011-09-05 06:33:52

@user8898216 2017-11-14 06:08:22

Hi @chharvey , Link only answers get 6 Upvotes ? Please add some points that could support the link .What if oracle changes their link?

@lamont 2011-01-01 20:23:52

As someone who has been doing operational performance engineering on very large scale SOA web services for about a decade, I would prefer the behavior of LinkedList over ArrayList. While the steady-state throughput of LinkedList is worse and therefore might lead to buying more hardware -- the behavior of ArrayList under pressure could lead to apps in a cluster expanding their arrays in near synchronicity and for large array sizes could lead to lack of responsiveness in the app and an outage, while under pressure, which is catastrophic behavior.

Similarly, you can get better throughput in an app from the default throughput tenured garbage collector, but once you get java apps with 10GB heaps you can wind up locking up the app for 25 seconds during a Full GCs which causes timeouts and failures in SOA apps and blows your SLAs if it occurs too often. Even though the CMS collector takes more resources and does not achieve the same raw throughput, it is a much better choice because it has more predictable and smaller latency.

ArrayList is only a better choice for performance if all you mean by performance is throughput and you can ignore latency. In my experience at my job I cannot ignore worst-case latency.

@ingyhere 2012-10-30 05:33:47

Wouldn't another solution be managing the size of the list programmatically by using the ArrayList's ensureCapacity() method? My question is why are so many things being stored in a bunch of brittle data structures when they might better be stored in a caching or db mechanism? I had an interview the other day where they swore up and down about the evils of ArrayList, but I come here and I find that the complexity analysis is all-around better! GREAT POINT FOR DISCUSSION, THOUGH. THANKS!

@bestsss 2014-12-17 20:15:47

once you get java apps with 10GB heaps you can wind up locking up the app for 25 seconds during a Full GCs which causes timeouts Actually with LinkedList you murder the garbage collector during full GCs, it has to iterate the overly large LinkedList with cache miss on each node.

@Andreas 2015-06-16 22:06:01

@bestsss What he is saying that you will never trigger a full GC cycle with link lists; the list will grow and shrink in increments of one element and the CMS GC will run continually; no hiccups.

@Philip Devine 2015-06-19 14:03:14

That's... a horrible solution. you're basically reliant on the GC cleaning up for you, which is incredibly expensive, when you can just call ensureCapacity() on an arraylist instead...

@Holger 2016-07-04 10:20:48

@Andreas: when a list grows and shrinks in increments of one element, there is no problem with ArrayList at all, as it doesn’t even need additional memory for that. Considering the possibility that the ArrayList has to increase its capacity once during the entire life time of a web service as a reason to downgrade performance with a LinkedList, is quite strange, especially, if you consider the cost of the web service’s I/O in comparison. Expanding the capacity of an ArrayList, even with millions of elements, is rather unlikely to be noticed as latency.

@Andreas 2016-07-05 03:46:47

@Holger An array list that increments over its capacity allocates a new list with 50% more room. For that increment you need 2.5 times the memory (and you likely need full gc cycle afterwards). I'm not concerned about day to day response time, I'm worried about running out of heap memory when a peak hour hits slightly harder than it hit yesterday and a couple big arraylists deciding they need room for 2.5 times their count for a second or two. One instance of that type of behavior during peak usage blows my sla for the whole month.

@Holger 2016-07-05 09:04:52

@Andreas: A LinkedList always allocates five times the memory than a plain array of references, so an ArrayList temporarily requiring 2.5 times still consumes far less memory, even while the memory is not reclaimed. Since large array allocation bypasses the Eden space, they don’t have any impact on GC behavior, unless there is really not enough memory, in which case, the LinkedList blew up much earlier…

@Andreas 2016-07-05 19:00:52

@Holger The issue isn't the total usage, it is when it is allocated. Adding an item to a LinkedList allocates a handful of new references, every time. I can watch this trend in resource allocation and plan maintenance outage if needed. Adding an item to a ArrayList generally allocates no new references and occasionally allocates millions. I can't predict this behavior by looking at a dashboard nor can I schedule when the jvm is going to need new resources.

@Piotr Kusmierczyk 2016-11-01 23:12:45

@Andreas The other issue is how the memory is allocated. LinkedList needs only a small piece of free memory to allocate for next element. ArrayList will need a large and continous free block of space to allocate the resized array. If the heap gets fragmented, then GC might end up reordering the entire heap just to free up a suitable single block of memory.

@Aleksandr Dubinsky 2018-10-23 13:27:18

Surely there's a list implementation out there similar to ArrayList but which uses several smaller arrays instead of one huge one. It's a bit drastic to just go with LinkedList.

@kemiller2002 2010-04-20 15:32:01

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.

Related Questions

Sponsored Content

60 Answered Questions

[SOLVED] How do I read / convert an InputStream into a String in Java?

80 Answered Questions

[SOLVED] Is Java "pass-by-reference" or "pass-by-value"?

39 Answered Questions

[SOLVED] How do I efficiently iterate over each entry in a Java Map?

32 Answered Questions

[SOLVED] Create ArrayList from array

30 Answered Questions

[SOLVED] Initialization of an ArrayList in one line

64 Answered Questions

[SOLVED] How do I generate random integers within a specific range in Java?

  • 2008-12-12 18:20:57
  • user42155
  • 3806839 View
  • 3238 Score
  • 64 Answer
  • Tags:   java random integer

44 Answered Questions

[SOLVED] How do I convert a String to an int in Java?

18 Answered Questions

[SOLVED] Why is char[] preferred over String for passwords?

54 Answered Questions

[SOLVED] Creating a memory leak with Java

16 Answered Questions

[SOLVED] Converting 'ArrayList<String> to 'String[]' in Java

Sponsored Content