wood burning stoves 2.0*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes LinkedList vs ArrayList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "LinkedList vs ArrayList" Watch "LinkedList vs ArrayList" New topic
Author

LinkedList vs ArrayList

Bojan Knezovic
Ranch Hand

Joined: Nov 20, 2003
Posts: 90
K&B book states "LinkedList may iterate more slowly than an ArrayList, but it's a good choice when you need fast insertion and deletion" (chapter 7, bottom of pg. 426).
Having in mind that that LinkedList has double-linked elements and ArrayList doesn't, how come it's better for insertion&deletion? It would take extra time to set references to the previous&next elements wouldn't it?
OTOH, LinkedHashMap (also double-linked) is SLOWER than HashMap for insertion&deletion but FASTER for iteration (pg.428)?

TIA,
Bojan
imre leber
Ranch Hand

Joined: Feb 26, 2004
Posts: 31
The thing here that there are different gradations of slowness!
The official sun API says for LinkedList:
All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the begining or the end, whichever is closer to the specified index.
That would mean that insertion, deletion into the list given an index must traverse the entire list in order to find the position at which to insert/delete.
It also means that once you have the element you are looking for you can just allocate a new space for the new object and insert it in/remove it from that location by just adjusting a few pointers.

For ArrayList it says:
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
That means finding an element is fast in ArrayList. But once you find it you have to move all the elements in the list either to the back of the array or to the front of the array, possibly requiring the array to be relocated to a larger memory space.
Hope it made sense
imre leber
Ranch Hand

Joined: Feb 26, 2004
Posts: 31
For LinkedHashMap and HashMap the situation is completely different.
The hashmap is a hash table with buckets in each hash slot. Like in the API documentation:
This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
The LinkedHashMap is a linked list implementing the map interface. As said in the API documentation:
Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
This means that when you want to insert an element in a hashmap you can almost directly, dependent on the int hashCode(), go to the position where you want to insert/delete.
If you want to insert/delete from a hashtable you have to traverse through the list before you find the position where you can add/insert.
Bojan Knezovic
Ranch Hand

Joined: Nov 20, 2003
Posts: 90
Imre, thank you for your explanation.
Corey McGlone
Ranch Hand

Joined: Dec 20, 2001
Posts: 3271
There were some excellent articles posted in the JavaRanch Newsletter by Thomas Paul a while ago. You can find a great deal of information at these links:
Collections in Java, Part 1 - The List Interface
Collections in Java, Part 2 - The Set Interface
Collections in Java, Part 3 - The Map Interface
Collections in Java, Part 4 - The Collections Class


SCJP Tipline, etc.
Firas Zuriekat
Ranch Hand

Joined: May 09, 2006
Posts: 143
If you want to insert/delete from a hashtable you have to traverse through the list before you find the position where you can add/insert. [/QUOTE}

You mean the above is true for the LinkedHashMap (not for hashtable as you said above), right?
[ June 07, 2006: Message edited by: Firas Zureikat ]
 
wood burning stoves
 
subject: LinkedList vs ArrayList
 
Similar Threads
Are ArrayList really slower than LinkedList?
LinkedList
LinkedHashMap and LinkedList, iteration time doubt
How to Convert one type of Collection object data's to Another Collection Object
Linked List and Linked Hash Map