Collections

Java Collections Framework Tutorial 1. What is the Collections Framework?

The Collections Framework provides a unified architecture for representing and manipulating collections. This framework includes:

Core Collection Interfaces

• List: An ordered collection. Allows duplicate elements.
• • ArrayList: Resizable array implementation.
• • LinkedList: Doubly-linked list implementation.
• • Vector: Similar to ArrayList, but thread-safe.
• Set: A collection that does not allow duplicate elements.
• • HashSet: Uses a hash table for storage. No order.
• • LinkedHashSet: Ordered by the insertion order.
• • TreeSet: Stored in a sorted order (red-black tree).
• Queue: A collection designed for holding elements prior to processing.
• • PriorityQueue: Elements ordered by their natural ordering or by a comparator.
• • ArrayDeque: Resizable array that can be used as a stack or a queue.
• • Deque: Extends Queue to handle elements at both ends.
• • ArrayDeque: Can be used as both a queue and a stack.
• Map: An object that maps keys to values. No duplicate keys.
• • HashMap: Uses a hash table to store key-value pairs.
• • TreeMap: Red-black tree-based implementation.
• • LinkedHashMap: Hash table and linked list implementation.
• • Hashtable: Similar to HashMap, but thread-safe.

List

A List is an ordered collection of elements that allows duplicate values. It can grow or shrink dynamically, and elements can be inserted or accessed by their position in the list.

List Implementations:

• ArrayList: This is a resizable array implementation of the List interface. It provides fast random access but slower insertions and removals in the middle.
• LinkedList: A doubly-linked list implementation of the List interface. It offers faster insertions and removals, but slower random access.
• Vector: Similar to ArrayList, but it's thread-safe. However, it's considered somewhat antiquated in modern Java programming.

Creating a List:

List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();

Adding Elements:

arrayList.add("Apple");
arrayList.add("Banana");
arrayList.add(1, "Cherry"); // Inserts at position 1

Accessing Elements

String fruit = arrayList.get(1); // Banana

Removing Elements

arrayList.remove(1); // Removes "Banana"
arrayList.remove("Apple");

Iterating Over a List

for(String item : arrayList) {
System.out.println(item);
}

Checking Size and Contents

int size = arrayList.size();
boolean containsApple = arrayList.contains("Apple");

Bulk Operations

List<String> anotherList = Arrays.asList("Grape", "Mango");
arrayList.addAll(anotherList); // Appends all elements from anotherList

Replace Element

arrayList.set(1, "Berry"); // Replaces the element at index 1

Sublist

List<String> subList = arrayList.subList(1, 3); // Includes the starting index, excludes the end index

Streams with Lists

// Using streams to filter and print items
arrayList.stream()
.filter(item -> item.startsWith("A"))
.forEach(System.out::println);

Common Pitfalls

• Avoiding Concurrency Issues: If a list is accessed by multiple threads, consider synchronization. For an immutable list, consider using Collections.unmodifiableList().
• Array Store Exception: When converting a list to an array, ensure the array type matches the list's type.
• Index Out of Bounds: Be cautious while accessing elements by index. Ensure the index is valid.

Set

A Set is a collection that does not allow duplicate elements. It models the mathematical set abstraction and is part of the Java Collections Framework.

Set Implementations:

• HashSet: This uses a hash table for storage. It does not guarantee any order of its elements.
• LinkedHashSet: It maintains the insertion order. It's slightly slower than HashSet but faster than TreeSet.
• TreeSet: A NavigableSet implemented based on a Red-Black Tree. Elements are stored in a sorted order.

Creating a Set

Set<String> hashSet = new HashSet<>();
Set<String> linkedHashSet = new LinkedHashSet<>();
Set<String> treeSet = new TreeSet<>();

Adding Elements

hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Apple"); // Duplicate, will not be added

Removing Elements

hashSet.remove("Apple");

contains an Element:

boolean hasApple = hashSet.contains("Apple");

Iterat3

for(String item : hashSet) 
   System.out.println(item);

Size

int size = hashSet.size();

Union

Set<String> anotherSet = new HashSet<>(Arrays.asList("Grape", "Mango"));
Set<String> union = new HashSet<>(hashSet);
union.addAll(anotherSet);

