In this blog post we will talk about When should we choose LinkedList over ArrayList for a given Scenario and Why? Both classes ArrayList and LinkedList implements List interface but have few differences if you know these differences then you would on the position to select correct data structure while coding.
- LinkedList provides constant-time complexity (Big O(1)) for insertion and removal using Iterators. But the methods to find the elements have Big O(n) time complexity (Linear Time, proportional to the size of list) and thus are poor performing.
- LinkedList has more memory overhead because it needs two nodes for each element which point to previous and next element in the LinkedList. If you are looking for random access of elements then ArrayList is the way to go for.
- To access elements are faster in ArrayList because it is index based. But to access element in LinkedList is slow because LinkedList need to navigate through the elements one by one but other hand insertion and deletion is much faster with LinkedList. If you know the node in LinkedList then just you have to change the pointers before or after nodes.
- Insertion and deletion are slow in ArrayList because during these operations ArrayList need to adjust their indexes according to deletion or insertion position if you are performing insertion or deletion in middle of indexes means an ArrayList having 20 elements. if you are inserting at index 10th then you have to shift the indexes above 10 to one more.
You may also like:
What are fail-fast and fail-safe Iterator?
What is difference between Iterator and LisIterator?
Is there concurrent version for TreeMap and TreeSet in Java Collections Framework?
Why Prime Numbers are considered in writing certain algorithms like hashcode()?
That’s all about When should we choose LinkedList over ArrayList for a given Scenario and Why?
If you have any feedback or suggestion please feel free to drop in blow comment box.