• Post Reply Bookmark Topic Watch Topic
  • New Topic

What is faster: array or ArrayList?  RSS feed

 
Bora Sabrioglu
Ranch Hand
Posts: 100
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey guys,

I'm just learning the API of the Collection classes and must confess that I'm really impressed by the powerful methods that the Collection interface provides which one can use with ArrayList as well...

makes me think to move from array to ArrayList alltogether in future... the only question or doubt that I have is: I know that array is very fast... is ArrayList also as fast or even faster ? (as far as iterating, access, changing of elements, etc... is concerned, the standard stuff)...

Thanks in advance
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16060
88
Android IntelliJ IDE Java Scala Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
An ArrayList internally uses an array to store elements.

But you should really not worry about such questions - computers are very fast, they can execute many millions of instructions per second, the difference in performance between for example arrays and ArrayList is totally not noticeable in 99,9% of applications.
 
Bora Sabrioglu
Ranch Hand
Posts: 100
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ah, thats great. Thank you!
 
Jelle Klap
Bartender
Posts: 1952
7
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ik gets more interesting when you compare, say, an ArrayList to a LinkedList, which are both List implementations, but perform radically different depending on how or in what context they're used. Definitely something you should consider when choosing an specific implementation.
 
Bora Sabrioglu
Ranch Hand
Posts: 100
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yes, in the book that I'm learning from (scjp6 b&k) it says that ArrayList is faster for iterating and LinkedList faster when it comes to adding/removing... I've done a search on this and on another forum there was a post which listed pretty detailed the differences:
For LinkedList<E>

get(int index) is O(n)
add(E element) is O(1)
add(int index, E element) is O(n)
remove(int index) is O(n)
Iterator.remove() is O(1) <--- main benefit of LinkedList<E>
ListIterator.add(E element) is O(1) <--- main benefit of LinkedList<E>


For ArrayList<E>

get(int index) is O(1) <--- main benefit of ArrayList<E>
add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
add(int index, E element) is O(n - index) amortized, but O(n) worst-case (as above)
remove(int index) is O(n - index) (i.e. removing last is O(1))
Iterator.remove() is O(n - index)
ListIterator.add(E element) is O(n - index)


I've looked in the API but the API does not mention this... do you (or anyone else) maybe know a book which covers this? Maybe "Effective Java" from Josh Bloch?
 
Jelle Klap
Bartender
Posts: 1952
7
Eclipse IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I own a copy of Datastructures & algorithms in Java by Robert Lafore, and it does a pretty good job of explaining different data structures, their uses and also which algorithms are used for traversal, searching, sorting etc. It does not cover the standard Collection framework though! The code samples (in Java) in the book implement the covered data structures and algorithms from scratch, which offers a pretty good insight. Also the book dates back to 2002, so the code samples are void of generics and all that sort of stuff. That does not matter all that much though. The concepts are what's important and they remain valid.
 
Bora Sabrioglu
Ranch Hand
Posts: 100
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
just added it to my wishlist thanks
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!