Collections in Java
In this blog, we are going to talk about collections in terms of their usage in coding/implementation. This is quite handy for a competitive programmer and we are not going to explore internal details in terms of interfaces and other stuff. This would also be helpful for people who are good with some other language say C++, python etc and wanted to have a look of implementation of some data structures in Java…
What are collections in Java…
The collections framework in Java is similar to that of STL in C++. This framework contains all the implementations of data structures ranging from LinkedList, Queue, Stack. We will also discuss Map in this blog which is one of the most widely used data structure though it does not implement the collection framework and one cannot miss this Map data structure when coding for interviews.
Let us first explore some of the general methods available in the Collection interface which means these methods apply for List, Set. Queue, Stack only and not Maps.
size() — returns the number of elements in the collection
isEmpty() — returns true if collection is empty i.e size==0
add() — add an element to the collection
remove() -removes an element from the collection
addAll(collection) — adds all element from the passed collection to the collection
removeAll(collection) — removes all elements in the passed collection from the collection
contains()- check if specific is present in the collection
clear() — removes all the elements from the collection
Implementation of List
We go for the list so as to avoid the problem of a fixed size which we face in arrays. We can implement the List in Java in two ways the ArrayList, LinkedList.
ArrayList is the most common usage of List and it is actually implemented in terms of dynamic arrays inside which means first some initial space is allocated to it when it runs out of space it doubles its existing space and this whenever we add more and more elements to the list.
To declare an ArrayList you can use like this with List interface:
List<Objecttype> listname = new ArrayList<>();
or
ArrayList<Objecttype> listname = new ArrayList<>();
Here ObjectType can be any class like our own custom created class type or Standard Types like String,Integer,Double etc.
To add elements to the list you can use add function and delete elements you can use remove.
One more thing we often use is the iteration over the entire list .For that you can use iterator or simply you can use the foreach loop.It is because all the collections implement the iterator interface.To use the for each loop we can use like this
for(Object o : collectionname){
//operation with Object o
}
For example:
for(String s : names) {
System.out.prinln(s);
}
List with LinkedList Implementation
This Implementation of List is carried out entirely using the LinkedList.To implement we can declare like this.
List<Objecttype> listname=new LinkedList<>();
We can use add() and remove() methods to add and delete elements from the list respectively.
Sets
Sets are data structures similar to that of list with the difference being there are no duplicates in the set.There is also a sorted version of the set where the order is determined by the compare method or you can use some custom Comparator.
To implement to normal Set we can use HashSet implementation of List and can be declared as follows:
Set<Objecttype> setname=new HashSet<>();
Eg: Set<Integer> myset=new HashSet<>();
We can use standard add and remove elements to perform operations on the set.
Note: The sameness of the elements is compared with something called as hashcode. So elements with the same hashcode are considered as equal.
To implement the sorted version of Set we can use TreeSet which is inbuilt implemented using tree implementation underneath.
SortedSet<Objecttype> setname=new TreeSet<>();
We can use standard add and remove elements to perform operations on the list.
Queue
Queues are data structures which following the First In First Out(FIFO) principle. There are various implementations of the Queue the famous being the ArrayDeque Implementation with Queue interface.
Queue<Objecttype> queuename = new ArrayDeque<>();
We can use our standard add and remove methods to perform operations but they may throw exceptions when the operation is prohibited like removing form an empty queue.So that is why they are not mostly used operations so the most common methods are:
offer()- adds an element to queue and returns null in case it is full.
poll()- removes an element from the queue and returns null if not possible
There is also the priority queue implementation of Queue when you want to store elements with some priority defined by your Comparator.
Queue<Objecttype> queuename = new PriorityQueue<>();
Stack
The most common implementation of the stack is using the Deque interface .
Deque<Objecttype> stackname= new ArrayDequeue<>();
We can use the push() and pop() functions to implement the operations of the stack.
Maps
Maps are important data structures in programming and they are sometimes referred to as dictionaries in some languages.They are Key,Value pair data structures.All the Keys are unique and are immutable in nature.
HashMap is the most common implementation of the Map.
Map<Keytype,Valuetype> mapname= new HashMap<>();
Eg: Map<Integer,String> m = new HashMap<>();
As it is discussed these do not implement the collection interface so the above discussed standard methods like add, remove will not work on maps.
Methods on Map are as follows:
put(Key, Value) — Adds an element into the map
remove(Key) — Removes element with that particular Key
replace(Key)- Replace the Value of the given Key
containsKey(Key)- checks whether the given key is present in map
get(Key) — returns the value of given Key
Also, note that as discussed we cannot iterate over maps as it does not implement Iterator interface.
To iterate over Map can use entrySet() method available. Map.entrySet() method returns a collection-view(Set<Map.Entry<K, V>>) of the mappings contained in this map. So we can iterate over key-value pair using getKey() and getValue() methods of Map.Entry<K, V>.
Usage is as follows :
Set<Map.Entry<Keytype,Valuetype>> setname= mapobject.entrySet();
Now we can use foreach loop on the obtained set
for (Map.Entry<Keytype,ValueType> entry : setname){
System.out.println("Key = " + entry.getKey() +
", Value = " + entry.getValue());
}
You can also read about other ways here.
Sorted Version of Map
You can also implement the sorted version of the map as TreeMap which is built using the Red-Black tree data structure.
SortedMap<Key, Value> mapname= new TreeMap<>();
You can use standard methods of the map to perform operations.
Some standard algorithms of Collection interface
sort() — used for sorting elements and you can use custom Comparator for defining order
shuffle() — rearrange the elements in random order in a collection
rotate(collections, distance) — It is used to rotate the elements present in the specified list of Collection by a given distance
The End
We come to end of the blog, we have discussed the overview of the implementations of the various data structures in java there are many more methods available in each of the collections and there are various other methods available in sorted versions like the tail() , head(), sub() you can look online/documentation for the same.
Please feel free to post any suggestions and recommendations for the blogs you want to see.
