ArrayList vs. LinkedList

[Puja Sinha]

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]

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

to start with -> check here and here

[Shawn Smith]

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]

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.