A collection is an object that can hold references to other objects.

Java Collection framework provides many interfaces (Set, List, Queue, Deque) and classes (ArrayList, Vector, LinkedList, PriorityQueue, HashSet, LinkedHashSet, TreeSet).

Hierarchy of Collection Framework

The java.util package contains all the classes and interfaces for the Collection framework.

List:-

List is an interface which can store the ordered collection of objects and duplicate values.

List interface is implemented by the classes ArrayList, LinkedList, Vector, and Stack.

ArrayList:-

The ArrayList class uses a dynamic array where it can contain duplicate elements and maintains insertion order.

Operations Complexity

get(int index) — O(1)

add(E element) -O(1) , O(n) worstcase

add(int index,E element) -O(n/2) average

remove — O(n/2) average

searching-O(n)

LinkedList

LinkedList class uses a doubly linked list to store the elements. It can maintain insertion order.

It’s faster than an array in insertion and deletion.

It can be used as a list, stack, or queue.

Operations Complexity

get(int index) — O(n/4) average

add(E element) -O(1)

add(int index,E element) -O(n/4) average,O(1)if index is 0

remove — O(n/4) average

contains() - O(n)

Set:-

Set represents the unordered set of elements that doesn’t allow us to store the duplicate items. We can store at most one null value in Set.

Set is implemented by HashSet, LinkedHashSet, and TreeSet.

TreeSet

It inherits AbstractSet class and implements the NavigableSet interface

  • It contains unique elements and doesn’t allow null element.
  • Java TreeSet sort the element in ascending order.

Operations Complexity

add() insertion takes O(log n) .

contains() — for searching it takes O(log n) .

next() — fetching each element takes O(log n) time.

HashSet:

Java HashSet class is used to create a collection that uses a hash table for storage. It allows unique and null value.

HashSet doesn’t maintain the insertion order. and it is the best to approach for search operations.

Operations Complexity

contains() — searching for an element takes O(1) time.

add() — insertion takes O(1) constant-time.

LinkedHashSet:

Java LinkedHashSet class is a Hashtable and Linked list implementation of the set interface. It inherits HashSet class and implements Set interface.

In set LinkedHashSet class maintains an insertion order.

Operations Complexity

add() — insertion O(1) .

contains() — searching O(1) .

next() — fetching an element takes O(1) time.

Queue:-

It is an ordered list of objects with its use to insert elements at the end of the list and deleting elements from the start of the list, it follows the FIFO or the First-In-First-Out.

Queue<data-type> queue = new PriorityQueue<data-type> ();

PriorityQueue class

The PriorityQueue class provides the facility of using queue. But it does not orders the elements in FIFO manner.

Insertion (add() )— O(log(n))

Deletion (Poll() ,remove()) — O(log(n))

Retrieving(peek())-O(1)

Deque Interface

Java Deque Interface is a linear collection that supports element insertion and removal at both ends. Deque is an acronym for “double ended queue”.

MAP

LinkedHashMap:-

LinkedHashMap —It contains Key and value where it allows one null key and multiple null values.

LinkedHashMap maintains order in which key-value pairs are inserted.

get() — retrieving takes O(1) constant-time

containsKey() — searching for an element takes O(1) time

next() — fetching an element takes O(1) time.

TreeMap:

It provides an efficient means of storing key-value pairs in sorted order.

  • get() — retrieving takes O(log n) constant-time.
  • containsKey() — searching for an element takes O(log n) time.
  • next() — fetching each element takes O(log n) time.