Collections In Java | A Helpful Framework

The Java collections framework provides a set of interfaces and classes to implement various data structures and algorithms.

So yes, we don’t exactly have to write the code again for Linked-list, Queue, etc data structures.

Cool !! Isn't it ?

Also Collections were introduced to overcome the demerits of Arrays i.e contiguous memory, no heterogeneous data type support, and no dynamic size functionality.

So let’s see what exactly the Collections constitute of :

Collection Hierarchy

Iterable

The Iterable interface is the root of all the collection classes. The Collection interface extends the Iterable interface and hence all sub classes of Collections also implement the Iterable interface.

Collection

Collection is the interface which is implemented by all the classes in the Collections framework. It consists of all the common methods that will be required in each every collection.

It has 3 child interfaces :

1. List
2. Queue
3. Set

These 3 are differentiated on the basis of their implementations and their functionality.

1. List

List is child of Collection interface. So it basically stores a list type data structure in which we can have order collection of objects as well as duplicate values.

To initialise we need to write :

List <data-type> list1= new TypeOfList();

Some of the commonly used methods of the Collection interface that's also available in the List interface are:

• add() - adds an element to a list
• addAll() - adds all elements of one list to another
• get() - helps to randomly access elements from lists
• iterator() - returns iterator object that can be used to sequentially access elements of lists
• set() - changes elements of lists
• remove() - removes an element from the list
• removeAll() - removes all the elements from the list
• clear() - removes all the elements from the list (more efficient than removeAll())
• size() - returns the length of lists
• toArray() - converts a list into an array
• contains() - returns true if a list contains specified element

List Interface further have the following sub classes which implement it:

a) ArrayList

ArrayList uses a dynamic array to store duplicate values as well.

It maintains the insertion order i.e the output is printed as it was inserted.

Since it is a type of Array, more-over a dynamic one, elements stored in it can be randomly accessed, unlike Linked List.

public static void main(String args[]){ 
//Creating arraylist
ArrayList<String> list=new ArrayList<String>();
//Adding object in arraylist
list.add("Ravi"); 
list.add("Vijay"); 
list.add("Ravi"); 
list.add("Ajay"); 
//Traversing list through Iterator Iterator itr=list.iterator(); 
while(itr.hasNext()){ 
System.out.println(itr.next()); 
} 
}
Output :
Ravi
Vijay
Ravi
Ajay

So the Time Complexity of this collection can be determined by its operations i.e :

add() -> O(1)

get() -> O(1)

remove() -> O(n)

contains() -> O(n)

So here we can conclude that adding the elements and getting the element is the fastest, Hence Array-list is preferred whenever there is continuous access calls to the items in the list.

But what if we were working on an list of elements and the current Array-list falls short of size but only a few elements are remaining to be appended.

So can we use ArrayList?

Yes of course, we can. It is dynamic it will increase its size, but not according to the elements required instead it has a “double the size when full” strategy for some or all of the space utilization. And hence it is not preferred in these situations , rather a LinkedList is preferred.

b) LinkedList

LinkedList uses a doubly linked list internally to store the elements and therefore no shifting is required , hence it is incredibly fast for manipulation.

It stores duplicate values and also maintains the insertion order.

public static void main(String args[]){
//Creating arraylist
LinkedList<String> list=new LinkedList<String>();
//Adding object in arraylist
list.add("Ravi"); 
list.add("Vijay"); 
list.add("Ravi"); 
list.add("Ajay");
//Traversing list through Iterator Iterator itr=list.iterator();
while(itr.hasNext()){ 
System.out.println(itr.next()); 
} 
}
Output:
Ravi
Vijay
Ravi
Ajay

So the Time Complexity of this collection can be determined by its operations i.e :

add() -> O(1)

get() -> O(n)

remove() -> O(1)

contains() -> O(n)

So here we can conclude that adding the elements and removing them is the fastest operation , Hence Linked-list is preferred whenever there is continuous updation and deletion of items in the list. Here it getting the element by index is not possible as Linked List traverses its elements through pointers and hence it will take linear time to arrive at that element, on the contrary , unlike array-list or arrays, it doesn't have to shift the whole list of elements in the case of adding or removing elements from anywhere in the list.

c) Vector

Vector is similiar to ArrayList , i.e it uses dynamic array only the difference is that it is synchronized i.e can be used for multi-threading unlike ArrayList and also it contains several methods apart from those in Collections framework which are mentioned below :

• set()changes an element of the vector
• size()returns the size of the vector
• toArray()converts the vector into an array
• toString()converts the vector into a String
• contains()searches the vector for specified element and returns a boolean result

public static void main(String args[]){
//Creating arraylist
Vector<String> v=new Vector<String>();
//Adding object in arraylist
v.add("Ravi"); 
v.add("Vijay"); 
v.add("Ravi"); 
v.add("Ajay");
//Traversing list through Iterator Iterator itr=list.iterator();
while(itr.hasNext()){ 
System.out.println(itr.next()); 
} 
}
Output:
Ravi
Vijay
Ravi
Ajay

• ArrayList is not thread safe as its methods are not synchronized, whereas Vector’s methods are synchronized. So, in multithreading environment, we can use Vector without making any extra efforts.
• Time Complexity of Vector in case of : get() →O(1)
• Adding and removing elements from the end : O(1)

Stack

Stack is subclass of Vector Class. It implements the Last-In-First-Out (LIFO) principle.

It has all the methods of Vector as well as provides methods like push, pop for insertion and deletion of elements.

public static void main (String[] args) { 
//creating an object of Stack class 
Stack stk = new Stack(); 
//pushing elements into stack 
stk.push("BMW"); 
stk.push("Audi"); 
stk.push("Ferrari"); 
stk.push("Bugatti"); 
stk.push("Jaguar"); 
//iteration over the stack 
Iterator iterator = stk.iterator(); 
while(iterator.hasNext()) 
{ 
Object values = iterator.next(); 
System.out.println(values); 
} 
}
Output:
BMW
Audi
Ferrari
Bugatti
Jaguar

2. Queue

Queue is also child of Collection interface. So it basically stores elements in an ordered list maintaining the First-In-First-Out (FIFO) Principle.

To initialise we need to write :

Queue <data-type> q1= new TypeOfQueue();

Following are methods of Queue Interface :

boolean add(object) : It is used to insert the specified element into this queue and return true upon success.

boolean offer(object) : It is used to insert the specified element into this queue.

Object remove() : It is used to retrieves and removes the head of this queue.

Object poll() : It is used to retrieves and removes the head of this queue, or returns null if this queue is empty.

Object element() : It is used to retrieves, but does not remove, the head of this queue.

Object peek() : It is used to retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

Queue Interface further have the following sub classes which implement it:

a.) PriorityQueue

In this, it hold the elements which are to be processed by their priorities.

It does not allow null values.

public static void main(String args[]){ 
PriorityQueue<String> queue=new PriorityQueue<String>(); queue.add(“Amit”); 
queue.add(“Vijay”); 
queue.add(“Karan”); 
queue.add(“Jai”); 
queue.add(“Rahul”); 
System.out.println(“head:”+queue.element()); System.out.println(“head:”+queue.peek()); System.out.println(“iterating the queue elements:”); 
Iterator itr=queue.iterator(); 
while(itr.hasNext())
{ 
System.out.println(itr.next()); 
} 
queue.remove(); 
queue.poll(); 
System.out.println(“after removing two elements:”); 
Iterator<String> itr2=queue.iterator(); 
while(itr2.hasNext())
{ 
System.out.println(itr2.next()); 
} 
}

So the Time Complexity of this collection can be determined by its operations i.e :

offer() -> O(log n)

peak() -> O(1)

poll() -> O(logn)

size() -> O(1)

Deque

Deque extends the Queue Interface. In this we can insert and delete elements from both the side of the queue. Deque stands for double-ended queue.

Following are methods of Deque Interface :

boolean add(object) : It is used to insert the specified element into this deque and return true upon success.

boolean offer(object) : It is used to insert the specified element into this deque.

Object remove() : It is used to retrieves and removes the head of this deque.

Object poll() : It is used to retrieves and removes the head of this deque, or returns null if this deque is empty.

Object element() : It is used to retrieves, but does not remove, the head of this deque.

Object peek() : It is used to retrieves, but does not remove, the head of this deque, or returns null if this deque is empty.

b.) ArrayDeque

ArrayDeque implements the Deque Interface and hence provides facility of using deque as well as resizable array.

As we can update from both the ends, it is faster than ArrayList and Stack.

Null elements are not allowed in it.

public static void main(String[] args) { 
//Creating Deque and adding elements 
Deque<String> deque = new ArrayDeque<String>(); 
deque.add(“Ravi”); 
deque.add(“Vijay”); 
deque.add(“Ajay”); 
//Traversing elements 
for (String str : deque) 
{ 
System.out.println(str); 
} 
} 
Output : 
Ravi
Vijay
Ajay

