ArrayList vs LinkedList : Both ArrayList and LinkedList implement the List interface, but what’s the difference then ? The main difference between ArrayList and LinkedList is in ArrayList which is implemented using an extensible array. As more items are added to ArrayList, its size dynamically increases. Its elements can be accessed directly using the get() and set() methods, since ArrayList is essentially an array.

LinkedList is implemented as a linked list, its add and remove performance is better than ArrayList, but bad for get() and set() methods.

In this article, we will see some differences between LinkedList and ArrayList and try to understand when and where to use LinkedList instead of ArrayList.

ArrayList vs LinkedList

All the differences between LinkedList and ArrayList have a source which is the difference between an array and a LinkedList (linked list).

  • Since the search in ArrayList is based on the index of the element then it is very fast. The get (index) method has a complexity of O (1), but the removal is expensive because you have to shift all the elements. In the case of LinkedList, it does not have direct access to items, you have to go through the whole list to retrieve an item, its complexity is equal to O (n).
  • Inserts are easy in LinkedList compared to ArrayList because there is no risk when resizing and adding the item to LinkedList and its complexity is O (1), while ArrayList shifts all items with a complexity of O (n) in the worst case.
  • Removal is like inserting, better in LikedList than in ArrayList.
  • LinkedList has more memory than ArrayList because in ArrayList each index is linked with the current object, but in the case of LinkedList each node is linked with the element and address of the next and previous node.

When to use LinkedList and ArrayList in Java ?

Obviously, LinkedList is not popular like ArrayList, but is still a good choice in some cases :

  1. Your application does not need random access, because that operation is to iterate through the entire list in this case.
  2. Your app has more insert and delete than retrieve. These two operations are faster in LikedList.
  3. Use ArrayList in Java in these situations when you need unsynchronized access. ArrayList is quick and easy to use.

Performance of ArrayList and LinkedList

OperationArrayListLinkedList
get()O(1)O(n)
add()O(1)O(1)
remove()O(n)O(1)
  • ArrayList has a time complexity of O(n) for the two operations add() and remove(), but O(1) for the operation at the end of the list or for the retrieval of an element with the method get().
  • LinkedList has a complexity of O(n) for the get() operation, but O(n) for the remove() operation.

References :

Laisser un commentaire