Posted by: lrrp | June 24, 2015

Difference between ArrayList and LinkedList in java

One of the common interview question is “What is difference between ArrayList and LinkedList”.Before we actually see differences,let me give you brief introduction of both.

ArrayList

  • ArrayList is implementation of list interface.
  • ArrayList is not synchonized(so not thread safe)
  • ArrayList is implemented using array as internal data structure.It can be dynamically resized .

LinkedList

  • LinkedList is implementation of list and deque interface.
  • LinkedList is not synchronized
  • LinkedList is implemented using doubly linked list as internal data structure.

ArrayList vs LinkedList:

Parameter ArrayList LinkedList
Internal data structure It uses dynamic array to store elements internally It uses doubly Linked List to store elements internally
Manipulation If We need to insert or delete element in ArrayList, it may take O(n), as it internally uses array and we may have to shift elements in case of insertion or deletion If We need to insert or delete element in LinkedList, it will take O(1), as it internally uses doubly LinkedList
Search Search is faster in ArrayList as uses array internally which is index based. So here time complexity is O(1) Search is slower in LinkedList as uses doubly Linked List internally So here time complexity is O(n)
Interfaces ArrayList implements List interface only, So it can be used as List only LinkedList implements List,Deque interfaces, so it can be used as List,Stack or Queue

When to use ArrayList or LinkedList?

It actually depends on our need.

  • If we have more insertion or deletion then we should use LinkedList.
  • If we have less insertion or deletion and more search operations then we should use ArrayList.

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

Categories

%d bloggers like this: