• 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

which is faster in List Classes

 
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
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

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.
 
Sheriff
Posts: 5782
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
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

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.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
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

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.
 
Oh. Hi guys! Look at this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic