Difference between ArrayList and LinkedList is one of the most important question in java Collection framework interviews now-a-days.Interviewer can continue asking about when to use ArrayList and when to use LinkedList .In this article I am going to explain you in detail about difference between ArrayList and LinkedList and will also explain when to use what.
- Internal storage -> ArrayList internally uses dynamic array or resizable array to store the elements.LinkedList internally uses doubly linked list to store the elements.Both ArrayList and LinkedList implemnts List interface.But LinkedList implements Dequeue interface ,so LinkedList can be used as stack and also as Queue.Default capacity of ArrayList is 10 and default size of LinkedList is 0.
- Search Operation -> ArrayList search operation is faster compared to the LinkedList search operation.As ArrayList elements are index based, get(int index) in ArrayList gives the performance of O(1).But search operation performance in LinkedList is O(n) as elements need to be searched from the first node till the nth element node in average cases.Random access is possible in ArrayList using index.Random access is not possible in LinkedList.ArrayList supports binary search.LinkedList does not support binary search.
- Insertion Operation -> In ArrayList inserting a new element at a specific position is costly O(n),as new space need to be created and each elements need to be moved by 1 position ahead.LinkedList has two pointers previous and next which points to before and after neighbouring elements,so insertion requires only adjustment of these pointers and insertion performance in LinkedList in O(1).
- Deletion Operation -> In ArrayList deleting a new element at a specific position is costly O(n),as each elements need to be moved by 1 position back.LinkedList has two pointers previous and next which points to before and after neighbouring elements,so insertion requires only adjustment of these pointers and deletion performance in LinkedList in O(1).
- Updation Operation -> As ArrayList is index based updating an element require getting and setting the element i.e. search and set .So updation operation in ArrayList has O(1) performance.But Updation operation in LinkedList has O(n) performance as the element needs to be searched with O(n) performance before updating the element.
- When to use what -> Out of CRUD(create,read,update,delete) if you have more read/search and update operation and less create/insert and delete operation ,you can select ArrayList as search and update performance in ArrayList is O(1). If you have more create/insert and delete operation and less read/search and update operation ,you can select LinkedList as create/insert and delete operation performance in LinkedList is O(1).