Collections

Question 1

What is the collection framework hierarchy, and how do they relate to each other>

Answer 1

Question 2

What is List interface in collection framework?

Answer 2

The collection framework provides a core set of interfaces to define different collection behaviors. One of the core interfaces is the List interface. A List is a collection where its elements are ordered in a sequence. Lists allow us to have duplicate elements and fine-grain control over where elements are inserted in the sequence. Like arrays, the position of a List is known as the index and is 0 based. Unlike arrays, which have a static size, Lists are dynamically sized.

The collection framework provides many List implementations but we’ll focus on the ArrayList and LinkedList. The ArrayList is the overall preferred implementation for most use cases but the LinkedList performs better than an ArrayList if your program mostly inserts and deletes elements.

List<Integer> intList = new ArrayList<>(); // Empty `List`
intList.add(4); // 4
intList.add(6); // 4, 6
intList.add(3); // 4, 6, 3
intList.set(1, 3); // 4, 3, 3
 
int a = intList.get(2); // a = 3
int b = intList.indexOf(3); // b = 1
 
List<Integer> subIntList = intList.subList(1,3); // subIntList -> 3, 3

Question 3

How can we iterate through a list?

Answer 3

for (Integer number: intList) {
  System.out.println(number);  
}

Question 4

What are the Set interface and its implementations?

Answer 4

Another core interface provided by the collection framework is the Set interface. A Set is a collection of unique elements and all of its methods ensure this stays true.

• The HashSet implementation has the best performance when retrieving or inserting elements but cannot guarantee any ordering among them.
• The TreeSet implementation does not perform as well on insertion and deletion of elements but does keep the elements stored in order based on their values (this can be customized).
• The LinkedHashSet implementation has a slightly slower performance on insertion and deletion of elements than a HashSet but keeps elements in insertion order.

Question 5