Intersection

Set<String> intersection = new HashSet<>(hashSet);
intersection.retainAll(anotherSet);

Difference

Set<String> difference = new HashSet<>(hashSet);
difference.removeAll(anotherSet);

TreeSet

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);

Integer highest = numbers.last();
Integer lowest = numbers.first();

Streams with Sets

hashSet.stream()
.filter(item -> item.startsWith("A"))
.forEach(System.out::println);

Common Pitfalls

• Element Uniqueness: The uniqueness of elements in a set is determined by the equals() and hashCode() methods. Make sure custom objects override these appropriately.
• Thread Safety: Default set implementations are not thread-safe. Consider Collections.synchronizedSet() for a basic thread-safe set or explore the java.util.concurrent package for more advanced concurrent collections.
• Null Values: While HashSet and LinkedHashSet allow a single null value, TreeSet does not allow null values as it cannot be compared to other values.

Queue

A Queue is a collection designed to hold elements until they are processed or until their time to be processed arrives. Elements are typically processed in a first-in-first-out (FIFO) order, though exceptions like priority queues exist.

Queue Implementations:

• LinkedList: Apart from being a list, LinkedList is also a Deque (double-ended queue) and can be used as a FIFO queue.
• PriorityQueue: Elements of the priority queue are ordered according to their natural ordering or by a Comparator provided at queue construction time. They don't follow the FIFO rule if their priorities differ.
• ArrayDeque: A resizable array implementation of the Deque interface, can be used as both a queue and a stack.

Creating a Queue

Queue<String> linkedListQueue = new LinkedList<>();
Queue<String> priorityQueue = new PriorityQueue<>();
Queue<String> arrayDequeQueue = new ArrayDeque<>();

Adding Elements:

linkedListQueue.offer("Apple");
linkedListQueue.offer("Banana");

Retrieving and Removing Elements

String head = linkedListQueue.poll(); // Retrieves and removes head; returns null if empty
String peekHead = linkedListQueue.peek(); // Retrieves but doesn't remove head; returns null if empty

Size and contains

int size = linkedListQueue.size();
boolean containsApple = linkedListQueue.contains("Apple");

PriorityQueue

With a PriorityQueue, elements are assigned priorities. When you retrieve an element, the element with the highest priority is returned. If multiple elements have the same priority, they are processed according to their order in the queue.

Example with integers (their natural order is used):

PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.offer(10);
numbers.offer(5);
System.out.println(numbers.poll()); // Outputs 5 because it's smaller

Example with custom objects and comparators:

class Person {
    String name;
    int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
  }
}

// Create a PriorityQueue where persons are ordered by their age
PriorityQueue<Person> people = new PriorityQueue<>(Comparator.comparingInt(person -> person.age));
people.offer(new Person("Alice", 30));
people.offer(new Person("Bob", 25));
System.out.println(people.poll().name); // Outputs Bob as he is younger

Best Practices

• Nulls: Queues don't allow the insertion of null elements.
• Thread Safety: Default queue implementations are not thread-safe. For thread safety, you can wrap them using Collections.synchronizedQueue() or use classes from java.util.concurrent like ConcurrentLinkedQueue or ArrayBlockingQueue.
• Capacity Restrictions: Some queues like ArrayBlockingQueue have capacity restrictions, so always ensure there's room before adding an element or handle possible exceptions.

Map

A Map represents a collection of key-value pairs where each key is mapped to exactly one value. The keys are unique, but values can be duplicated.

Map Implementations:

• HashMap: Implements Map using a hash table. It allows null values and the null key. It doesn't guarantee any order of its key-value pairs.
• LinkedHashMap: Maintains the insertion order or can be set up to maintain access order. It is slightly slower than HashMap but faster than TreeMap.
• TreeMap: A Red-Black tree-based NavigableMap implementation. Pairs are ordered by their keys' natural ordering, or by a Comparator provided at the map's creation time.
• Hashtable: Similar to HashMap but is synchronized. It's considered somewhat antiquated in modern Java programming.

Creating a Map

Map<String, Integer> hashMap = new HashMap<>();
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
Map<String, Integer> treeMap = new TreeMap<>();

