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

Collections – List – ArrayList and LinkedList

Collections – List – ArrayList and LinkedList:
So far we have already discussed regarding Set and Map. In this article we are going to discuss regarding Lists. There are two types of Lists – ArrayList and LinkedList – (HashSet here and HashMap here)

collections

 

Difference Between ArrayList and LinkedList: 

ArrayList LinkedList
ArrayList uses array to store the elements LinkedList uses doubly linked list to store the elements
ArrayList needs to know the size or it will re-create when it needs to grow LinkedList grows dynamically
ArrayList Manipulation is slow since it is an array LinkedList Manipulation is fast


When should we use ArrayList and When to use LinkedList:
ArrayList:

  • When random access of elements are needed
  • If we know the size of array ahead so we can allocate the memory

LinkedList:

  • When we need more insertions/deletions
  • When we do not know the size to be allocated

Example Program:

Output:
op

 HashSet here
HashMap here

 

Read More