When to use ArrayList and LinkedList in java
October 8, 2012 1 Comment
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
What about traversal to that position in linked list for inserting an element at kth position?