How do we create and use HashSet?`

Answer 5

Set<Integer> intSet = new HashSet<>();  // Empty set
intSet.add(6);  // true - 6  
intSet.add(0);  //  true - 0, 6 (no guaranteed ordering)
intSet.add(6);  //  false - 0, 6 (no change, no guaranteed ordering)
 
boolean isNineInSet = intSet.contains(9);  // false
boolean isZeroInSet = intSet.contains(0);  // true

Question 6

What is a queue interface?

Answer 6

The Queue core interface in the collection framework, is a collection that stores elements that can be accessed at some later point to process (like waiting in line at the bank teller). A Queue accesses elements in a (usually) First In First Out (FIFO) manner where elements are inserted at the tail (back) of the collection and removed from the head (front).

Question 7

What are the methods of queue interface?

Answer 7

A Queue has two types of access methods for inserting, removing, and getting but not removing the head of the Queue.

The following methods throw an exception when:

add() - there is no space for the element
remove() - there are no elements to remove
element() - there are no elements to get

The following methods return a special value:

offer() - false there is no space for the element
poll() - null there are no elements to remove
peek() - null there are no elements to get

The methods that return a special value should be used when working with a statically sized Queue and the exception throwing methods when using a dynamic Queue.

Question 8

What are the important implementations of queue interface?

Answer 8

LinkedList and PriorityQueue.

LinkedList be used as a List implementation and it’s also perfect when needing a basic Queue implementation. Being able to use a LinkedList as both a List and Queue implementation is a perfect example of the compatibility within the collection framework.

The PriorityQueue ensures the top element is the smallest relative to the data type’s natural ordering (or some custom comparison algorithm you provide).

Question 9

How do we use queues?

Answer 9

Queue<String> stringQueue = new LinkedList<>();
stringQueue.add("Mike"); // true - state of queue -> "Mike"
stringQueue.offer("Jeff"); // true - state of queue -> "Mike", "Jeff" 
 
String a = stringQueue.remove() // Returns "Mike" - state of queue -> 1
String b = stringQueue.poll() // Returns "Jeff" - state of queue -> empty
String c = stringQueue.peek() // Returns null
String d = stringQueue.element() // Throws NoSuchElementException

Question 10

How do we iterate over queues?

Answer 10

// Assuming `stringQueue` has elements -> "Mike", "Jack", "John"
for (String name: stringQueue) {
  System.out.println(name);
}
// OUTPUT TERMINAL: "Mike", "Jack", "John"

One thing to note about a PriorityQueue is that an enhanced for-loop (or Iterator) makes no guarantee in the ordering of elements after the head.

Question 11

What is the Deque collection interface?

Answer 11

A Deque is a collection that allows us to manipulate elements from both the front and end of the collection.

Question 12

What are the methods and exceptions of Deque interface?

Answer 12

The Deque interface has two types of methods for manipulating the front and back of the collection.

The following methods throw an exception when:

• addFirst(), addLast() - there is no space to add an element.
• removeFirst(), removeLast() - there is no element to remove.
• getFirst(), getLast() - there is no element to get.

The following methods return a special value:

• offerFirst(), offerLast() - false when there is no space to add an element. // returns boolean
• pollFirst(), pollLast() - null when there is no element to remove.
• peekFirst(), peekLast() - null when there is no element to get.

Question 13

What are the implementations of Deque class?

Answer 13

A Deque has many implementations and we’ll focus on the LinkedList and ArrayDeque implementations. The LinkedList, although not the most optimized, is flexible enough to not only be used as a List and Queue but also a Deque. The ArrayDeque is the preferred implementation when needing to manipulate elements at the front and end of a collection.

Question 14

A sample implementation of Deque interface?

Answer 14

Deque<String> stringDeque = new LinkedList<>();
stringDeque.addFirst("A"); // Front -> "A" <- end
stringDeque.offerFirst("B"); // Return `true` - front -> "B", "A" <- end
stringDeque.offerLast("Z"); // Returns `true` - front -> "B", "A", "Z" <- end
 
String a = stringDeque.removeFirst()  // Returns "B" - front -> "A", "Z"
String b = stringDeque.pollLast()  // Returns "Z" - front -> "A" <- back
String c = stringDeque.removeLast()  // Returns "A" - empty deque
 
String d = stringDeque.peekFirst()  // Returns null
String e = stringDeque.getLast() // Throws NoSuchElementException

Question 15

How do we iterate over Deque?

Answer 15

We can iterate Deque from front to back using an enhanced for-loop and we can use the descendingIterator() method and use the Iterator returned to go from back to front.

// Assuming `stringDeque` has elements front -> "Mike", "Jack", "John" <- back
Iterator<String> descItr = stringDeque.descendingIterator();
 
while(descItr.hasNext()) {
  System.out.println(descItr.next());
}
// OUTPUT TERMINAL:  "John", "Jack", "Mike"

Question 16

What are the some other collection methods?

Answer 16

addAll() - receives a Collection argument and adds all the elements.
isEmpty() - return true if the collection is empty, false otherwise.
iterator() - returns an Iterator over the collection.
size() - returns the number of elements in the collection.
stream() - returns a Stream over the elements in the collection.
toArray() - returns an array with all elements in the collection.

Question 17

What is a map?

Answer 17

Map defines a generic interface for an object that holds key-value pairs as elements. The key is used to retrieve (like the index in an array or List) some value. A key must be unique and map to exactly one value. A Map can be thought of as a Java interface for a Hash Table data structure.

Question 18

HashMap?

Answer 18

The HashMap defines no specific ordering for the keys and is the most optimized implementation for retrieving values

Question 19

LinkedHashMap?

Answer 19

The LinkedHashMap keeps the keys in insertion order and is slightly less optimal than the HashMap.

Question 20

TreeMap?

Answer 20

The TreeMap keeps keys in their natural order (or some custom order defined using a Comparator). This implementation has a significant performance decrease compared to HashMap and LinkedHashMap but is great when needing to keep keys sorted.

Question 21

What methods do we use to access elements in a map?

Answer 21

put(): Sets the value that key maps to. Note that this method replaces the value key mapped to if the key was already present in the Map.

get(): Gets, but does not remove, the value the provided key argument points to if it exists. This method returns null if the key is not in the Map. Let’s see how we can use them:

Map<String, String> myMap = new HashMap<>();
 
myMap.put("Hello", "World") // { "Hello" -> "World" }
myMap.put("Name", "John") //   { "Hello" -> "World" }, { "Name" -> "John" }
 
String result = myMap.get("Hello") // returns "World" 
String noResult = myMap.get("Jack") // return `null`

Question 22

Iterating over a map?

Answer 22

// Given a map, `myMap`, with the following key-value pairs { "Hello" -> "World" }, { "Name" -> "John"}
for (Map.Entry<String, String> pair: myMap.entrySet()){
  System.out.println("key: "+pair.getKey()+", value: "+pair.getValue());
}
// OUTPUT TERMINAL:
// key: Name, value: John
// key: Hello, value: World