Java Collections – List – An Depth Analysis

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.

Read More