File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes ArrayList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "ArrayList" Watch "ArrayList" New topic
Author

ArrayList

Richard Mendoza
Ranch Hand

Joined: Feb 26, 2003
Posts: 48
Would there be performance issue if say, there are more than a hundred objects added in an ArrayList?
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

First, consider that a hundred is a small number, by most accounts.

Second, you have to specify what issues you're looking at. Appending items to the end of an ArrayList is very fast -- the technical term is "amortized constant time," meaning it's more or less independent of size, on the average. Accessing an item by index is also fast -- it's purely "constant time", completely independent of size. But deleting an item from the beginning (or middle) takes time proportional to the size of the list, so that gets slower as the list grows. And searching for an item also takes time proportional to the list size.

So before you can ask about performance issues, you have to say what you're going to do with the list. If all you'll do is add items and then access them in order or randomly by index, then an ArrayList will be fast no matter how many items you have. If, on the other hand, you need to both add and delete items from the list, and you need to search the list, then the more items you have, the slower things will be.


[Jess in Action][AskingGoodQuestions]
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
EFH:

After reading your post, I just had one of those "ahah" moments. At the risk of displaying my stupidity for all to see, I would like to explain what seems so obvious to me now. Maybe it will help someone in the future...if anyone ever Searches these forums, that is...

I don't know why I didn't realize before that ArrayList is backed by an array. At least, I assume that's why deleteing from the middle of the list is O(n). So am I correct in assuming that inserting to the middle of an ArrayList is also O(n)?

For some reason this never occured to me before. And since ArrayList is so common, I have wondered why you would use a LinkedList instead. But it all makes sense to me now: LinkedList provides efficient insert and delete operations in the middle of the list. The trade of is that random access is much more costly.

Am I on the right track here?

Layne
[ October 24, 2005: Message edited by: Layne Lund ]

Java API Documentation
The Java Tutorial
Mr. C Lamont Gilbert
Ranch Hand

Joined: Oct 05, 2001
Posts: 1170

Yes. You look at the List interface then you see all the classes that implement it. Then you pick the one that has the algorithm that will meet your needs most efficiently/fastest. Same with Set and Map.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

Originally posted by Layne Lund:
Am I on the right track here?


Absolutely!
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Mr. C Lamont Gilbert:
Yes. You look at the List interface then you see all the classes that implement it. Then you pick the one that has the algorithm that will meet your needs most efficiently/fastest. Same with Set and Map.


Yes, I know all about the API docs for these interfaces. I guess I never put together the tradeoffs between ArrayList and LinkedList. Of course, I've never really thought about it much. I'm sure if I had a project where efficiency was a concern I would have looked it up to compare.

Layne
Stuart Ash
Ranch Hand

Joined: Oct 07, 2005
Posts: 637
Originally posted by Ernest Friedman-Hill:
First, consider that a hundred is a small number, by most accounts.

Second, you have to specify what issues you're looking at. Appending items to the end of an ArrayList is very fast -- the technical term is "amortized constant time," meaning it's more or less independent of size, on the average. Accessing an item by index is also fast -- it's purely "constant time", completely independent of size. But deleting an item from the beginning (or middle) takes time proportional to the size of the list, so that gets slower as the list grows. And searching for an item also takes time proportional to the list size.

So before you can ask about performance issues, you have to say what you're going to do with the list. If all you'll do is add items and then access them in order or randomly by index, then an ArrayList will be fast no matter how many items you have. If, on the other hand, you need to both add and delete items from the list, and you need to search the list, then the more items you have, the slower things will be.


Ernest, can you mention some pointers on the net for good material which explains this concept in depth?


ASCII silly question, Get a silly ANSI.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18993
    
    8

This link here:

Kabutz Newsletter 111

suggests that deleting from the middle of a LinkedList isn't that much faster than deleting from the middle of an ArrayList. Apparently because finding the node to delete is much faster in an ArrayList, but you can read for yourself and draw your own conclusions.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

Originally posted by Paul Clapham:
This link here:

Kabutz Newsletter 111

suggests that deleting from the middle of a LinkedList isn't that much faster than deleting from the middle of an ArrayList.


