Jan 19

On JavaKoans I was asked whether for a dynamic set of numbers one could use ArrayList. This brings up a good question: The Java Collections Framework offers a lot of implementions to its many interfaces. Sometimes its unclear when to use what.

I will try to supply an answer for the LinkedList / ArrayList issue. The first thing to do is to look at what interfaces these two implement. This might hint us at their purpose, as Sun usually bound purposes into interfaces.


// lang java
public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Queue<E>, Cloneable, Serializable

We can ignore Cloneable and Serializable as all of the JCF implement those. It’s also quite obvious that both of them implement the List interface, as they need to provide list functionability (backwards iteration, sub listing, etc).

Now for the differences: ArrayList is implementing RandomAccess while LinkedList implementing Queue. You could already tell something about the usage of the two classes.

ArrayList

Now for some implementation notes. The ArrayList is actually encapsulating an actualy Array, an Object[]. When you instanciate ArrayList, an array is created, and when you add values into it, the array changes its size accordingly. This gives you strengths and weaknesses:

  • Fast Random Access
  • You can perform random access without fearing for performence. Calling get(int) will just access the underlying array.

  • Adding values might be slow When you don’t know the amount of values the array will contain when you create it, a lot of shifting is going to be done in the memory space when the ArrayList manipulates its internal array.
  • Slow manipulation When you’ll want to add a value randomly inside the array, between two already existing values, the array will have to start moving all the values one spot to the right in order to let that happen.

LinkedList

The LinkedList is implemented using nodes linked to each other. Each node contains a previous node link, next node link, and value, which contains the actual data. When new data is inserted, a node is inserted and the links of the surrounding nodes are updated accordingly. When one is removed, the same happens – The surrounding nodes are changing their links and the deleted node is garbage collected. This, as well, gives strengths and weaknesses:

  • Fast manipulation As you’d expect, adding and removing new data anywhere in the list is instantanious. Change two links, and you have a new value anywhere you want it.
  • No random access Even though the get(int) is still there, it now just iterates the list until it reaches the index you specified. It has some optimizations in order to do that, but that’s basically it.

Some Conclusions

ArrayList is very useful when a well defined set of data is needed in a List interface as opposed to an array. It can be dynamically changed, but try not to do so frequently throughout the life of the application. LinkedList is there for you to do just that: Manipulating it is very easy, and as long as its used for iteration purposes only and not for random accessing, it’s the best solution. Further, if you need random accessing from time to time, I suggest toArray for that specific moment.

Another point I didn’t raise here is the Queue issue. LinkedList implements extended abilities to the normal List interface which allows it to add and remove elements from its beginning and end. This makes the LinkedList perfect for Queue and Stack purposes – Although in Java 5 they already added a Stack class.

Hope this helped someone. Tell me if you want to differ.

Related Posts with Thumbnails
Share

