Collections
1. Why do we need Collections in Java?
Arrays are not dynamic. Once an array of a particular size is declared, the size cannot be modified. To add a new element to the array, a new array has to be created with bigger size and all the elements from the old array copied to new array.
Collections are used in situations where data is dynamic. Collections allow adding an element, deleting an element and host of other operations. There are a number of Collections in Java allowing to choose the right Collection for the right context.
2. What are the important interfaces in the Collection Hierarchy?
The most important interfaces and their relationships are below:-
interface Collection < E > extends Iterable < E > {
}
// Unique things only - Does not allow duplication.
// If obj1.equals(obj2) then only one of them can be in the Set.
interface Set < E > extends Collection < E > {
}
// LIST OF THINGS
// Cares about which position each object is in
// Elements can be added in by specifying position - where should it be added in
// If element is added without specifying position - it is added at the end
interface List < E > extends Collection < E > {
}
// Arranged in order of processing - A to-do list for example
// Queue interface extends Collection. So, it supports all Collection Methods.
interface Queue < E > extends Collection < E > {
}
// A,C,A,C,E,C,M,D,H,A => {("A",5),("C",2)}
// Key - Value Pair {["key1",value1],["key2",value2],["key3",value3]}
// Things with unique identifier
interface Map < K, V > {
}
3. What are the important methods that are declared in the Collection Interface?
Most important methods declared in the collection interface are the methods to add and remove an element. add method allows adding an element to a collection and delete method allows deleting an element from a collection.
size() methods returns number of elements in the collection. Other important methods defined as part of collection interface are shown below.
interface Collection < E > extends Iterable < E > {
boolean add(E paramE);boolean remove(Object paramObject);
int size();boolean isEmpty();void clear();
boolean contains(Object paramObject);
boolean containsAll(Collection << ? > paramCollection);
boolean addAll(Collection << ? extends E > paramCollection);
boolean removeAll(Collection << ? > paramCollection);
boolean retainAll(Collection << ? > paramCollection);
Iterator < E > iterator();
//A NUMBER OF OTHER METHODS AS WELL..
}
4. Can you explain briefly about the List Interface?
List interface extends Collection interface. So, it contains all methods defined in the Collection interface. In addition, List interface allows operation specifying the position of the element in the Collection.
Most important thing to remember about a List interface – any implementation of the List interface would maintain the insertion order. When an element A is inserted into a List (without specifying position) and then another element B is inserted, A is stored before B in the List. When a new element is inserted without specifying a position, it is inserted at the end of the list of elements.
However, We can also use the void add(int position, E paramE); method to insert an element at a specific position.
Listed below are some of the important methods in the List interface (other than those inherited from Collection interface):
interface List < E > extends Collection < E > {
boolean addAll(int paramInt, Collection << ? extends E > paramCollection);
E get(int paramInt);
E set(int paramInt, E paramE);
void add(int paramInt, E paramE);
E remove(int paramInt);
int indexOf(Object paramObject);
int lastIndexOf(Object paramObject);
ListIterator < E > listIterator();
ListIterator < E > listIterator(int paramInt);
List < E > subList(int paramInt1, int paramInt2);
}
5. Explain about ArrayList with an example?
ArrayList implements the list interface. So, ArrayList stores the elements in insertion order (by default). Element’s can be inserted into and removed from ArrayList based on their position.
Let’s look at how to instantiate an ArrayList of integers.
List < Integer > integers = new ArrayList < Integer > ();
Code like below is permitted because of auto boxing. 5 is auto boxed into Integer object and stored in ArrayList.
integers.add(5); //new Integer(5)
Add method (by default) adds the element at the end of the list.
6. Explain about ArrayList with an example?
ArrayList can have duplicates (since List can have duplicates).
List <String> arraylist = new ArrayList <String>();
//adds at the end of list
arraylist.add("Sachin"); //[Sachin]
//adds at the end of list
arraylist.add("Dravid"); //[Sachin, Dravid]
//adds at the index 0
arraylist.add(0, "Ganguly"); //[Ganguly, Sachin, Dravid]
//List allows duplicates - Sachin is present in the list twice
arraylist.add("Sachin"); // [Ganguly, Sachin, Dravid, Sachin]
System.out.println(arraylist.size()); //4
System.out.println(arraylist.contains("Dravid")); //true
7. How do you iterate around an ArrayList using Iterator?
Example below shows how to iterate around an ArrayList.
Iterator < String > arraylistIterator = arraylist.iterator();
while (arraylistIterator.hasNext()) {
String str = arraylistIterator.next();
System.out.println(str); //Prints the 4 names in the list on separate lines.
}
8. How do you sort an ArrayList?
Example below shows how to sort an ArrayList. It uses the Collections.sort method.
List < String > numbers = new ArrayList < String > ();
numbers.add("one");
numbers.add("two");
numbers.add("three");
numbers.add("four");
System.out.println(numbers); //[one, two, three, four]
//Strings - By Default - are sorted alphabetically
Collections.sort(numbers);
System.out.println(numbers); //[four, one, three, two]
9. How do you sort elements in an ArrayList using Comparable interface?
class Cricketer implements Comparable < Cricketer > {
int runs;String name;
public Cricketer(String name, int runs) {
super();
this.name = name;
this.runs = runs;
}
@Override public String toString() {
return name + " " + runs;
}
@Override public int compareTo(Cricketer that) {
if (this.runs > that.runs) {
return 1;
}
if (this.runs < that.runs) {
return -1;
}
return 0;
}
}
Let’s now try to sort a list containing objects of Cricketer class.
List < Cricketer > cricketers = new ArrayList < Cricketer > ();
cricketers.add(new Cricketer("Bradman", 9996));
cricketers.add(new Cricketer("Sachin", 14000));
cricketers.add(new Cricketer("Dravid", 12000));
cricketers.add(new Cricketer("Ponting", 11000));
System.out.println(cricketers);
//[Bradman 9996, Sachin 14000, Dravid 12000, Ponting 11000]
Now let’s try to sort the cricketers.
Collections.sort(cricketers); System.out.println(cricketers); //[Bradman 9996, Ponting 11000, Dravid 12000, Sachin 14000]
10. How do you sort elements in an ArrayList using Comparator interface?
Other option to sort collections is by creating a separate class which implements Comparator interface. Example below:
class DescendingSorter implements Comparator < Cricketer > {
//compareTo returns
//-1 if cricketer1 < cricketer2
// 1 if cricketer1 > cricketer2
// 0 if cricketer1 = cricketer2
//Since we want to sort in descending order,
//we should return -1 when runs are more
@Override public int compare(Cricketer cricketer1, Cricketer cricketer2) {
if (cricketer1.runs > cricketer2.runs) {
return -1;
}
if (cricketer1.runs < cricketer2.runs) {
return 1;
}
return 0;
}
}
Let’s now try to sort the previous defined collection:
Collections.sort(cricketers, new DescendingSorter()); System.out.println(cricketers); //[Sachin 14000, Dravid 12000, Ponting 11000, Bradman 9996]
11. What is Vector class? How is it different from an ArrayList?
class Vector /* implements List<E>, RandomAccess */ {
// Thread Safe - Synchronized Methods
// implements RandomAccess, a marker interface, meaning it support fast
// almost constant time - access
}
Vector has the same operations as an ArrayList. However, all methods in Vector are synchronized. So, we can use Vector if we share a list between two threads and we would want to them synchronized.
12. What is LinkedList? What interfaces does it implement? How is it different from an ArrayList?
class LinkedList /* implements List<E>, Queue */ {
// Elements are doubly linked - forward and backword - to one another
// Ideal choice to implement Stack or Queue
// Iteration is slower than ArrayList
// Fast Insertion and Deletion
// Implements Queue interface. Supports methods like peek(), poll()
// and remove()
}
Linked List extends List and Queue.Other than operations exposed by the Queue interface, LinkedList has the same operations as an ArrayList. However, the underlying implementation of Linked List is different from that of an ArrayList.
ArrayList uses an Array kind of structure to store elements. So, inserting and deleting from an ArrayList are expensive operations. However, search of an ArrayList is faster than LinkedList.
LinkedList uses a linked representation. Each object holds a link to the next element. Hence, insertion and deletion are faster than ArrayList. But searching is slower.
13. Can you briefly explain about the Set Interface?
There are hardly any new methods in the Set interface other than those in the Collection interface. The major difference is that Set interface does not allow duplication. Set interface represents a collection that contains no duplicate elements.
// Unique things only - Does not allow duplication.
// If obj1.equals(obj2) then only one of them can be in the Set.
interface Set < E > extends Collection < E > {
}
14. What are the important interfaces related to the Set Interface?
// Unique things only - Does not allow duplication.
// If obj1.equals(obj2) then only one of them can be in the Set
interface Set < E > extends Collection < E > {}
// Main difference between Set and SortedSet is - an implementation of
// SortedSet interface maintains its elements in a sorted order.
// Set interface does not guarantee any Order.
interface SortedSet < E > extends Set < E > {
SortedSet < E > subSet(E fromElement, E toElement);
SortedSet < E > headSet(E toElement);
SortedSet < E > tailSet(E fromElement);
E first();
E last();
}
//A SortedSet extended with navigation methods reporting closest matches for
//given search targets.
interface NavigableSet < E > extends SortedSet < E > {
E lower(E e);
E floor(E e);
E ceiling(E e);
E higher(E e);
E pollFirst();
E pollLast();
}
15. What is the difference between Set and SortedSet interfaces?
SortedSet Interface extends the Set Interface. Both Set and SortedSet do not allow duplicate elements.
Main difference between Set and SortedSet is – an implementation of SortedSet interface maintains its elements in a sorted order. Set interface does not guarantee any Order. For example, If elements 4,5,3 are inserted into an implementation of Set interface, it might store the elements in any order. However, if we use SortedSet, the elements are sorted. The SortedSet implementation would give an output 3,4,5.
16. Can you give examples of classes that implement the Set Interface?
HashSet, LinkedHashSet and TreeSet implement the Set interface.
// Order of Insertion : A, X , B
// Possible Order of Storing : X, A ,B
class HashSet /* implements Set */{
// unordered, unsorted - iterates in random order
// uses hashCode()
}
// Order of Insertion :A, X, B
// Order of Storing : A, X, B
class LinkedHashSet /* implements Set */{
// ordered - iterates in order of insertion
// unsorted
// uses hashCode()
}
// Order of Insertion :A,C,B
// Order of Storing : A,B,C
class TreeSet /* implements Set,NavigableSet */{
// 3,5,7
// sorted - natural order
// implements NavigableSet
}
17. What is a HashSet?
HashSet implements set interface. So, HashSet does not allow duplicates. However, HashSet does not support ordering. The order in which elements are inserted is not maintained.
Example 1
Set < String > hashset = new HashSet < String > ();
hashset.add("Sachin");
System.out.println(hashset); //[Sachin]
hashset.add("Dravid");
System.out.println(hashset); //[Sachin, Dravid]
Let’s try to add Sachin to the Set now. Sachin is Duplicate. So will not be added. returns false.
hashset.add("Sachin"); //returns false since element is not added
System.out.println(hashset); //[Sachin, Dravid]
18. What is a LinkedHashSet? How is different from a HashSet?
LinkedHashSet implements set interface and exposes similar operations to a HashSet. Difference is that LinkedHashSet maintains insertion order. When we iterate a LinkedHashSet, we would get the elements back in the order in which they were inserted.
19. What is a TreeSet? How is different from a HashSet?
TreeSet implements Set, SortedSet and NavigableSet interfaces.TreeSet is similar to HashSet except that it stores element’s in Sorted Order.
Set < String > treeSet = new TreeSet < String > ();
treeSet.add("Sachin");
System.out.println(treeSet); //[Sachin]
Notice that the list is sorted after inserting Dravid.
//Alphabetical order
treeSet.add("Dravid");
System.out.println(treeSet); //[Dravid, Sachin]
Notice that the list is sorted after inserting Ganguly.
//Sachin is Duplicate. So will not be added. returns false.
treeSet.add("Sachin"); //returns false since element is not added
System.out.println(treeSet); //[Dravid, Ganguly, Sachin]
20. Can you give examples of implementations of NavigableSet?
TreeSet implements this interface. Let’s look at an example with TreeSet. Note that elements in TreeSet are sorted.
TreeSet < Integer > numbersTreeSet = new TreeSet < Integer > (); numbersTreeSet.add(55); numbersTreeSet.add(25); numbersTreeSet.add(35); numbersTreeSet.add(5); numbersTreeSet.add(45);
NavigableSet interface has following methods.
Lower method finds the highest element lower than specified element. Floor method finds the highest element lower than or equal to specified element. Corresponding methods for finding lowest number higher than specified element are higher and ceiling. A few examples using the Set created earlier below.
//Find the highest number which is lower than 25 System.out.println(numbersTreeSet.lower(25)); //5 //Find the highest number which is lower than or equal to 25 System.out.println(numbersTreeSet.floor(25)); //25 //Find the lowest number higher than 25 System.out.println(numbersTreeSet.higher(25)); //35 //Find the lowest number higher than or equal to 25 System.out.println(numbersTreeSet.ceiling(25)); //25
21. Explain briefly about Queue Interface?
Queue Interface extends Collection interface. Queue Interface is typically used for implementation holding elements in order for some processing.
Queue interface offers methods peek() and poll() which get the element at head of the queue. The difference is that poll() method removes the head from queue also. peek() would keep head of the queue unchanged.
interface Queue < E > extends Collection < E > {
//Inserts the specified element into this queue
//Throws exception in case of failure
boolean add(E paramE);
//Inserts the specified element into this queue
//Returns false in case of failure
boolean offer(E paramE);
//Retrieves and removes the head of this queue.
//Throws Exception if Queue is empty
E remove();
//Retrieves and removes the head of this queue.
//returns null if Queue is empty
E poll();
E element();
E peek();
}
22. What are the important interfaces related to the Queue Interface?
Two important interfaces are Deque and BlockingQueue.
23. Explain about the Deque interface?
//A linear collection that supports element insertion and removal at both ends
interface Deque < E > extends Queue < E > {
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
}
24. Explain the BlockingQueue interface?
// A Queue that additionally supports operations that wait for
// the queue to become non-empty when retrieving an
// element, and wait for space to become available in the queue when
// storing an element.
interface BlockingQueue < E > extends Queue < E > {
// Same as in Queue Interface
// Inserts the specified element into queue IMMEDIATELY
// Throws exception in case of failure
boolean add(E e);
// Same as in Queue Interface
// Inserts the specified element into queue IMMEDIATELY
// Returns false in case of failure
boolean offer(E e); // Same as in Queue Interface
// Inserts the specified element into this queue, waiting
// if necessary for space to become available.
void put(E e) throws InterruptedException;
// waiting up to the specified wait time
boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException;
// waits until element becomes available
E take() throws InterruptedException;
// waits for specified time and returns null if time expires
E poll(long timeout, TimeUnit unit) throws InterruptedException;
int remainingCapacity();
boolean remove(Object o);
public boolean contains(Object o);
int drainTo(Collection << ? super E > c);
int drainTo(Collection << ? super E > c, int maxElements);
}
25. What is a PriorityQueue?
PriorityQueue implements the Queue interface.
//The elements of the priority queue are ordered according to their natural ordering
class PriorityQueue /* implements Queue */ {
// sorted - natural order
}
//Using default constructor - uses natural ordering of numbers //Smaller numbers have higher priority PriorityQueue < Integer > priorityQueue = new PriorityQueue < Integer > ();
Adding an element into priority queue – offer method
priorityQueue.offer(24); priorityQueue.offer(15); priorityQueue.offer(9); priorityQueue.offer(45); System.out.println(priorityQueue); //[9, 24, 15, 45]
Peek method examples
//peek method get the element with highest priority. System.out.println(priorityQueue.peek()); //9 //peek method does not change the queue System.out.println(priorityQueue); //[9, 24, 15, 45] //poll method gets the element with highest priority. System.out.println(priorityQueue.poll()); //9 //peek method removes the highest priority element from the queue. System.out.println(priorityQueue); //[24, 15, 45]
//This comparator gives high priority to the biggest number.
Comparator reverseComparator = new Comparator < Integer > () {
public int compare(Integer paramT1, Integer paramT2) {
return paramT2 - paramT1;
}
};
26. Can you give example implementations of the BlockingQueue interface?
class ArrayBlockingQueue /*implements BlockingQueue*/ {
//uses Array - optionally-bounded
}
class LinkedBlockingQueue /*implements BlockingQueue*/ {
//uses Linked List - optionally-bounded
//Linked queues typically have higher throughput than array-based queues but
//less predictable performance in most concurrent applications.
}
27. Can you briefly explain about the Map Interface?
First and foremost, Map interface does not extend Collection interface. So, it does not inherit any of the methods from the Collection interface.
A Map interface supports Collections that use a key value pair. A key-value pair is a set of linked data items: a key, which is a unique identifier for some item of data, and the value, which is either the data or a pointer to the data. Key-value pairs are used in lookup tables, hash tables and configuration files. A key value pair in a Map interface is called an Entry.
Put method allows to add a key, value pair to the Map.
V put(K paramK, V paramV);
Get method allows to get a value from the Map based on the key.
V get(Object paramObject);
Other important methods in Map Interface are shown below:
interface Map < K, V > {
int size();
boolean isEmpty();
boolean containsKey(Object paramObject);
boolean containsValue(Object paramObject);
V get(Object paramObject);
V put(K paramK, V paramV);
V remove(Object paramObject);
void putAll(Map << ? extends K, ? extends V > paramMap);
void clear();
Set < K > keySet();
Collection < V > values();
Set < Entry < K,V >> entrySet();
boolean equals(Object paramObject);int hashCode();
public static abstract interface Entry < K,V > {
K getKey();
V getValue();
V setValue(V paramV);
boolean equals(Object paramObject);
int hashCode();
}
}
28. What is difference between Map and SortedMap?
SortedMap interface extends the Map interface. In addition, an implementation of SortedMap interface maintains keys in a sorted order.
Methods are available in the interface to get a ranges of values based on their keys.
public interface SortedMap < K, V > extends Map < K, V > {
Comparator << ? super K > comparator();
SortedMap < K, V > subMap(K fromKey, K toKey);
SortedMap < K, V > headMap(K toKey);
SortedMap < K, V > tailMap(K fromKey);
K firstKey();
K lastKey();
}
29. What is a HashMap?
HashMap implements Map interface – there by supporting key value pairs. Let’s look at an example.
HashMap Example
Map < String, Cricketer > hashmap = new HashMap < String, Cricketer > ();
hashmap.put("sachin", new Cricketer("Sachin", 14000));
hashmap.put("dravid", new Cricketer("Dravid", 12000));
hashmap.put("ponting", new Cricketer("Ponting", 11500));
hashmap.put("bradman", new Cricketer("Bradman", 9996));
30. What are the different methods in a Hash Map?
get method gets the value of the matching key.
System.out.println(hashmap.get("ponting")); // Ponting 11500
//if key is not found, returns null.
System.out.println(hashmap.get("lara")); // null
If existing key is reused, it would replace existing value with the new value passed in.
// In the example below, an entry with key "ponting" is already present.
// Runs are updated to 11800.
hashmap.put("ponting", new Cricketer("Ponting", 11800));
// gets the recently updated value
System.out.println(hashmap.get("ponting")); //Ponting 11800
31. What is a TreeMap? How is different from a HashMap?
TreeMap is similar to HashMap except that it stores keys in sorted order. It implements NavigableMap interface and SortedMap interfaces along with the Map interface.
Map < String, Cricketer > treemap = new TreeMap < String, Cricketer > ();
treemap.put("sachin", new Cricketer("Sachin", 14000));
System.out.println(treemap);
// {sachin=Sachin 14000}
We will now insert a Cricketer with key dravid. In sorted order,dravid comes before sachin. So, the value with key dravid is inserted at the start of the Map.
treemap.put("dravid", new Cricketer("Dravid", 12000));
System.out.println(treemap);
//{dravid=Dravid 12000, sachin=Sachin 14000}
We will now insert a Cricketer with key ponting. In sorted order, ponting fits in between dravid and sachin.
treemap.put("ponting", new Cricketer("Ponting", 11500));
System.out.println(treemap);
// {dravid=Dravid 12000, ponting=Ponting 11500, sachin=Sachin 14000}
treemap.put("bradman", new Cricketer("Bradman", 9996));
System.out.println(treemap);
// {bradman=Bradman 9996, dravid=Dravid 12000, ponting=Ponting 11500, sachin=Sachin 14000}
32. Can you give an example of implementation of NavigableMap Interface?
TreeMap is a good example of a NavigableMap interface implementation. Note that keys in TreeMap are sorted.
NavigableMap is a SortedMap extended with navigation methods reporting closest matches for given search targets.
interface NavigableMap < K, V > extends SortedMap < K, V > {
Map.Entry < K, V > lowerEntry(K key);
K lowerKey(K key);
Map.Entry < K,V > floorEntry(K key);
K floorKey(K key);
Map.Entry < K, V > ceilingEntry(K key);
K ceilingKey(K key);
Map.Entry < K, V > higherEntry(K key);
K higherKey(K key);
Map.Entry < K, V > firstEntry();
Map.Entry < K, V > lastEntry();
Map.Entry < K, V > pollFirstEntry();
Map.Entry < K, V > pollLastEntry();
NavigableMap < K, V > descendingMap();
NavigableSet < K > navigableKeySet();
NavigableSet < K > descendingKeySet();
}
Example Program
TreeMap < Integer, Cricketer > numbersTreeMap = new TreeMap < Integer, Cricketer > ();
numbersTreeMap.put(55, new Cricketer("Sachin", 14000));
numbersTreeMap.put(25, new Cricketer("Dravid", 12000));
numbersTreeMap.put(35, new Cricketer("Ponting", 12000));
numbersTreeMap.put(5, new Cricketer("Bradman", 9996));
numbersTreeMap.put(45, new Cricketer("Lara", 10000));
lowerKey method finds the highest key lower than specified key. floorKey method finds the highest key lower than or equal to specified key. Corresponding methods for finding lowest key higher than specified key are higher and ceiling. A few examples using the Map created earlier below.
// Find the highest key which is lower than 25 System.out.println(numbersTreeMap.lowerKey(25)); / /5 // Find the highest key which is lower than or equal to 25 System.out.println(numbersTreeMap.floorKey(25)); // 25 // Find the lowest key higher than 25 System.out.println(numbersTreeMap.higherKey(25)); // 35 // Find the lowest key higher than or equal to 25 System.out.println(numbersTreeMap.ceilingKey(25)); // 25
33. What are the static methods present in the Collections class?
• static int binarySearch(List, key)
o Can be used only on sorted list
• static int binarySearch(List, key, Comparator)
• static void reverse(List) o Reverse the order of elements in a List.
• static Comparator reverseOrder();
o Return a Comparator that sorts the reverse of the collection current sort sequence.
• static void sort(List) • static void sort(List, Comparator)
