Difference between LinkedList and ArrayList in Java (original) (raw)

LinkedList and ArrayList both implement List Interface but how they work internally is where the differences lie. The main difference between ArrayList and LinkedList is that ArrayList is implemented using a resizable array while LinkedList is implemented using doubly LinkedList. ArrayList is more popular among Java programmers than LinkedList as there are few scenarios on which LinkedList is a suitable collection than ArrayList. In this article, we will see some differences between LinkedList and ArrayList and try to find out when and where to use LinkedList over ArrayList.

LinkedList vs ArrayList in Java

All the differences between LinkedList and ArrayList have their root in the difference between Array and LinkedList data structure. If you are familiar with Array and LinkedList data structure you will most likely derive the following differences between them:

1. Since Array is an index based data-structure searching or getting element from Array with index is pretty fast. Array provides O(1) performance for get(index) method but remove is costly in ArrayList as you need to rearrange all elements.

On the Other hand, LinkedList doesn't provide Random or index-based access and you need to iterate over the linked list to retrieve any element which is of order O(n).

2. Insertions are easy and fast in LinkedList as compared to ArrayList because there is no risk of resizing the array and copying content to the new array if the array gets full which makes adding into ArrayList of O(n) in the worst case while adding is O(1) operation in LinkedList in Java. ArrayList also needs to update its index if you insert something anywhere except at the end of the array.

3. Removal is like insertions better in LinkedList than ArrayList.

4. LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds an actual object (data) but in the case of LinkedList, each node holds both data and address of the next and previous node.

When to use LinkedList and ArrayList in Java?

As I said LinkedList is not as popular as ArrayList but still, there are situations where a LinkedList is a better choice than ArrayList in Java. Use LinkedList in Java if:

1. Your application can live without Random access. Because if you need nth element in LinkedList you need to first traverse up to nth element O(n) and then you get data from that node.

2. Your application is more insertion and deletion driver and you insert or remove more than retrieval. Since insertion or removal doesn't involve resizing it's much faster than ArrayList.

And, if you need to know more diffrences betwen ArrayList and LinkedList in Java then here is a nice talbe which you can refer:

That’s all on the difference between ArrayList and LinkedList in Java. Use ArrayList in Java for all their situation where you need non-synchronized index-based access. ArrayList is fast and easy to use, just try to minimize array resizing by constructing ArrayList with a proper initial size.

Other Java Tutorials you may like

Thanks for reading this article so far. Let me know if this question was asked to you on any Java Interviews? It was asked to me multiple times and its my favorite one? what about you?