Putting Key-Value Pairs

hashMap.put("Apple", 100);
hashMap.put("Banana", 60);

Getting Values

int applePrice = hashMap.get("Apple"); // Returns 100

Removing Key-Value Pairs

hashMap.remove("Apple");

Checking for Keys/Values:

boolean hasApple = hashMap.containsKey("Apple");
boolean hasPrice100 = hashMap.containsValue(100);

Iterating

for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
  System.out.println(entry.getKey() + ": " + entry.getValue());
}

Bulk Operations

Map<String, Integer> anotherMap = new HashMap<>();
anotherMap.putAll(hashMap); // Puts all mappings from hashMap into anotherMap

Default Methods (Java 8 and Beyond):

hashMap.getOrDefault("Cherry", 0); // Returns 0 if "Cherry" isn't in the map

hashMap.putIfAbsent("Apple", 80); // Puts the value if "Apple" isn't already mapped

hashMap.replace("Banana", 70); // Replaces the existing value for "Banana"

Streams with Maps

Filter a map to create another one with prices greater than 80:

Map<String, Integer> expensiveFruits = hashMap.entrySet()
.stream()
.filter(entry -> entry.getValue() > 80)
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

Best Practices:

• Key Uniqueness: Keys in a map are unique. When you put a key-value pair with an existing key, the value is overwritten.
• Nulls: While HashMap and LinkedHashMap allow one null key and many null values, TreeMap doesn't allow any null keys but does allow null values.
• Thread Safety: Default map implementations aren't thread-safe. For a basic thread-safe map, use Collections.synchronizedMap(). Alternatively, the java.util.concurrent package offers ConcurrentHashMap for concurrent use.

Exercises

List

• Basic Operations:

• • Create an ArrayList and add the following elements: "Apple", "Banana", "Cherry", "Date", "Fig".
• • Remove the third element from the list.
• • Check if the list contains "Cherry".
• • Print all elements of the list using a for-each loop.

• Intermediate Operations:

• • Create a List of integers. Add the numbers 1 to 10 to the list.
• • Remove all even numbers from the list.

• Advanced Operations:

• • Create an ArrayList with the following elements: 5, 2, 8, 7, 1. Sort the list in descending order.
• • Create two lists, list1 with elements "a", "b", "c" and list2 with elements "c", "d", "e". Find the common elements between the two lists.
• • Create an ArrayList and add random numbers (between 1 to 100) until the total of numbers added surpasses 1000. Print the list and the final total.

Set

• Basic Operations:

• • Create a HashSet and add the following elements: "Lion", "Tiger", "Panther", "Cheetah", "Leopard".
• • Check if the set contains "Panther".
• • Remove "Leopard" from the set.
• • Try to add "Tiger" again to the set and observe what happens. (Sets do not allow duplicate entries)

• Intermediate Operations:

• • Create a TreeSet of integers. Add the numbers 15, 5, 29, 5, 42, 19 to the set.
• • Print the first and last elements of the set.
• • Create a LinkedHashSet of strings. Add "Step1", "Step2", "Step3", "Step4". Remove the second element and print the set. Observe the order of the elements.

• Advanced Operations:

• • Create two HashSet collections: set1 containing "a", "b", "c", "d" and set2 containing "c", "d", "e", "f". Find the union of the two sets (all unique elements from both sets).
• • Continuing from the previous exercise, find the intersection of set1 and set2 (only the elements that are present in both sets).
• • Create a TreeSet with the following elements: 5, 1, 7, 6, 8, 2. Retrieve and print the element just higher than 5 and the element just lower than 5.

Queue

• Basic Operations:

• • Create a LinkedList (which implements Queue) and add the following strings: "Tom", "Jerry", "Spike", "Tyke".
• • Peek at the front of the queue without removing the element.
• • Poll an element from the queue (this will retrieve and remove the front element).
• • Check the size of the queue after the poll operation.

• Intermediate Operations:

• • Implement a simple queue using an ArrayDeque and add five integers to it.
• • Iterate through the queue and print each element. (Note: Iterating through the queue will not remove elements from it)
• • Use the remove method to remove a specific element from the queue, and print the queue after.

• Advanced Operations:

