Difference between ArrayList and LinkedList?

[Thomas Markl]

What ist the difference between an ArrayList and a LinkedList?
When do we use a LinkedList? What’s the advantage over an ArrayList?

import java.util.*;
class ListOp1a {
 public static void main(String args[]) {
   LinkedList l = new LinkedList();
   l.add("This");
   l.add("is");
   l.add("a");
   l.add("test");
   l.add("test");
 
   System.out.println(l);
 }
}

import java.util.*;
class ListOp1a {
 public static void main(String args[]) {
   ArrayList l = new ArrayList();
   l.add("This");
   l.add("is");
   l.add("a");
   l.add("test");
   l.add("test");
 
   System.out.println(l);
 }
}

result of both is:
C:\Java\EigeneJavaProgramme>java ListOp1a
[This, is, a, test, test]

[Anonymous]

Both are similar, though slightly different in terms of goal and implementation. In a LinkedList, each element is linked to its previous and next element making it easier to delete or insert in the middle of the list. A ArrayList is more as its name subjects used as an array.
Performance is similar, though LinkedList is optimized when inserting elements before the end of the list, where ArrayList is optimized when adding elements at the end.
Cheers

[Thomas Paul]

Check this article from the javaRanch newsletter:
http://www.javaranch.com/newsletter/June2002/newsletterjune2002.jsp#collections

[jeya lakshmi]

public void add(int index,E element)
Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

add(int index,E element)- this method is used to insert a element wherever we want.Then what is the difference between linkedlist and arraylist

[Jesper de Jong]

jeya lakshmi wrote:Then what is the difference between linkedlist and arraylist

The difference is in the performance characteristics. Because of the way ArrayList and LinkedList work internally, some operations are more efficient on ArrayList, and some operations are more efficient on LinkedList.

For example, inserting an element in the middle of the list is relatively slow on ArrayList, but fast on LinkedList. And looking up a random element in the list is fast on ArrayList, but slow on LinkedList. Which of the two you should choose depends on what you're going to use the list for. This page from Sun's Java Tutorials explains:

If you frequently add elements to the beginning of the List or iterate over the List to delete elements from its interior, you should consider using LinkedList. These operations require constant-time in a LinkedList and linear-time in an ArrayList. But you pay a big price in performance. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList. Furthermore, the constant factor for LinkedList is much worse. If you think you want to use a LinkedList, measure the performance of your application with both LinkedList and ArrayList before making your choice; ArrayList is usually faster.

[Sam Samson]

Thomas Paul wrote:Check this article from the javaRanch newsletter:
http://www.javaranch.com/newsletter/June2002/newsletterjune2002.jsp#collections

In this newsletter is a table. Regarding this table I guess I should use LinkedList instead of ArrayList when I want to iterate over it and insert elements. LinkedList is only slower when getting an element? I can't remember that I've ever used get(index) on an ArrayList.

I've done some research into this topic via Google. Almost everyone is saying that ArrayList should be chosen. LinkedList uses more memory etc. Here they're discussing it on StackOverflow.

I don't understand the issue with "RandomAccess". What is exactly RandomAccess on an ordered List?

In a for-each loop, which method is called behind the scenes for iterating? get(index)? an Iterator?

[Stephan van Hulst]

Yes, ArrayList is generally faster. You should almost always prefer it, unless you are doing a *lot* of inserting and removing at places other than the end of the list.

The RandomAccess interface is just a label that some utility classes may check for when they are performing operations on lists. Random access means that reading a value in the middle of the list is just as fast as reading a value at the start or end of the list. A binary search will perform rather poorly on a list that doesn't have random access. So instead, when the algorithm sees that the list doesn't implement RandomAccess, it might first copy the contents of the list to an array (which has random access) before performing the search.

The enhanced for loop (or for-each loop) will use an Iterator behind the scenes. The iterator itself may use the get() method, but this is only the case for random access collections, such as ArrayList. The iterator provided by LinkedList will just have a reference to the current node in the link.

[Jeff Verdegan]

Sam Samson wrote:I guess I should use LinkedList instead of ArrayList when I want to iterate over it and insert elements.

Not quite sure what you're saying here. If you're just going to add at the end with add() and iterate normally with iterator() or foreach, then the performance will be the same.

If you're going to insert an element anywhere but at the end, LL will be faster the closer the insertion point moves to the beginning of the list. The reason for this is that LL just has to update 4 pointers, whereas AL has to copy all the elements after the insertion point. So O(1) for LL vs. O(n) for AL.

However, if you're using an index to get to the location where you're going to insert (as opposed to doing through ListIterator during an iteration), then LL will have an O(n) cost to find the element at that index.

LinkedList is only slower when getting an element?

