ArrayList Vs LinkedList in Java
ArrayList and LinkedList are the Collection classes , and both of them implements the List interface. LinkedList implements it with a doubly-linked list while ArrayList implements it with a dynamically re-sizing array.
- Search Operation
- Memory Overhead
Search Operation in ArrayList is pretty fast when compared to the LinkedList search operation. ArrayList Method get(int index) gives the performance of O(1) while LinkedList performance is O(n). This is because ArrayList allows random access to the elements in the list as it operates on an index-based data structure while LinkedList does not allow random access as it does not have indexes to access elements directly, it has to traverse the list to retrieve or access an element from the list.
Manipulation with ArrayList is slow because it internally uses array. If We need to insert or delete element in ArrayList, it may take O(n), as it internally uses array and we may have to shift elements in case of insertion or deletion. On the other hand manipulation with LinkedList is faster than ArrayList because it uses doubly linked list so no bit shifting is required in memory. If We need to insert or delete element in LinkedList, it will take O(1), as it internally uses doubly.
An ArrayList is a simpler data structure than a LinkedList . An ArrayList has a single array of pointers in contiguous memory locations. It only has to be recreated if the array is expanded beyond its allocated size. But, LinkedList consists of a chain of nodes; each node is separated allocated and has front and back pointers to other nodes. So, unless you need to insert in the middle, splice, delete in the middle etc. an ArrayList will usually be faster. It needs less memory allocations, has much better locality of reference (which is important for processor caching) etc.
ArraylList behaves as List as it implements list. LinkedList behaves as List a well as the Queue as it implements List and Queue both.
ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbour nodes hence the memory consumption is high in LinkedList comparatively.