Java Collections — List, Queue, Sets

What are Java collections? collection of group of objects and representing that as a single unit. which helps in sorting,searching and manuplation of our data

why do we need collection?…

Disadavantages of array

1. Need contiguous memory to store elements
2. Only homogenous type data can be stored
3. It is compulsory to known the number of elements that we would inserting to array
4. Size of array is fixed

The above disadvantage can be overcome by using collection.

There are several benefits of using Java collections such as:

• Reducing the effort required to write the code by providing useful data structures and algorithms
• Java collections provide high-performance and high-quality data structures and algorithms thereby increasing the speed and quality
• Decreases extra effort required to learn, use, and design new API’s
• Supports reusability of standard data structures and algorithm

Java Collection Framework Hierarchy

Java collections: List

A List is an ordered Collection of elements which may contain duplicates. It is an interface that extends the Collection interface. Lists are further classified into the following:

1. ArrayList
2. LinkedList
3. Vectors

Array list: ArrayList is the implementation of List Interface where the elements can be dynamically added or removed from the list

syntax: ArrayList object = new ArrayList ();

Linked List: Linked List is a sequence of links which contains items. Each link contains a connection to another link.

Syntax: Linkedlist object = new Linkedlist();

Vectors : Vectors are similar to arrays, where the elements of the vector object can be accessed via an index into the vector.

syntax: Vector object = new Vector(size,increment);

Below are some of methods of List :

1. void add(int index, E element) -> It is used to insert the specified element at the specified position in a list.

2. boolean add(Collection ) ->Appends the specified element to the end of a list.

3 .void add(int index, Object element) -> Inserts the specified element at the specified position.

4.void clear() ->Removes all the elements from this list.

5. int lastIndexOf(Object o)->Return the index in this list of the last occurrence of the specified element, or -1 if the list does not contain this element.

Now let us understand more when to use an ArrayList and a Linked List

“ ArrayList should be used where more search operations are required, and LinkedList should be used where more insert and delete operation is needed."

Java collections: Queue

Queue in Java follows a FIFO approach i.e. it orders the elements in First In First Out manner. In a queue, the first element is removed first and last element is removed in the end.

Below are some of the methods of Java Queue interface:

1. boolean add(object) -> Inserts the specified element into the queue and returns true if it is a success.
2. boolean offer(object)-> Inserts the specified element into this queue.
3. Object remove() -> Retrieves and removes the head of the queue.
4. Object poll()-> Retrieves and removes the head of the queue, or returns null if the queue is empty.
5. Object element() ->Retrieves, but does not remove the head of the queue.
6. Object peek()-> Retrieves, but does not remove the head of this queue, or returns null if the queue is empty.

PriorityQueue Time Complexity

Time complexity for the methods offer & poll is O(log(n)) and for the peek() it is Constant time O(1) of java priority queue.

• In Java programming, Java Priority Queue is implemented using Heap Data Structures and Heap has O(log(n)) time complexity to insert and delete element.
• Offer() and add() methods are used to insert the element in the in the priority queue java program.
• Poll() and remove() is used to delete the element from the queue.
• Element retrieval methods i.e. peek() and element(), that are used to retrieve elements from the head of the queue is constant time i.e. O(1).
• contains(Object)method that is used to check if a particular element is present in the queue, have leaner time complexity i.e. O(n).

Java Collections: Sets

A Set refers to a collection that cannot contain duplicate elements.Set has its implementation in various classes such as HashSet, TreeSetand LinkedHashSet.

HashSet: Java HashSet class creates a collection that use a hash table for storage. Hashset only contain unique elements and it inherits the AbstractSet class and implements Set interface.

Linked Hashset : Java LinkedHashSet class is a Hash table and Linked list implementation of the set interface. It contains only unique elements like HashSet. Linked HashSet also provides all optional set operations and maintains insertion order.

TreeSet : TreeSet class implements the Set interface that uses a tree for storage. The objects of this class are stored in the ascending order.

Below are some of methods of Set:

1. boolean addAll(Collection c) -> Add all the elements in the specified collection to this set.
2. boolean contains(Object o) -> Returns true if the set contains the specified element.
3. boolean isEmpty() -> Returns true if this set contains no elements.
4. boolean remove(Object o) -> Remove the specified element from the set.
5. void add(Object o) -> Add the specified element to the set.
6. void clear() Removes all the elements from the set.
7. Object clone()-> Return a shallow copy of this TreeSet instance.

Applications of Set

• We can use Set interface to maintain data uniqueness.
• Set is used to avoid data redundancy.

Complexity Of add Method :

• HashSet add method have constant time complexity O(1).
• TreeSet add method have constant time complexity O(log(n)).
• LinkedHashSet add method have constant time complexity O(1).

Complexity Of remove Method :

• HashSet remove method have constant time complexity O(1).
• TreeSet remove method have constant time complexity O(log(n)).
• LinkedHashSet remove method have constant time complexity O(1).

HashSet vs TreeSet vs LinkedHashSet:

1. HashSet :

• HashSet Use hashtable to store elements.
• Elements are not stored in sorted order(unsorted).
• add,remove,contain method have constant time complexitiy O(1).

1. TreeSet :

• TreeSet Use RedBlack tree to store elements.
• Elements are stored in sorted order (sorted).
• add, remove, and contains methods has time complexity of O(log (n)).

1. LinkedHashSet :

• LinkedHashSet is between HashSet and TreeSet. It is implemented as a hash table with a slinked list running through it.
• The time complexity of basic methods is O(1).

HashSet has best-performing implementation of Set compare to LinkedHashSet and TreeSet .