Yes, the only significant performance disadvantage of LL is when accessing an element by index. For LL that is O(n), since it has to count from the beginning or end of the list, but for AL it's O(1), since it can use indexed access to get straight to the corresponding element in the backing array.

Outside of CPU cycles, LL will use on average about 20-30 byte per element, whereas AL will use about 4. This will really only be significant if your list is very large (probably millions of elements or more) AND the size of one element is under about 200 bytes or so.

I can't remember that I've ever used get(index) on an ArrayList.

It's definitely a less common use case than simply iterating and processing all elements.

Almost everyone is saying that ArrayList should be chosen.

For the vast majority of use cases, there will be no noticeable difference. The most common use case is simply a bunch of add()s, to build it up, and then using iterate() to access the elements for processing. Both will have the same performance for this case. As far as memory goes, since most lists are probably less than a few thousand or tens of thousands of elements, we're talking worst case a few hundred kB difference in memory for the common case.

I don't understand the issue with "RandomAccess". What is exactly RandomAccess on an ordered List?

Accessing any arbitrary element, in no particular order (usually by index), rather than accessing them in order via iteration.

In a for-each loop, which method is called in behind for iterating? get(index)?

No, it uses the Iterator.

[Jeff Verdegan]

Stephan van Hulst wrote:Yes, ArrayList is generally faster. You should almost always prefer it, unless you are doing a *lot* of inserting and removing at places other than the end of the list.

I disagree. For the common use case--a bunch of add()s to build it, and then iterating using Iterator or foreach--they're both O(1) for the add and O(n) for the iteration.

I do use AL unless I have a specific reason to use LL, but something's gotta be the default, and for most cases it doesn't matter.

[Sam Samson]

Thanks, now it's a little bit more understandable.

Can you explain me that kind of notation to me? O(1) for LL vs. O(n) for AL. What's the meaning of O?

Summarize:
LinkedList should be chosen if I want to make a lot of insertions(not at the end) and deletions. And get(index) isn't heavily used.

True or false?

[Paul Clapham]

Sam Samson wrote:

Thomas Paul wrote:Check this article from the javaRanch newsletter:
http://www.javaranch.com/newsletter/June2002/newsletterjune2002.jsp#collections

In this newsletter is a table. Regarding this table I guess I should use LinkedList instead of ArrayList when I want to iterate over it and insert elements.

Bear in mind that the newsletter is now nearly 10 years old. Advice about Java performance does not age well so you should normally seek the most recent advice.

[Stephan van Hulst]

I disagree. For the common use case--a bunch of add()s to build it, and then iterating using Iterator or foreach--they're both O(1) for the add and O(n) for the iteration.

I meant faster in absolute terms, not in complexity class. On my system, adding 10.000.000 objects to an ArrayList takes 300-500 ms, versus 2000-4000 ms for a LinkedList. If I set the initial capacity for ArrayList to 10.000.000, it takes 50 ms.

It seems it takes LinkedList a lot of time to create the node objects that wrap the elements.

import java.util.*;

final class Test {

  private static final Object[] objects;

  static {
    objects = new Object[10_000_000];
    for (int i = 0; i < objects.length; i++)
      objects[i] = new Object();
  }

  static void test(List<Object> list) {
    long start = System.currentTimeMillis();

    for (Object o: objects)
      list.add(o);

    System.out.println(System.currentTimeMillis() - start);
  }


  public static void main(String... args) {
    test(new ArrayList<Object>());
    test(new LinkedList<Object>());
  }
}

[Jesper de Jong]

Sam Samson wrote:Can you explain me that kind of notation to me? O(1) for LL vs. O(n) for AL. What's the meaning of O?

See Big O notation. It's a way to express how much work algorithms cost.

O(1) means "constant time"; whatever the input, it will take some constant amount of time to perform the algorithm. For example, in an ArrayList, get(index) is O(1), because no matter how many elements there are in the ArrayList, you can lookup any element in a constant amount of time.

O(n) means "linear time"; the amount of time it takes to run the algorithm is proportional to the size of the input (n). For example, in a LinkedList, get(index) is O(n), because the time it takes to find an arbitrary element in a LinkedList is proportional to the number of elements in the list.

Other common algorithms have a complexity of for example O(n log n), or O(n²).

[Jeff Verdegan]

Stephan van Hulst wrote:

I disagree. For the common use case--a bunch of add()s to build it, and then iterating using Iterator or foreach--they're both O(1) for the add and O(n) for the iteration.

I meant faster in absolute terms, not in complexity class.

I figured as much. My point was that since the big-O curves are the same, that absolute performance wouldn't matter.

On my system, adding 10.000.000 objects to an ArrayList takes 300-500 ms, versus 2000-4000 ms for a LinkedList.