28 Responses to “LinkedList vs. ArrayList”

  1. Relvox Says:

    Just a though,
    If you need “Random access from time to time” the toArray() Method will probably just cause more overhead since if you’re iterating through the LinkedList there’s no real reason to do that twice. I’d say toArray() comes in handy when you have a lot of random accessing to do at one specific point of time.

    What do you think?

  2. Avah Says:

    That’s what I meant.

    When you have a random access need, convert the linked list to an array and use it as an array for the scope of that method. Otherwise, you should use it as a linked list and use its iteration capabilities.

  3. Stephen Colebourne Says:

    See also commons collections TreeList which has some performance figures
    http://jakarta.apache.org/commons/collections/apidocs-COLLECTIONS_3_1/org/apache/commons/collections/list/TreeList.html

    As a general rule, 99% of the time you should use ArrayList. (Linked list is badly affected by object allocation and garbage collection.)

    You should only worry about the type of the list if it is long lived, large and performance is important.

  4. Avah Says:

    Stephen,

    What you’re saying is very new to me, I must admit, and I’m always willing to learn more.

    The figure in the TreeList link screams “odd”. Why would inserting to anywhere on a LinkedList be slower than inserting anywhere on an ArrayList? Doesn’t the array-based implementation of ArrayList deems it slower by definition?

    Thanks for commenting!

  5. Sandy McArthur Says:

    I did some performance comparisons between ArrayList and LinkedList with 1.4 and 1.5 JVMs. For the almost worst case for ArrayList (using it as a queue, worst being a stack adding to/from the head) it’s still faster than LinkedList for sizes under 15 (1.4 JVM) to 25 (1.5 JVM). After that the overhead of copying values around in the ArrayList ends up being slower than the LinkedList book keeping.

  6. Sandy McArthur Says:

    @Avah: The cost of System.arrayCopy() to shift values around in an array are less than the cost of traversing the chain of nodes backing a LinkedList. At least for smaller arrays.

    Also, your toArray suggestion probably only holds true if you’re going to be doing A LOT of random access. Even then I probably wouldn’t do it. That said I haven’t benchmarked that so I don’t really know.

  7. Avah Says:

    Sandy,

    Your benchmarking sounds reasonable: I can’t imagine copying hundrends of values around being faster than adding a few links to a linked list. However, traversal is expensive, now the question is by how much!

    Do you have the benchmark somewhere online?

  8. Avrom Says:

    This site has some benchmarks and comparisons between various collection classes.

    http://www.precisejava.com/javaperf/j2se/Collections.htm

  9. Avah Says:

    Thank you Avrom!

    Even though this is a bit past news (They speak about JVM 1.2 and 1.3 there), it makes sense. So, as a conclusion, LinkedList should be used whenever a Stack or Queue are needed, and ArrayList whenever a collection of items is needed – But an initialisation of the ArrayList’s size is extremely recomended.

    Did I get that right?

  10. Stephen Colebourne Says:

    Linked lists have these flaws:

    - object allocation – one object per item added
    - garbage collection – the result of object allocation
    - slow random access, by design
    - slow add/remove – because you have to find the entry to remove

    There are thus very, very few cases when you should use LinkedList. Basically most advice that says use a LinkedList class for something is wrong.

    Remember the JDK Stack class is built on an array.

    Most of the time you don’t add/remove from inside an list anyway. Mostly you append to the end and query randomly. These characteristics graetly favour ArrayList.

    LinkedList can be useful if you have a deque – you write to the list both at the beginning and at the end and not in the middle. But even then, the list needs to be long-lived for the benefit to be seen.

    And yes, if you can pre-size the array list then you should.

  11. Avah Says:

    Stephen and Avrom,

    I must say, I didn’t like the testing method they took in the link Avrom gave me so I produced a little test of my own, this time on JVM 1.5. I used 50,000 items as well, and only made the insertion test (for now). Take a look at my numbers (in milliseconds):

    addFirst() to array list took 1468
    addFirst() to linked list using general* methods took 16
    addFirst() to linked list using linked list** methods took 16
    addLast() to array list took 0
    addLast() to linked list using general methods took 15
    addLast() to linked list using linked list methods took 16
    addMiddleTest() to array list took 750
    addMiddleTest() to linked list using general methods took 13047
    addMiddleTest() to linked list using linked list methods took 12344

    * Using add(int, Object) for every type of addition
    ** Using addFirst(Object) and addLast(Object) for these types of additions.

    About the Stack, I believe its because its the best way to implement a Stack, as it usually grows and shrinks all the time; The use of a “circular” array is common for fast stack implementations, or at least that’s what I learned to believe.

  12. Relvox Says:

    correct me if I’m wrong, but you tests show that unless you’re planning on adding first elements to your collection, ArrayList wins.
    But that was about adds
    how about Deleting the first last and middle element?
    and several other CRUD operations?

  13. Avah Says:

    Relvox, at your request:

    addFirst() to array list took 1422
    addFirst() to linked list using general methods took 16
    addFirst() to linked list using linked list methods took 16
    addLast() to array list took 16
    addLast() to linked list using general methods took 15
    addLast() to linked list using linked list methods took 0
    addMiddleTest() to array list took 735
    addMiddleTest() to linked list using general methods took 11688
    addMiddleTest() to linked list using linked list methods took 8406
    removeFirst() to array list took 1422
    removeFirst() to linked list using general methods took 0
    removeFirst() to linked list using linked list methods took 0
    removeLast() to array list took 0
    removeLast() to linked list using general methods took 0
    removeLast() to linked list using linked list methods took 0
    removeMiddle() to array list took 734
    removeMiddle() to linked list using general methods took 7594
    removeMiddle() to linked list using linked list methods took 7719
    fetchFirst() to array list took 0
    fetchFirst() to linked list using general methods took 0
    fetchFirst() to linked list using linked list methods took 0
    fetchLast() to array list took 16
    fetchLast() to linked list using general methods took 0
    fetchLast() to linked list using linked list methods took 0
    fetchMiddle() to array list took 15
    fetchMiddle() to linked list using general methods took 9156
    fetchMiddle() to linked list using linked list methods took 9234

  14. Oliver Hutchison Says:

    Short and sweet discussion of this issue can be found here:

    http://cretesoft.com/archive/newsletter.do?issue=111&locale=en_US

    Oliver

  15. Avah Says:

    Thanks Oliver!

    Seems like I found that out myself as well. Take a look at my test results. :)

  16. Avah Says:

    I suppose that no-one actually believes each other’s test results in the end, so everyone perform their little benchmark at some point or another. :)

  17. Relvox Says:

    Well, seems like I should switch to ArrayLists in my own solution, not that the speed makes a difference to me, but for uniformity’s sake.

  18. Avah Says:

    I would say that in your specific case, where you just add items and only use them for iteration, it makes no difference whatsoever. :)

  19. kaushik Says:

    this is really useful, still a lot to investigate

  20. avrom Says:

    [...] technology. Leave a Reply. Name (required) Mail (will not be published) (required) Website …LinkedList vs. ArrayListThank you Avrom! Even though this is a bit past news (They speak about JVM 1.2 and 1.3 … took in [...]

  21. itsmylife Says:

    Stack is available since 1.0 and not 1.5

  22. Aviad Says:

    Correct! I actually meant the Queue interface and implementing classes and no-one corrected me..

  23. venki Says:

    good

  24. Manish Says:

    Depends on your use. ArrayList is much faster if you need to add and retrieve results in a loop.

    Did following tests with Java 1.6 on windows 64 bit:
    ArrayList was taking almost half time.

    public static void main(String[] args) {
    long l1 = System.currentTimeMillis();
    System.out.println(l1);
    List l = new ArrayList();
    // List l = new LinkedList();

    for (int j = 0; j < 1000000; j++) {
    l.add(String.valueOf(j));
    }
    long l2 = System.currentTimeMillis();
    System.out.println("List size " + l.size());
    // now retrieve

    for (String string : l) {
    System.out.println(string);
    }
    System.out.println(l2);

    // get random value
    System.out.println(l.get(10000));

    System.out.println("Total time " + (l2 – l1));
    }

  25. ravi Says:

    There is one more link for understanding difference :
    http://www.narendranaidu.com/2006/09/arraylist-vs-linkedlist.html

  26. Jack Says:

    Hi there are couple of things that come to my analysis when it comes to decide which one is better performance ArrayList Vs LinkedList.
    1. even after using the same Collection type for example, ArrayList herein this test case, the test program gives different resulst of time taken if the prohram is run multiple times. first time program is run takes longet than if it run second time, on the other hand doesn’t mean it takes less and less time on few run of the same program, it is sporadically taking less time and more time each time a program is run.,
    So, may be an average of couple of Program runs have to be taken into consideration.
    secondly, it also depends on whether it is based on the external resources such as the OS, IDE or 32-bit vs 64bit etc.,
    thirdly, the volume or the size of the collection.
    the results are different in different scenarios.
    Conclusion, It is very interesting to debate on such a topic, however there would be no concrete solution as such,
    As there is no right or wrong in Philosophy. every thing is context based. same goes here !!

  27. Shekhar Says:

    Nice discussion. Got to learn a lot about ArrayList and LinkedList. Thanks to the author and others to put in their thoughts as well.

  28. poornima Says:

    Thanks for the Information