In Java Collections framework there are two general-purpose List implementations— ArrayList and LinkedList. In this post we'll see the differences between ArrayList and LinkedList in Java to understand these two implementations better. Knowing the differences between ArrayList and LinkedList will also help you to determine which implementation is better in which scenario.
ArrayList Vs LinkedList in Java
1- How they are internally implemented-
ArrayList internal implementation uses an array to store its element. The size of the array can be increased dynamically if needed that is why ArrayList is known as the resizeable array implementation.
LinkedList is internally implemented as a doubly linked list where elements are stored as object of type node. In the node object apart from the element, references of the previous and next nodes are also stored.
2- Initial capacity-
ArrayList has a constructor ArrayList(int initialCapacity) which can construct an ArrayList of the specified capacity. Even if no initial capacity is specified ArrayList is created with the default capacity of 10.
LinkedList in Java doesn’t have any initial capacity, as and when an element is added object of type Node is created.
3- Adding element-
ArrayList in Java has an array of size 10 created by default even if internal capacity is not specified. Since array
is created as a contiguous memory block so adding element in an ArrayList is as simple as putting element in the next
index but there are some complexities involved.
If array is full then the insertion of next element in the ArrayList would require resizing the array and moving all
the existing element of the ArrayList to the new array.
If elements are frequently added to the beginning of the ArrayList then also there is added overhead of shifting all
the elements of the array to make place for the new element. Same overhead is there of you add element using the
add(int index, E element) method to add element at the specified position.
With all these possibilities while adding element to the ArrayList, add operation in ArrayList runs in amortized
constant time, that is, adding n elements requires O(n) time.
LinkedList insertion is O(1) as adding element just requires to adjust references for previous and next nodes.
But one thing to note here is that the constant factor in ArrayList is low compared to that for the LinkedList implementation.
4- Removing element-
Removing element from an ArrayList requires less time reaching to the element that has to be removed (just accessing the array index) but requires shifting all the elements, after the element that has to be removed, backward to fill the space left by the removed element. So removing the last element of the ArrayList is O(1) where as for the first element is O(n).
In the case of LinkedList also performance is O(n) as reaching to the element that has to be removed is a linear operation. Again remove() and removeFirst() methods which remove the first element require O(1) time. Removing last element using removeLast() method will also be O(1) as reference to the last node is also stored.
5- Accessing element-
In ArrayList retrieving an element using get(int index) method is O(1) as it just need to access that array index.
In case of LinkedList get(int index) method is O(n) as it requires linear traversal to reach to that index.
6- Removing element when iterating-
In ArrayList deleting element while iterating over the List still has that overhead of shifting the elements.
In LinkedList deleting element while iterating over the List is O(1) as iterator is already positioned at the element that has to be removed.
7- Overall performance-
As per official JavaDocs also ArrayList should be preferred over LinkedList.
"If you think you want to use a LinkedList, measure the performance of your application with both LinkedList and ArrayList before making your choice; ArrayList is usually faster."
Reference: https://docs.oracle.com/javase/tutorial/collections/implementations/list.html
That's all for the topic ArrayList Vs LinkedList in Java. If something is missing or you have something to share about the topic please write a comment.
You may also like
No comments:
Post a Comment