I'm kind of surprised. There was a similar discussion recently, and I thought I created a class to test just that, and got indeterminate results--sometimes LL was faster and sometimes AL. Can't find my test class now.

I still wouldn't choose AL for performance reasons unless I measured and found that LL was causing a bottleneck.

It seems it takes LinkedList a lot of time to create the node objects that wrap the elements.

Yup. I figured the larger array creation and copy would offset that to a greater degree than your numbers suggest.

[Jeff Verdegan]

Stephan van Hulst wrote:

I disagree. For the common use case--a bunch of add()s to build it, and then iterating using Iterator or foreach--they're both O(1) for the add and O(n) for the iteration.

I meant faster in absolute terms, not in complexity class. On my system, adding 10.000.000 objects to an ArrayList takes 300-500 ms, versus 2000-4000 ms for a LinkedList. If I set the initial capacity for ArrayList to 10.000.000, it takes 50 ms.

I changed your test a bit:

1. I always add the same object. Adding the iteration over the array of objects means we're timing more than just the list.add() method.

2. I run the pair of alternating tests 3 times, so any JVM startup issues should wash away.

3. I System.gc() after each individual test, and sleep to give the GC time and the JVM cycles to do it, so each test has the best chance of starting with a clean slate memory wise.

4. I launch the JVM with -Xms1G -Xmx1G, so that we (I hope) won't be measuring time obtaining memory from the OS.

The results are interesting. For 10,000,000 elements, while AL is still faster, it's only a factor of about 2x, vs. your factor of 7x-8x. However, when I bump the size up to 20,000,000, I get a factor of about 6x.

I guess that makes sense. The per-element cost for LL is constant, where as the per-element cost for AL could be decreasing, since the allocate/copy happens less and less frequently as the list gets larger.