• • Create a PriorityQueue of integers and add numbers: 15, 10, 20, 5, 30. Peek at the front element. (Note: PriorityQueue orders its elements in their natural order or based on a comparator, so the smallest integer will be at the front in this case.)
• • Implement a basic printer queue simulation where documents named "Doc1", "Doc2", "Doc3", etc. are added to a LinkedList. Then simulate the printer processing (polling) each document until the queue is empty.

Map

• Basic Operations:

• • Create a HashMap with 5 key-value pairs where keys are names of countries and values are their capitals.
• • Retrieve the capital of a specific country using the get method.
• • Check if the map contains a particular country using the containsKey method.

• Intermediate Operations:

• Insert a new key-value pair only if the key doesn't already exist in the map (use putIfAbsent).

• Remove a country-capital pair by country name.

• Print all countries (keys) and separately print all capitals (values).

• Advanced Operations:

• • Create a TreeMap and add some key-value pairs. Observe the order in which the keys are stored (it should be sorted).
• • Merge two maps: Given two maps, add all the key-value pairs from the second map to the first. If a key already exists, concatenate the values.
• • Count the occurrences of each word in a sentence and store the result in a map where keys are words and values are their occurrences.

Solutions

List

Basic Operations:

• Create an ArrayList and add elements.

  List<String> fruits = new ArrayList<>();
  fruits.addAll(Arrays.asList("Apple", "Banana", "Cherry", "Date", "Fig"));

• Remove the third element from the list.

  fruits.remove(2); // Indexing starts at 0, so Cherry is removed.

• Check if the list contains "Cherry".

  boolean hasCherry = fruits.contains("Cherry");
  System.out.println(hasCherry);  // This will return false since we've just removed "Cherry".

• Print all elements of the list using a for-each loop.

  for (String fruit : fruits) {
  System.out.println(fruit);
  }

Intermediate Operations:

• Create a LinkedList of integers and add numbers.

  List<Integer> numbers = new LinkedList<>();
  for (int i = 1; i <= 10; i++) {
  numbers.add(i);
  }

• Remove all even numbers from the list.

  numbers.removeIf(n -> n % 2 == 0);

• Convert the LinkedList into an array of integers.

  Integer[] array = numbers.toArray(new Integer[0]);

Advanced Operations:

• Create an ArrayList and sort in descending order.

  List<Integer> nums = new ArrayList<>(Arrays.asList(5, 2, 8, 7, 1));
  nums.sort(Collections.reverseOrder());

• Find common elements between two lists.

  List<String> list1 = new ArrayList<>(Arrays.asList("a", "b", "c"));
  List<String> list2 = new ArrayList<>(Arrays.asList("c", "d", "e"));
  list1.retainAll(list2);
  System.out.println(list1);  // Outputs: [c]

• Create ArrayList and add random numbers.

  List<Integer> randomNumbers = new ArrayList<>();
  Random random = new Random();
  int total = 0;

  while (total <= 1000) {
  int nextNum = random.nextInt(100) + 1;
  randomNumbers.add(nextNum);
  total += nextNum;
  }
  System.out.println(randomNumbers);
  System.out.println("Total: " + total);

Set

Basic Operations:

Set<String> animals = new HashSet<>();
animals.addAll(Arrays.asList("Lion", "Tiger", "Panther", "Cheetah", "Leopard"));

boolean containsPanther = animals.contains("Panther");
System.out.println(containsPanther);

animals.remove("Leopard");

animals.add("Tiger"); // Nothing will happen since "Tiger" is already in the set.

Intermediate Operations:

TreeSet<Integer> numbers = new TreeSet<>();
numbers.addAll(Arrays.asList(15, 5, 29, 5, 42, 19));

System.out.println("First element: " + numbers.first());
System.out.println("Last element: " + numbers.last());

LinkedHashSet<String> steps = new LinkedHashSet<>();
steps.addAll(Arrays.asList("Step1", "Step2", "Step3", "Step4"));
steps.remove("Step2");
System.out.println(steps);

Advanced Operations:

HashSet<String> set1 = new HashSet<>(Arrays.asList("a", "b", "c", "d"));
HashSet<String> set2 = new HashSet<>(Arrays.asList("c", "d", "e", "f"));
// Union
HashSet<String> union = new HashSet<>(set1);
union.addAll(set2);
System.out.println("Union: " + union);

// Intersection
HashSet<String> intersection = new HashSet<>(set1);
intersection.retainAll(set2);
System.out.println("Intersection: " + intersection);

TreeSet<Integer> treeSetNumbers = new TreeSet<>(Arrays.asList(5, 1, 7, 6, 8, 2));
System.out.println("Higher than 5: " + treeSetNumbers.higher(5));
System.out.println("Lower than 5: " + treeSetNumbers.lower(5));

Queue

Basic Operations:

• Create a LinkedList and add strings.

  Queue<String> characters = new LinkedList<>();
  characters.addAll(Arrays.asList("Tom", "Jerry", "Spike", "Tyke"));

• Peek at the front.

  String frontCharacter = characters.peek();
  System.out.println(frontCharacter);  // Outputs: Tom

• Poll an element.

  String polledCharacter = characters.poll();
  System.out.println(polledCharacter);  // Outputs: Tom

• Check the size.

  int size = characters.size();
  System.out.println(size);  // Outputs: 3

Intermediate Operations:

• Implement a simple queue with ArrayDeque.

  Queue<Integer> numbers = new ArrayDeque<>();
  numbers.addAll(Arrays.asList(1, 2, 3, 4, 5));

• Iterate and print.

  for (int num : numbers) 
  System.out.println(num);

• Remove a specific element.

  numbers.remove(3);  // Removes the number 3 from the queue
  System.out.println(numbers);

Advanced Operations:

• Create a PriorityQueue.

  Queue<Integer> priorityNumbers = new PriorityQueue<>();
  priorityNumbers.addAll(Arrays.asList(15, 10, 20, 5, 30));
  int frontNumber = priorityNumbers.peek();
  System.out.println(frontNumber);  // Outputs: 5 (since 5 is the smallest in the list)

• Implement a basic printer queue simulation.

  Queue<String> printerQueue = new LinkedList<>();
  printerQueue.addAll(Arrays.asList("Doc1", "Doc2", "Doc3"));
  while (!printerQueue.isEmpty()) {
  String document = printerQueue.poll();
  System.out.println("Printing: " + document);
  }

Map

Basic Operations:

• Create a HashMap with countries and capitals.

  Map<String, String> countries = new HashMap<>();
  countries.put("USA", "Washington D.C.");
  countries.put("UK", "London");
  countries.put("France", "Paris");
  countries.put("Germany", "Berlin");
  countries.put("India", "New Delhi");

• Retrieve the capital of a specific country.

  String capitalOfFrance = countries.get("France");
  System.out.println(capitalOfFrance);  // Outputs: Paris

• Check if the map contains a particular country.

  boolean containsFrance = countries.containsKey("France");
  System.out.println(containsFrance);  // Outputs: true

  Intermediate Operations:

• Insert using putIfAbsent.

  countries.putIfAbsent("Spain", "Madrid");

• Remove a country-capital pair.

  countries.remove("Germany");

• Print all countries and capitals.

  System.out.println("Countries: " + countries.keySet());
  System.out.println("Capitals: " + countries.values());

Advanced Operations:

• Create a TreeMap.

  Map<String, String> treeCountries = new TreeMap<>();
  treeCountries.put("Australia", "Canberra");
  treeCountries.put("Canada", "Ottawa");
  treeCountries.put("Brazil", "Brasilia");
  System.out.println(treeCountries.keySet());  // Outputs: [Australia, Brazil, Canada]

• Merge two maps.

  Map<String, String> map1 = new HashMap<>();
  Map<String, String> map2 = new HashMap<>();
  map1.put("A", "apple");
  map2.put("B", "banana");
  map2.put("A", "ant");
  map1.forEach((key, value) -> map2.merge(key, value, (v1, v2) -> v1 + ", " + v2));
  System.out.println(map2);

• Count word occurrences.

  String sentence = "apple banana apple orange apple";
  Map<String, Integer> wordCounts = new HashMap<>();
  for (String word : sentence.split(" ")) {
  wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
  }
  System.out.println(wordCounts);