aspose file tools*
The moose likes Beginning Java and the fly likes ArrayList or LinkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "ArrayList or LinkedList" Watch "ArrayList or LinkedList" New topic
Author

ArrayList or LinkedList

Chetan Raju
Ranch Hand

Joined: Aug 02, 2006
Posts: 109
Which is faster for Iteration ? An ArrayList or a LinkedList ? What about insertions and deletions ?
Shaan Shar
Ranch Hand

Joined: Dec 27, 2005
Posts: 1249

Originally posted by Chetan Raju:
Which is faster for Iteration ? An ArrayList or a LinkedList ? What about insertions and deletions ?


Well about your question

LinkedList is a doubly linked list allowing constant time access to the first and last elements, constant time appending of a single element to the end of the list or prepending a single element to the beginning of the list (deletion is also quick from the front or back, and deletion near the front or back has low overhead), linear time random access to elements in the middle, and linear time iteration over all elements in order.

ArrayLists allow constant time random access to all elements, amortized constant time appending of a single element to the end of a list but gets sluggish if you want to add and delete stuff from places other than the end of the list, particularly the beginning.

LinkedLists will have a higher memory overhead since even in the most efficient memory representation each element maintains two extra pointers, whereas an ArrayList maintains an array no more than twice as large as contents which won't cost more memory than maintaining a single extra pointer per element and will usually cost less. LinkedLists will also have an additional garbage collection overhead since a object is created for each element.

LinkedLists make handy queues and are also good when there won't be random access but there will be iteration with an Iterator or ListIterator along with calls to remove(). When you don't need to add or delete items in the middle or front of the list an ArrayList is more appropriate.

Well Hope you have cleared your doubts now....

Well about the more or less comparasions check out following links

Final Performance Testing - Examples


The Best way to predict your future is to create it - Every great individual common man
Shaan Shar
Ranch Hand

Joined: Dec 27, 2005
Posts: 1249

If you want to add and remove the elements frequently then use LinkedList , for Simple retrieve use ArrayList because for simple retrieval ArrayList is faster than LinkedList

The concept used for the implementation is a wholly different one. An ArrayList is, as the name states, backed by an array (so is a Vector); access occurs index-based.
The LinkedList is a "chain" of wrappers around the contained objects (these wrappers are "linked" to their neighbour(s), only they know who it is), and the only "fixed" thing, i.e. information kept by the LinkedList's instance, is the "head" of the List (and eventually a "tail" too, for reverse access). Access occurs via iteration along the chain (therefore the faster sequential access, object removal and addition, and the slower random access).
As far as i've experienced it, the LinkedList's concept is covered in one of the first chapters of every object-based language's tutorial book.

Hope it helps you out.
Ilja Preuss
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
Originally posted by Ankur Sharma:
If you want to add and remove the elements frequently then use LinkedList


Unless you only need to add and remove at the end of the list.

for Simple retrieve use ArrayList because for simple retrieval ArrayList is faster than LinkedList


Unless the only form of "retrieve" you need is iteration over all elements.


The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: ArrayList or LinkedList