(I still wouldn't pick AL for speed as a general rule though. )

10M elements
============
class java.util.ArrayList: 78
class java.util.LinkedList: 94

class java.util.ArrayList: 53
class java.util.LinkedList: 102

class java.util.ArrayList: 52
class java.util.LinkedList: 101


20M elements
============
class java.util.ArrayList: 249
class java.util.LinkedList: 947

class java.util.ArrayList: 182
class java.util.LinkedList: 945

class java.util.ArrayList: 184
class java.util.LinkedList: 1899

import java.util.*;

final class AListVsLList {
    static final Object obj = new Object();
    static final int count = 40 * 1000 * 1000;


    static void test(List<Object> list) {
        long start = System.currentTimeMillis();

        for (int i = 0 ; i < count ; i++)
            list.add(obj);

        long elapsed = System.currentTimeMillis() - start;
        System.out.println(list.getClass() + ": " + elapsed);
    }


    public static void main(String... args) throws Exception {
        test(new ArrayList<Object>());
        System.gc();
        Thread.sleep(1000);
        test(new LinkedList<Object>());
        System.gc();
        Thread.sleep(1000);

        System.out.println();

        test(new ArrayList<Object>());
        System.gc();
        Thread.sleep(1000);
        test(new LinkedList<Object>());
        System.gc();
        Thread.sleep(1000);

        System.out.println();

        test(new ArrayList<Object>());
        System.gc();
        Thread.sleep(1000);
        test(new LinkedList<Object>());
        System.gc();
        Thread.sleep(1000);

        System.out.println();
    }
}

[Stephan van Hulst]

I'm curious, could you run the code I posted and report what timings you get? Maybe play around with it, if you want?

I know there are factors involved that my test can't account for, but I still wonder

[edit]

Hah wow you beat me to my own request!

[Jeff Verdegan]

Stephan van Hulst wrote:I'm curious, could you run the code I posted and report what timings you get? Maybe play around with it, if you want?

I know there are factors involved that my test can't account for, but I still wonder

[edit]

Hah wow you beat me to my own request!

Running your code as-is, no changes except that I'm on 1.6 so can't use 10_000_000, and no -Xms or -Xmx args, I got the following, for 3 consecutive runs:

795
1754

855
1716

854
1797

Putting the 3 runs in one JVM execution:

        test(new ArrayList<Object>());
        test(new LinkedList<Object>());
        test(new ArrayList<Object>());
        test(new LinkedList<Object>());
        test(new ArrayList<Object>());
        test(new LinkedList<Object>());

but no additional changes, I got this:

841
1753
52
191
163
636

[Stephan van Hulst]

Thanks, I ran your code and I got about the same results you did, except it seems your system is twice as fast :P

My point is that unless you need random access, or random insertion/removal, there's no good reason to prefer one over the other, other for the fact that ArrayList generally has better coefficients. I think that's a good reason to use it as the default.

I agree it doesn't matter much in the face of bigger performance issues in an application, but what the hey.

[Rob Spoor]

Jeff Verdegan wrote:

    static final int count = 40 * 1000 * 1000;

If you use Java 7 you can prevent that unnecessary calculation and simply write 40_000_000. Of course it's only syntactic sugar; the compiler will already turn 40 * 1000 * 1000 into 40000000.

[Stephan van Hulst]

Jeff Verdegan wrote:[...] I'm on 1.6 so can't use 10_000_000 [...]

[Rob Spoor]

Missed that...

[Martin Vashko]

Stephan van Hulst wrote:My point is that unless you need random access, or random insertion/removal, there's no good reason to prefer one over the other, other for the fact that ArrayList generally has better coefficients. I think that's a good reason to use it as the default.

I agree it doesn't matter much in the face of bigger performance issues in an application, but what the hey.

Do you always know beforehand you'll not need random access to items in an arbitrary list? I use ArrayList by default for that reason alone, LinkedList only when I have documented reason to do so, generally for queues.

Warning: wild speculation: I live under deeply rooted, yet unfounded impression that the more objects are there on the heap, the more work GC has to do. Large LinkedList could therefore put more strain on the GC, as it takes more memory spread among significantly more objects than an ArrayList of the same size. I don't know how to reliably test this assumption, though. Has anybody some ideas on this?

[Stephan van Hulst]

Yes, you'll always know ahead of time that you need random access, namely when you find yourself using the get() method in some iterative or recursive loop. When you use the get() method in response to some GUI event then you hardly need random access, since the user isn't going to notice any difference.

These situations are fairly rare, since you mostly want to iterate over the entire list, as opposed to accessing specific elements. Most of the algorithms that do fancy stuff using specific elements are already pretty standard, such as searching and sorting algorithms. They already account for whether the data type they operate on has random access.

I guess in theory a LinkedList would put more strain on the GC, but it's very hard to make any assumptions about stuff that the JVM does behind the scenes.

[Martin Vashko]

Stephan van Hulst wrote:Yes, you'll always know ahead of time that you need random access, namely when you find yourself using the get() method in some iterative or recursive loop. When you use the get() method in response to some GUI event then you hardly need random access, since the user isn't going to notice any difference.

That much is clear. I had possible future extensions of the software on my mind. I'm probably just used to being able to pass lists to methods and services that may use random access. It is true that indexed access is not that common, and probably some of its occurrences in my code might indicate a flaw in design (I do use the collection-for-loop whenever possible, of course, but time from time an index access still sneaks in).

The LinkedList main advantage of low-cost insert and deletions is probably also negligible unless the list is really huge and modified a lot, and you should also know that ahead of time.

It simply seems to me that LinkedList has a few very subtle disadvantages (total performance, memory requirements, random access, might be less GC friendly) and perhaps one similarly subtle advantage over an ArrayList that actually gets very rarely utilized (I certainly use index access much more than ListIterator or even Iterator in my code, but others may have a different mileage, of course).

[Jeff Verdegan]

Rob Spoor wrote:

Jeff Verdegan wrote:

    static final int count = 40 * 1000 * 1000;

If you use Java 7 you can prevent that unnecessary calculation and simply write 40_000_000. Of course it's only syntactic sugar; the compiler will already turn 40 * 1000 * 1000 into 40000000.

Yup. Not on 7 yet though.
\

[Jeff Verdegan]

Stephan van Hulst wrote:Yes, you'll always know ahead of time that you need random access, namely when you find yourself using the get() method in some iterative or recursive loop.

Except that the creator of the List doesn't always know how it will be used.

I guess in theory a LinkedList would put more strain on the GC, but it's very hard to make any assumptions about stuff that the JVM does behind the scenes.

Yeah, it really depends. If the objects are short-lived enough to be reclaimed while still in eden, then I don't think it's any extra strain. IIRC, it's live objects that need to be copied that put the strain on it.

But yes, LL creates more objects than AL, and as a general rule, GC costs increase with object creation. Actually measuring those costs for the scenarios in question is not something I care to dabble in, however.

[Stephan van Hulst]

Jeff Verdegan wrote:Except that the creator of the List doesn't always know how it will be used.

Ahh, but that's why methods that do require random access can check whether it's provided ;)

It's funny how this old thread still managed to generate all this interesting discussion

[Jeff Verdegan]

Stephan van Hulst wrote:

Jeff Verdegan wrote:Except that the creator of the List doesn't always know how it will be used.

Ahh, but that's why methods that do require random access can check whether it's provided ;)

Not disagreeing with that one bit. Just with the claim that, "Yes, you'll always know ahead of time that you need random access."

It's funny how this old thread still managed to generate all this interesting discussion

Indeed.