Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

which is faster in List Classes

 
Kumar Anupam
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ArrayList, Vector and LinkedList. these are three classes implementing List.

Vector is slow due to Syncronozation. but Which is the faster in execution ArrayList or LinkedList and why?

Regards
Kumar Anupam
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24213
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Kumar Anupam:

but Which is the faster in execution ArrayList or LinkedList and why?


Each is faster than the other for some operations; you need to specify faster for what. LinkedList is much faster for inserting and deleting items from anywhere except the end. ArrayList is much faster for random access -- i.e., visiting the twenty-seventh item in the list without visiting the first twenty-six.

Moving to Performance -- doesn't belong here.
 
Ajith Kallambella
Sheriff
Posts: 5782
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For an indexed access [ such as get(i) ], their(ArrayLis and Vector) performance should be fairly comparable, and so are the operations at the end of the list ie., adding or deleting elements at the end of the list.
[ June 06, 2006: Message edited by: Ajith Kallambella ]
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24213
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Ajith Kallambella:
For an indexed access [ such as get(i) ], their performance should be fairly comparable,


Sorry, beg to differ. LinkedList.get(int) has to count links from the beginning of the list, meaning you have to do O(N) operations to access element N. If you do a "for" loop and access each element of a LinkedList using get(int), then you'll visit 1, 2, 3, ... N elements in total, making such a loop O(N^2) ! This is why using Iterator (or ListIterator) for a list is so important, because a LinkedList Iterator knows how to walk the links.

Accessing any element in an ArrayList takes constant time -- it's a simple array access, O(1). Therefore ArrayList.get(int) is much faster for large lists.
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Um, for indexed access, ArrayList is almost certainly better than LinkedList. Indexed access to the middle of a list is O(n) on a LinkedList, and O(1) on an ArrayList. This is one of the primary areas where there's a significant difference in performace between the two.
 
Ajith Kallambella
Sheriff
Posts: 5782
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I agree. Index access in LinkedList is slower. My intent was to compare ArrayList with Vector.
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24213
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Ajith Kallambella:
I agree. Index access in LinkedList is slower. My intent was to compare ArrayList with Vector.


Ah, OK, sorry for jumping on you. I see you've now edited your original post to make that clear.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!