What is the difference between ArrayList and LinkedList

LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array.

The difference between the two boils down to the basic difference between and Array and LinkedList.

Here are the differences between them:

  1. Since Array is an index based data-structure searching or retrieving element from Array with index is pretty fast. Array provides O(1) performance for get(index) method but remove is costly in ArrayList as you need to rearrange all elements. On the Other hand LinkedList doesn’t provide Random or index based access and you need to iterate over linked list to retrieve any element which is of order O(n).
  2. Insertions are easy and fast in LinkedList as compared to ArrayList because there is no need of resizing array and copying content to new array if array gets full which makes adding into ArrayList to amortized constant time of O(n) in worst case, while adding is O(1) operation in LinkedList in Java. ArrayList also needs to update its index if you insert something anywhere except at the end of array.
  3. Removal is like insertions better in LinkedList than ArrayList. LinkedList won’t need to re-arrange elements on removal.
  4. LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds actual object (data) but in case of LinkedList each node holds both data and address of next and previous node.

Final Verdict

ArrayList should be used where you have more retrieval than insertions and deletions. while the LinkedList should be used when you have more insertions and deletions as it won’t need resizing on insertions and deletions.

Use ArrayList in Java for all those situations where you need a non-synchronized index based access. ArrayList is fast and easy to use, just try to minimize array resizing by constructing arraylist with proper initial size using following ensureCapacity method

 void 	ensureCapacity(int minCapacity); 

which means – Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

and construct an empty list with the specified initial capacity using constructor as below.

List<Object> lst = new ArrayList<Object>(initialSize);
Advertisements

, , , , ,

  1. #1 by Anubhav on January 26, 2013 - 3:20 am

    Nice post. By the way you can also check these difference between ArrayList and LinkedList, helps to make decision better.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: