How to work with Java Collections?

Introduction

Collections in Java is a framework that provides architecture to store and manipulate data.

👉 (BONUS) Array-based Coding Interview Question at the end!

Hierarchy

Iterable Interface

This interface is the root interface in Collection framework. It is extended by Collection interface. It contains method:

Iterator<E> iterator() which returns iterator over elements in the list.

Collection Interface

This interface extends Iterable interface. Some of the known subinterfaces include interface List, Queue, Deque, Sets and SortedSets. It contains some of the methods below:

• boolean add(Object o)
• boolean addAll(Object o)
• void clear()
• boolean contains(Object o)

Full list of methods supported: https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html

List Interface

This interface is the child interface of Collection and implemented by classes ArrayList, LinkedList, Vector and Stack.

ArrayList Class

This class implements List interface. Some of the properties:

• Can store duplicated element
• Maintains insertion order
• Non-synchronized
• Manipulation is slow because shifting is required if any element is removed from the array

ArrayList vs Array

Array is static because it needs to be initialized with known length. ArrayList is dynamic array and its size increases dynamically as new elements are added. Size of array is obtained using array.length and for arraylist is arraylist.size().

Example of Array Usage:

int arr[] = new int[] {1,2,3};
  
  for (int i=0;i<arr.length;i++) {
   System.out.println("Value is " + arr[i]);
  }

Example of ArrayList usage:

ArrayList<Integer> arrayList = new ArrayList<Integer>();
  
  list1.add(1);
  list1.add(2);
  list1.add(3);
  
  // Method1: Fetching elements from Integer ArrayList using for loop
  for (int i=0;i<arrayList.size();i++) {
   System.out.println("Value is " + arrayList.get(i));
  }
// Method2: Fetching elements from Integer ArrayList using iterator
  Iterator<Integer> it = arrayList.iterator();
  while(it.hasNext()) {
   System.out.println("Value is " + it.next());
  }

NOTE: To retrieve elements using iterator() , you need to use while loop.

LinkedList Class

This class implements List and Deque interface. It uses double linked list to store element, which means each node contains 3 fields, 2 link fields (references to previous and next element) and 1 data field. Fast for inserting and removing elements but slow in get and set elements.

Some of the properties (similar to that of ArrayList):

• Can store duplicated element
• Maintains insertion order
• Non-synchronized
• Manipulation is fast because no shifting is required
• Can be used as list, stack or queue

Example of usage:

LinkedList<String> linkedList = new LinkedList<String>();
  list1.add("test");
  list1.add("test");
  list1.add("test");
  
  Iterator <String> it = linkedList.iterator();
  while(it.hasNext()) {
   System.out.println(it.next());
  }

ArrayList vs LinkedList

• ArrayList can only act as list whereas LinkedList can act as both list and queue.
• ArrayList is better at storing and accessing data whereas LinkedList is better for manipulating data.

Vector Class

This class implements List interface. It is similar to ArrayList except it is synchronized. Some of the properties:

• Can store duplicated element
• Maintains insertion order
• Synchronized

Example of usage:

Vector<Integer> vector = new Vector<Integer>();
  
  list1.add(1);
  list1.add(2);
  list1.add(3);
  
  Iterator<Integer> it = vector.iterator();
  while(it.hasNext()) {
   System.out.println(it.next());
  }

Stack Class

This class is subclass of vector. It implements last-in-first-out order of LIFO. Some of the known methods include:

• Object Push(Object o) —Adding element to the top of stack and return that element
• Object Pop(Object o) — Return and remove element from top of stack
• Object Peek(Object o) — Return element from top of stack without removing it.

Example of usage:

Stack<Integer> stack = new Stack<Integer>();
  System.out.println("Push element: " + stack.push(1));
  System.out.println("Push element: " + stack.push(2));
  System.out.println("Push element: " + stack.push(3));
  System.out.println("Pop element: " + stack.pop());
  System.out.println("Peek element: " + stack.peek());
  
  Iterator<Integer> it = stack.iterator();
  while(it.hasNext()) {
   System.out.println(it.next());
  }

Result:

Push element: 1
Push element: 2
Push element: 3
Pop element: 3
Peek element: 2
1
2

Queue Interface

This interface is the child interface of Collection and is implemented by class PriorityQueue and extended by Deque. This interface maintains first-in-first-out order or FIFO.

PriorityQueue

This class implements Queue interface. It does not allow null values to be stored in the queue.

Some of the known methods:

• Object peak() — Retrieves but does not remove the head of the queue, or return null if queue is empty
• Object poll() — Retrieves and removes the head of the queue, or return null if queue is empty

Example of usage:

PriorityQueue<String> queue = new PriorityQueue<String>();
  queue.add("test1");
  queue.add("test2");
  queue.add("test3");
  System.out.println("Peek: " + queue.peek());
  System.out.println("Poll: " + queue.poll());
  
  Iterator<String> it = queue.iterator();
  while(it.hasNext()) {
   System.out.println(it.next());
  }

Result:

Element: test1
Peek: test1
Poll: test1
test2
test3

Deque Interface

This interface extends Queue interface. Elements can be added or removed from both ends.

ArrayDeque Class

ArrayDeque implements Deque interface. Some of the properties includes not threadsafe and does not permit null elements. This class is likely to be faster than Stack when used as stack and faster than LinkedList when used as queue. Since ArrayDeque implements Deque, it has methods of queue such as peek, pool as well as stack such as push and pop.

Properties include:

• Add or remove elements on both ends
• Do not allow null value
• Not synchronized
• Faster than LinkedList and Stack.

Example usage:

Deque<String> deque = new ArrayDeque<String>();
  deque.add("Test1");
  deque.add("Test2");
  deque.add("Test3");
  Iterator<String> it = deque.iterator();
  while(it.hasNext()) {
   System.out.println(it.next());
  }

Set Interface

This interface is a subinterface of Collection. It represents unordered set of elements that does not contain duplicated elements.

HashSet Class

This class implements Set interface. It permits null element. Elements are stored in hash table after being hash. Hence, if there is a duplicated element, the hash value will overwrite the existing in the hashtable. In additional, the elements are stored in unordered structure.

Properties include:

• Stores element by hashing
• Contains unique elements only
• Allows null value
• Not synchronized
• Does not maintain insertion order

Example usage:

HashSet<String> set = new HashSet<String>();
  set.add("test1");
  set.add("test1");
  set.add("test2");
  set.add("test2");
  set.add("test3");
  set.add("test3");
  
  Iterator<String> it = set.iterator();
  while(it.hasNext()) {
   System.out.println(it.next());
  }

Result:

test2
test3
test1

NOTE: The order of insertion is not maintained.

LinkedHashSet

This class implements Set interface. Similar to HashSet, it does not contain duplicated elements and maintains the order of insertion.

Properties include:

• Stores element by hashing
• Contains unique elements only
• Allows null value
• Not synchronized
• Maintains insertion order

Example of usage:

LinkedHashSet<String> set = new LinkedHashSet<String>();
  set.add("test1");
  set.add("test1");
  set.add("test2");
  set.add("test2");
  set.add("test3");
  set.add("test3");
  
  Iterator<String> it = set.iterator();
  while(it.hasNext()) {
   System.out.println(it.next());
  }

Result:

test1
test2
test3

NOTE: The order of insertion is maintained

SortedSet Interface

This is interface extends Set interface and implementing class includes TreeSet class. It provides total ordering on its element.

TreeSet Class

This class implements SortedSet interface in which elements are sorted and does not contain duplicated elements.

Properties include:

• Contains unique elements only
• Does not allow null value
• Not synchronized
• Stores in ascending order

Example of usage.

TreeSet<String> set = new TreeSet<String>();
  set.add("orange");
  set.add("orange");
  set.add("apple");
  set.add("apple");
  set.add("banana");
  set.add("banana");
  
  Iterator<String> it = set.iterator();
  while(it.hasNext()) {
   System.out.println(it.next());
  }

Result:

apple
banana
orange

NOTE: Elements are sorted

(BONUS) Map Interface

The Map interface is not a subtype of Collection interface. However it is part of the Collections Framework. Map allows to store elements in key and value format.

HashMap Class

This class implements Map interface.

Properties include:

• Contains value based on key
• Contains only unique keys
• May have one null key and many null values
• Not synchronized
• Maintains no order

Example usage:

Map<Integer, String>map=new HashMap<Integer, String>();
map.put(1,"test1");  
map.put(5,"test2");  
map.put(2,"test3");  
map.put(6,"test3");
for(Map.Entry <Integer, String> m: map.entrySet()) {
  System.out.println(m.getKey()+" "+m.getValue());  
}

Result:

1 test1
2 test3
5 test2
6 test3

LinkedHashMap Class

This class extends from HashMap Class. Different from HashMap which does not maintain any order, LinkedHashMap class maintains the insertion order.

Properties include:

• Contains value based on key
• Contains only unique keys
• May have one null key and many null values
• Not synchronized
• Maintains insertion order

Example Usage:

Map<Integer, String>map=new LinkedHashMap<Integer, String>();
map.put(1,"test1");  
map.put(5,"test2");  
map.put(2,"test3");  
map.put(6,"test3");
for(Map.Entry <Integer, String> m: map.entrySet()) {
  System.out.println(m.getKey()+" "+m.getValue());  
}

Result:

1 test1
5 test2
2 test3
6 test3

TreeMap Class

This class implements SortedMap interface.

Properties include:

• Contains value based on key
• Contains only unique keys
• Cannot have a null key and many null values
• Not synchronized
• Maintains ascending order by key

Example Usage

TreeMap<Integer, String>map=new TreeMap<Integer, String>();
map.put(1,"test1");  
map.put(5,"test2");  
map.put(2,"test3");  
map.put(6,"test3");
for(Map.Entry <Integer, String> m: map.entrySet()) {
  System.out.println(m.getKey()+" "+m.getValue());  
}

Results:

1 test1
2 test3
5 test2
6 test3

(BONUS) HashTable Class

This legacy class inherits Dictionary class and implements Map interface. Similar to HashMap, both stores data in the form of key and value and uses hashing to store unique key. However some differences are:

• HashTable is synchronized
• HashTable does not allow null key or value
• HashTable is slow

(BONUS) Array-Based Coding Interview Questions

How to find missing number in integer array?

The secret is using an algorithm to get the sum of series highlighted in bold below

public class TestFindMIssingNumberInArray {
public static void main(String[] args) {
  printMissingNumber(new int[] {1,2,3,5,6}, 6);
 }
 
 private static void printMissingNumber(int[] input, int totalCount) {
  int expectedSum = totalCount * (totalCount+1)/2;
  int actualSum = 0;
  for(int i=0;i<input.length;i++) {
   actualSum += input[i];
  }
  System.out.println("Missing number is " + (expectedSum - actualSum));
 }
}

How to find duplicated numbers in integer array?

There are 2 solutions to it. If the question does not allow solving using java.util.* packages, then refer to removeDuplicateBruteForce. The removeDuplicateCollection involves utilizing the properties of Set interface which does not allow duplicates. Use TreeSet to display result in sorted and ascending order.

import java.util.Arrays;
import java.util.Iterator;
import java.util.TreeSet;
public class TestFIndDuplicatesInArray {
 public static void main(String[] args) {
  removeDuplicateBruteForce(new int[] {1,1,1,2,2,2,3,3,3,3}); //sorted
  removeDuplicateCollection(new int[] {1,2,3,4,6,5,7,7,9,8}); //unsorted
 }
 
 
 public static void removeDuplicateBruteForce(int[] input) {
  Arrays.sort(input);
  
  int[] result = new int[input.length];
  int duplicateCount = 0;
  int previous = input[0];
  result[0] = previous;
  
  for(int i=0;i<input.length;i++) {
   if(input[i] != previous) {
    result[i] = input[i];
    previous = result[i];
   } else {
    duplicateCount++;
   }
  }
  
  int count = 0;
  int[] finalResult = new int[input.length - duplicateCount + 1];
  for(int i=0;i<result.length;i++) {
   if(result[i] != 0) {
    finalResult[count] = result[i];
    count++;
   } 
  }
  System.out.println(Arrays.toString(finalResult));
 }
 
 public static void removeDuplicateCollection(int[] input) {
  
  TreeSet<Integer> set = new TreeSet<Integer>();
  
  for(int i: input) {
   set.add(i);
  }
  
  int[] output = new int[set.size()];
  int count = 0;
  
  Iterator<Integer> it = set.iterator();
  while(it.hasNext()) {
   output[count] = it.next();
   count++;
  }
  
  System.out.println(Arrays.toString(output));
  
 }
}

How to find all pairs of an integer array who sum is equal to a given number?

There are 2 ways of solving it. One is using brute force and the other is using HashSet or LinkedHashSet. Using Set interface has advantages that any duplicates are remove and we get to use Collection method of contains() to quickly find if the set contains the number that we want. It is equivalent to a for loop block but only with 1 line of code.

package com.example;
import java.util.HashSet;
public class TestSumPairArray {
public static void main(String[] args) {
  pairSumBruteForce(new int[] {2, 4, 7, 5, 9, 10, -1}, 9);
  System.out.println(".....");
  pairSumHashSet(new int[] {2, 4, 7, 5, 9, 10, -1}, 9);
 }
 
 public static void pairSumBruteForce(int[] number, int sum) {
  for(int i=0;i<number.length;i++) {
   int first = number[i];
   for(int j=i+1;j<number.length;j++) {
    int second = number[j];
    if(first+second==sum) {
     System.out.printf("(%d,%d) %n", first, second);
    }
   }
  }
 }
 
 public static void pairSumHashSet(int[] number, int sum) {
  HashSet<Integer> set = new HashSet<Integer>();
  for(int value: number) {
   int target = sum - value;
   if(!set.contains(target)) {
    set.add(value);
   } else {
    System.out.printf("(%d,%d) %n", value, target);
   }
  }
  
 }
}