So the Time Complexity of this collection can be determined by its operations i.e :

offer() -> O(1)

peak() -> O(1)

poll() -> O(1)

size() -> O(1)

So as you can see, all the operations have time complexity of O(1), and also we know that we can update it from both the ends, it is faster than ArrayList as well as Stack.

3.Set

Set is child of Collection interface. So it basically consists of unordered set of elements and also doesn't allow duplicate items. Only 1 null value is allowed in a set.

Set <data-type> set1= new TypeOfSet();

So Set interface has following associated methods with it :

add(E e) : It is used to add the specified element to this set if it is not already present.

clear() : It is used to remove all of the elements from the set.

clone() : It is used to return a shallow copy of this HashSet instance: the elements themselves are not cloned.

contains(Object o) : It is used to return true if this set contains the specified element.

isEmpty() : It is used to return true if this set contains no elements.

iterator() : It is used to return an iterator over the elements in this set.

remove(Object o) : It is used to remove the specified element from this set if it is present.

size() : It is used to return the number of elements in the set.

spliterator() : It is used to create a late-binding and fail-fast Spliterator over the elements in the set.

Set Interface further have the following sub classes which implement it:

a.) HashSet

HashSet consists of elements stored in it according to their hash-values calculated through hash-table. It implements hashing technique and stored only unique items.

public static void main(String args[]){ 
//Creating HashSet and adding elements 
HashSet<String> set=new HashSet<String>(); 
set.add(“Ravi”); 
set.add(“Vijay”); 
set.add(“Ravi”); s
et.add(“Ajay”); 
//Traversing elements 
Iterator<String> itr=set.iterator(); 
while(itr.hasNext())
{ 
System.out.println(itr.next()); 
} 
}
Output : 
Vijay
Ravi   // Duplicate item, i.e "Ravi" is ignored!!
Ajay 

So the Time Complexity of this collection can be determined by its operations i.e :

add() -> O(1)

remove() -> O(1)

contains() -> O(1)

next() -> O(h/n)

b.) LinkedHashSet

LinkedHashSet basically is an implementation of both Linked List and a Hash Set. Like LinkedList it maintains the insertion order and permits null elements as well as like Hash Set it contains Unique elements.

public static void main(String args[]){ 
//Creating HashSet and adding elements 
LinkedHashSet<String> set=new LinkedHashSet<String>(); 
set.add(“Ravi”); 
set.add(“Vijay”); 
set.add(“Ravi”); s
et.add(“Ajay”); 
//Traversing elements 
Iterator<String> itr=set.iterator(); 
while(itr.hasNext())
{ 
System.out.println(itr.next()); 
} 
}
Output : 
Ravi
Vijay
Ajay

So the Time Complexity of this collection can be determined by its operations i.e :

add() -> O(1)

remove() -> O(1)

contains() -> O(1)

next() -> O(1)

So from above we can conclude that almost every operation takes O(1) time complexity in LinkedHashSet as it is combination of Linked List as well as Hash Set

SortedSet

SortedSet is also and interface similar to Set interface, only the difference is in SortedSet, elements are arranged in increasing (ascending) order.

The SortedSet can be instantiated as:

SortedSet<data-type> set = new TreeSet();

c.) TreeSet

TreeSet is similar to HashSet as it contains unique elements but it uses Tree structure for storage and hence the data access and retrieval time is fast and also the elements are stored in ascending order.

public static void main(String args[]){ 
//Creating HashSet and adding elements 
TreeSet<String> set=new TreeSet<String>(); 
set.add(“Ravi”); 
set.add(“Vijay”); 
set.add(“Ravi”); s
et.add(“Ajay”); 
//Traversing elements 
Iterator<String> itr=set.iterator(); 
while(itr.hasNext())
{ 
System.out.println(itr.next()); 
} 
}
Output : 
Ajay
Ravi
Vijay

So the Time Complexity of this collection can be determined by its operations i.e :

add() -> O(logn)

remove() -> O(logn)

contains() -> O(logn)

next() -> O(logn)

So from above we can conclude that almost every operation takes O(logn) time complexity in TreeHashSet as it is Red-Black tree data structure.

So we can conclude that introduction to collections framework in java reduced the effort to code the useful Data Structures and algorithms as well as provided re-usability of them, also furthermore increased the efficiency and ease to code bigger programs as well as overcame the problem with the Primitive Arrays and provided a much more efficient and complex functionalities.

This was a quick Glance of Collections Framework in Java.

Thanks for Reading, See you Guys in next Blog !!