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


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "ArrayList vs. LinkedList" Watch "ArrayList vs. LinkedList" New topic
Author

ArrayList vs. LinkedList

Puja Sinha
Greenhorn

Joined: May 25, 2011
Posts: 27
Hi,

Why and how is the linkedList good for fast insertion and deletion while the arraylist good for fast iteration and retrieval?

Also, why and how is the LinkedHashMap fast for iteration and slow for insertion and deletion ?


Regards,
Puja
Robin John
Ranch Hand

Joined: Sep 10, 2008
Posts: 270

Search these forums you will get a lot of answers...

to start with -> check here and here


Time is what we want the most, but what we use the worst. -- William Penn
Shawn Smith
Ranch Hand

Joined: Feb 22, 2011
Posts: 41
ArrayList's are stored in contiguous memory, which means random access can be done using "pointer arithmetic" therefore has constant time and is very fast. Insertion or Deletion from anywhere but the end, however, requires that the remaining data elements have to be moved and a possible resizing memory allocation may have to occur. Adds/Removes from anywhere but the end are expensive.

LinkedLists are not stored in contiguous memory and just keep a reference to the next an previous nodes. This means that middle inserts/deletes are fast (just reassign the node references), but you can only do linear lookups because you have to traverse (non-contiguous means you can't use math to find the nth element).

LinkedHashMap contains additional data to ensure iteration order. Because that data must be managed, slower inserts/deletes. Because it is managed, faster interation (O(1)).



Jack Tol
Greenhorn

Joined: Oct 27, 2009
Posts: 24

Hi Puja,

The fact why LinkedList is good for fast insertion/deletion and ArrayList is good for fast iteration/retrieval lies in the way they are implemented.

ArrayList
The ArrayList saves elements in a normal array. This means it can access elements by array[index_number]. When deleting elements, the ArrayList moves all elements after the current index, one index to the left. With many elements this takes some time. The same goes for inserting elements at a specific index: all elements >= than the index get moved one to the right.

To handle increasing number of elements, the backing array sometimes needs to grow. When this is necessary all elements in the current array get moved to a bigger array. This happens, if necessary, when you add elements. This takes some extra time.

LinkedList
A LinkedList on the other hand saves its element in an entirely different way. Each element in an LinkedList, keeps a reference to the element before and after it in the List. So you get sort of a chain. Like:
Element 1 <--> Element 2 <--> Element 3 <--> Element 4

Now, when you remove an element, say Element 2, Element 1 will refer to Element 3 as its next element, and Element 3 will refer to Element 1 as its element before. This results in:
Element 1 <--> Element 3 <--> Element 4

So when deleting an element, this results in only two operations:
  • Change Element 1's next reference to Element 3
  • Change Element 3's next reference to Element 1

  • This makes deletion very fast in LinkedList. You don't have to move all elements beyond it like with an ArrayList. The same goes for inserting elements at a specific index:
  • Let the element before refer to the inserted element as its next element
  • Let the element after refer to the inserted element as its previous element

  • Faster again. However, when traversing and retrieving specific elements, you have to go through the elements one by one. So when you want to get element 4, the following happens:
  • Get first element's next element
  • Get second element's next element
  • Get third element's next element and return it

  • (This is just an illustration. In reality the List will traverse backwards when (size of list / 2) <= index. Starting with the last element.)

    In this case ArrayList would be faster, as it can access the element directly in the array.
     
    jQuery in Action, 2nd edition
     
    subject: ArrayList vs. LinkedList
     
    Similar Threads
    Collection classes
    LinkedList vs ArrayList
    ArrayList and LinkedList
    ArrayList vs LinkedList
    Why should ArrayList be assigned polymorphically as a List?