I read in Bruce Eckel's Thinking in Java that an ArrayListallows rapid access to elements, but is slow when inserting and removing elements from the middle of the list. Also that a LinkedList has inexpensive insertions and deletions from the middle of the list but is relatively slow for random access.
I thought I would test this out so I wrote the following code:
When I run, I get the following:
As I would have expected accessing the random values is much faster for the ArrayList than the LinkedList. But why is it marginally quicker to add to the middle of the ArrayList?
Shouldn't the LinkedList be much better with this one?
add(int, Object) has to first find the location in the list. For LinkedList, this involves walking the links from the beginning -- the same thing that makes get() slow. So your results are expected.
To do fast add(), remove(), and set() operations on a LinkedList, you have to do them via a ListIterator. You can walk through the list and insert, delete, or change an item at the current iterator position at any time. These operations are cheap -- they're "O(1)", they take constant time, independent of list length. Walking the iterator to the right position, though, is O(N) -- it takes time proportional to the distance walked.
Thanks for the reply, Ernest. I can understand what you're saying regarding the walking distance and it potentially taking a while to reach the middle of the LinkedList. But once you get there shouldn't the addition be a relatively quick and simple operation?
Whereas, with an ArrayList, I was under the impression that you would reach the middle quickly; but the reason it takes longer would be because you have to create a new array with space for the new element, and then copy the previous elements into the new array.
If it is quicker to access elements in the middle of an ArrayList even though Bruce describes it as slow. What does he mean when he calls adding to the middle of a LinkedListinexpensive?
To me, this suggests that a LinkedList would be quicker. [ November 22, 2005: Message edited by: Arthur Blair ]
author and iconoclast
One thing to remember is that ArrayLists don't have to contain an array that's exactly the right size: they can (and usually do) contain an array that's a little larger than needed. That means most insertions won't require reallocation, just moving (copying) the existing array elements. Allocation is actually much cheaper than most people think, anyway. The truth is that allocation is considerably faster in Sun's Java VMs than in the typical malloc() implementation used in C.
Your understanding is correct and your argument makes sense. But if you think about it, the amount of work it takes to copy (on average) half the elements in an ArrayList is quite comparable to the amount of work it takes to call get(0).next().next().next().next()....next() to locate a particular spot in a LinkedList -- so it's not surprising that calling add(int, Object) takes about the same time for both classes, even though the implementations are completely different, and for the two classes, the time goes into two different pursuits.
Another way to put it: add(int, Object) has to do random access, and random access for LinkedLists is slow.
assume you want to add an element between item A and B. before you come in, A has a reference to the "next" element, namely B. in a doubly linked list, B also has a "previous" reference to A.
once you know where to put the new element, all you have to do is set it's "next" reference to B, and A's next reference to it (the new one). in the doubly linked list, you have to do the same thing for all the previous posts.
it doesn't matter how big the list is, ONCE YOU FIND THE SPOT, there are two or four references that need to be changed. and that's easy to do. quick, cheap and easy.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors