• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Speed of Accessing ArrayList and LinkedList

 
Ranch Hand
Posts: 71
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I read in Bruce Eckel's Thinking in Java that an ArrayList allows 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?

Thoughts appreciated.
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Arthur Blair
Ranch Hand
Posts: 71
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 LinkedList inexpensive?

To me, this suggests that a LinkedList would be quicker.
[ November 22, 2005: Message edited by: Arthur Blair ]
 
Ernest Friedman-Hill
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
reply
    Bookmark Topic Watch Topic
  • New Topic