What are differences between ArrayList and LinkedList in java
LinkedList vs ArrayList in Java
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 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 array
and copying content to new array if array gets full which makes adding into ArrayList of O(n) in 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 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 actual object (data) but in case of LinkedList each node holds both data and address of next and previous node.
Difference between ArrayList and LinkedList
ArrayList and LinkedList both implements List interface and maintains insertion order. Both are non synchronized classes.
But there are many differences between ArrayList and LinkedList classes that are given below.
|
ArrayList
|
LinkedList
|
|---|---|
|
1) ArrayList internally uses dynamic array resizable array to store the elements.
|
LinkedList internally uses doubly linked list to store the elements.
|
|
2) Manipulation with ArrayList is slow because it internally uses array. If any element is removed from the array, all the bits are shifted in memory.
|
Manipulation with LinkedList is faster than ArrayList because it uses doubly linked list so no bit shifting is required in memory.
|
|
3) ArrayList class can act as a list only because it implements List only.
|
LinkedList class can act as a list and queue both because it implements List and Deque interfaces.
|
|
4) ArrayList is better for storing and accessing data.
|
LinkedList is better for manipulating data.
|
When to use LinkedList and ArrayList in Java
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 than 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 its much faster than ArrayList.
- Share on:
post a comment