Java Collections – List – An Depth Analysis
What is a List?
It is an ordered collection, which stores elements in a order. List can have duplicate elements.
Types of Lists:
- LinkedList
- ArrayList
- Vector
- CopyOnWriteArrayList
LinkedList:
It is a linear data structure where each element point to the next element.
What is the internal Implementation of List?
Internal implementation of LinkedList is – Doubly LinkedList.
So what is the difference between Single LinkedList and Doubly LinkedList?
Single Linked List:
In a single linked list, all the elements when inserted will point to the next node of the element and the last element will point to the first element. So whats is the draw back of this, we cant do reversal process, only one way access is possible. Example if we are at element 3, we cant go back to element 2. we need to pass to element 4, then element 1 and then to element 2.
Doubly Linked List:
In double linked list, all the nodes are interconnected and can do reversal operations. The last node is connected to first node and same way first one is connected to the last node.
Advantages of Doubly Linked List Over Single Linked List:
- We can traverse in both the directions
- We can easily insert a new node before the given node.
Disadvantages of Doubly Linked List over Single Linked List:
- Extra space required for previous pointer (since it is interconnected one for previous and one for next required)
- Insertion and deletion requires extra operation as previous pointer and next pointer has to be changed.
Advantages of LinkedList:
Linkedlist does not have initial capacity, the list grows as the elements are added to the list. Insertion and deletion are faster in linkedlist as it uses doubly linkedlist.
Why is Insertion and Deletion faster in LinkedList?
- Insertion and deletion is faster in LinkedList cause, as we have to update the pointers of the node to the next node
Disadvantages of LinkedList:
- There is no random access, only sequential access. i.e. if we try to find element “100” and the element “100” is in 20th position. List has to start looking from node 0.
- More memory is required, as Linkedlist uses pointers to point to next node. Pointers itself will consume memory.
ArrayList:
What is the internal Implementation?
- It uses Array as internal implementation
- It has initial size capacity to 10.
Advantages of ArrayList:
- Manipulation is faster in ArrayList (get operations).
Why get operation is faster in ArrayList?
- ArrayList has direct references to every element in the list, so it can get the n-th element at constant time.
Disadvantages of ArrayList:
- Insertion and deletion are more expensive, as all the elements needs to be shifted in the array
- ArrayList initial size is 10, once the size is reached it will rebuild itself with 50% more space.
Let us see the Difference between – Array, ArrayList and LinkedList
Array |
ArrayList |
LinkedList |
We need to give initial size and it will not grow dynamically |
Internal implementation of Array, but grows itself to 50% when capacity is reached |
Internal implementation is doubly LinkedList – no initial capacity, list grows as elements added |
Get operation is faster in array list |
Insertion and deletion is faster in LinkedList |
|
Insertion and deletion is slower, as all the elements needs to be shifted when delete or insertion is happened |
Manipulation is slower as it has to transverse starting from the first element |
Vector:
Vector is similar to arrayList except this is synchronized. (thread-safe)
Note: ArrayList can also be synchronized using utils – Collection.SynchronizedList();
Whats the difference between Vector vs ArrayList?
ArrayList |
Vector |
When the list limit reached, it increases its size by one and half |
When the list size is reached it increases its size by two times |
It is not synchronized, but can be made synchronized using Collections.SynchronizedList(list) |
By default it is synchronized |
CopyOnWriteArrayList:
What is CopyOnWriteArrayList?
-
It is a synchronized collection, which allows multiple thread to read values at same time.
How does it work?
-
For every update operation, CopyOnWriteArrayList creates a cloned copy of list and will update and sync with the main list at a point of time as decided by JVM
-
very efficient if you have a List where Iteration outnumber mutation e.g. you mostly need to iterate the ArrayList and don’t modify it too often.
-
No concurrent modification exception thrown, when the data is modified. As the iterator works on list but the updates take place in cloned copy of list.
-
But when you try to remove an element during Iteration, it will throw UnsupportedOperationException.