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
- 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.
You can perform random access without fearing for performence. Calling get(int) will just access the underlying array.
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.
January 19th, 2006 at 9:35 am
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?
January 19th, 2006 at 11:06 am
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.
January 19th, 2006 at 3:43 pm
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.
January 19th, 2006 at 4:14 pm
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!
January 19th, 2006 at 4:32 pm
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.
January 19th, 2006 at 4:40 pm
@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.
January 19th, 2006 at 5:22 pm
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?
January 19th, 2006 at 7:40 pm
This site has some benchmarks and comparisons between various collection classes.
http://www.precisejava.com/javaperf/j2se/Collections.htm
January 19th, 2006 at 7:48 pm
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?
January 19th, 2006 at 8:31 pm
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.
January 19th, 2006 at 8:52 pm
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)andaddLast(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.
January 19th, 2006 at 9:49 pm
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?
January 20th, 2006 at 12:04 am
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
January 20th, 2006 at 12:21 am
Short and sweet discussion of this issue can be found here:
http://cretesoft.com/archive/newsletter.do?issue=111&locale=en_US
Oliver
January 20th, 2006 at 12:25 am
Thanks Oliver!
Seems like I found that out myself as well. Take a look at my test results.
January 20th, 2006 at 12:25 am
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.
January 22nd, 2006 at 7:14 pm
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.
January 22nd, 2006 at 7:28 pm
I would say that in your specific case, where you just add items and only use them for iteration, it makes no difference whatsoever.