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
- Need contiguous memory to store elements
- Only homogenous type data can be stored
- It is compulsory to known the number of elements that we would inserting to array
- 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:
- ArrayList
- LinkedList
- 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 :
- 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:
- boolean add(object) -> Inserts the specified element into the queue and returns true if it is a success.
- boolean offer(object)-> Inserts the specified element into this queue.
- Object remove() -> Retrieves and removes the head of the queue.
- Object poll()-> Retrieves and removes the head of the queue, or returns null if the queue is empty.
- Object element() ->Retrieves, but does not remove the head of the queue.
- 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:
- boolean addAll(Collection c) -> Add all the elements in the specified collection to this set.
- boolean contains(Object o) -> Returns true if the set contains the specified element.
- boolean isEmpty() -> Returns true if this set contains no elements.
- boolean remove(Object o) -> Remove the specified element from the set.
- void add(Object o) -> Add the specified element to the set.
- void clear() Removes all the elements from the set.
- 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:
- 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).
- 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)).
- 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 .