OK, that's twice in as many days that I've seen people linking to this blog, and both times, it's been an attack on a straw man. Deleting an item from a linked list is faster than deleting an item from an array list, both theoretically and practically. You'll find a discussion of this in every algorithms textbook ever written. But that statement assumes that you already know where the item is; everyone seems to understand this but our blogger friend. If you compare a search plus a delete, then you're talking about a different problem altogether, and the results depend on the implementation, not on theory. If you need to do fast lookups, then don't use a List at all -- use a Map. If you're always iterating over the collection, though, and then occasionally encounter an item to delete during that iteration, then use a LinkedList.

The other entry I saw from this web site was about the relative speed of garbage collection in the presence and absence object caching. But he made the comparison using millions instances of java.lang.Object, and of course, that's ridiculous -- no one caches those. Object caches are for substantial objects. Compare allocating vs. caching a hundred JDialogs full of components, and then we'll see which way the comparison goes!

My recommendation is to bring your salt shaker if you read "The Java(tm) Specialists' Newsletter".
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

Originally posted by Stuart Ash:


Ernest, can you mention some pointers on the net for good material which explains this concept in depth?


Josh Bloch's Collections article from the Java Tutorial covers all of this, especially in the "Implementations" and "Algorithms" section. But any algorithms textbook, or online algorithms tutorial, will talk about this kind of material. Personally I'm a fan of Bob Sedgewick's "Algorithms" books.
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

Originally posted by Stuart Ash:
...can you mention some pointers on the net for good material which explains this concept in depth?

Ernest has already responded to this above, but I'll add my favorite: The collections chapter in Bruce Eckel's Thinking in Java...

http://www.faqs.org/docs/think_java/TIJ313.htm

By the way, towards the end of this chapter, Mr. Eckel includes some test code along with summaries of results, demonstrating that...
...insertions and removals from the middle of a list are dramatically cheaper for a LinkedList than for an ArrayList -- especially removals.

[ October 28, 2005: Message edited by: marc weber ]

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18993
    
    8

Deleting an item from a linked list is faster than deleting an item from an array list, both theoretically and practically. You'll find a discussion of this in every algorithms textbook ever written. But that statement assumes that you already know where the item is; everyone seems to understand this but our blogger friend. If you compare a search plus a delete, then you're talking about a different problem altogether...
Not necessarily; I'm sure that many people wouldn't notice that calling the remove(int) or remove(Object) method on a List object requires a search followed by a delete, whereas deleting via the remove() method of a ListIterator only requires the delete. Assuming reasonable implementations, that is. So for that reason I think that the bare statement "Deleting an item from a linked list is faster than deleting an item from an array list" is misleading.

But I did say "draw your own conclusions". As you suggest, it helps to know what the question is first. My salt shaker is always handy.
Tony Morris
Ranch Hand

Joined: Sep 24, 2003
Posts: 1608
Originally posted by Ernest Friedman-Hill:


OK, that's twice in as many days that I've seen people linking to this blog, and both times, it's been an attack on a straw man. Deleting an item from a linked list is faster than deleting an item from an array list, both theoretically and practically. You'll find a discussion of this in every algorithms textbook ever written. But that statement assumes that you already know where the item is; everyone seems to understand this but our blogger friend. If you compare a search plus a delete, then you're talking about a different problem altogether, and the results depend on the implementation, not on theory. If you need to do fast lookups, then don't use a List at all -- use a Map. If you're always iterating over the collection, though, and then occasionally encounter an item to delete during that iteration, then use a LinkedList.

The other entry I saw from this web site was about the relative speed of garbage collection in the presence and absence object caching. But he made the comparison using millions instances of java.lang.Object, and of course, that's ridiculous -- no one caches those. Object caches are for substantial objects. Compare allocating vs. caching a hundred JDialogs full of components, and then we'll see which way the comparison goes!

My recommendation is to bring your salt shaker if you read "The Java(tm) Specialists' Newsletter".


LOL, well said
An important lesson to take here is that the internet, and even tech books, generally portray rubbish to the masses - this is not a corner case. Reiterating the guff doesn't make it "more correct". Take the best possible lesson from every piece of information, regardless of how true or untrue it is. There is even something to learn from absolute bollocks.

Finally, think for yourself

</two-cents currency="AU">


Tony Morris
Java Q&A (FAQ, Trivia)
Ken Blair
Ranch Hand

Joined: Jul 15, 2003
Posts: 1078
I don't understand where the flaw in his test lies. He's removing an element using LinkedList and specifying the location, shouldn't that be faster?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: ArrayList