When to use ArrayList and LinkedList in java

These two data structures(DS) operate exactly opposite in terms of read and write operations.

ArrayList: this is build from a basic array

read operation complexity: O(1)
This is always constant because we query for an element based on index and hence there is no search involved to reach to the required element.

write operation: O(n)
Any modifications will lead to the shift of elements in an array completely, it first creates new array with new size inserts elements prior to the position of element to be inserted, then inserts the current element and inserts remaining elements after it.
Ex: If we wanna add element at 1st position then we need to shift all elements 1 position to the right and then insert element at first position

Linked List: This is build from double linked list

read operation: O(n):
Since the traversal of this data structure is based on links we need to traverse from starting position till the point we encounter the element that we are searching for, since in BIG-O notation time complexity is worst case scenario, if the element we are looking for is at last position then read operation complexity will be proportional to the length of the DS, hence O(n)

write operation: O(1):
Just by changing the links we would be able to insert the element at any position at any place in the DS which consumes same time

Advertisements

One Response to When to use ArrayList and LinkedList in java

  1. Praveen J says:

    What about traversal to that position in linked list for inserting an element at kth position?

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

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey