Introduction to Java Collections Framework

The Java Collections Framework (JCF) is a unified architecture for representing and manipulating collections (groups of objects). Introduced in Java 1.2, it provides high-performance, high-quality implementations of useful data structures and algorithms, reducing programming effort and increasing program speed and quality.

Core Interfaces

The Collections Framework is built around a set of standard interfaces:

1. Collection<E>: The root interface in the collection hierarchy. It represents a group of objects, known as its elements.
2. List<E>: An ordered collection (also known as a sequence). Lists can contain duplicate elements. Common implementations include ArrayList and LinkedList.
3. Set<E>: A collection that cannot contain duplicate elements. It models the mathematical set abstraction. Common implementations include HashSet and TreeSet.
4. Queue<E>: A collection used to hold multiple elements prior to processing, typically ordered in a FIFO (first-in, first-out) manner. Common implementations include PriorityQueue and LinkedList.
5. Map<K, V>: An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. Common implementations include HashMap and TreeMap. (Note: Map does not extend Collection, but is part of the framework).

Key Implementations

ArrayList vs LinkedList

• ArrayList: Backed by a dynamic array. Fast random access ($O(1)$) but slow insertions and deletions in the middle ($O(n)$) because elements need to be shifted.
• LinkedList: Backed by a doubly-linked list. Fast insertions and deletions ($O(1)$ once the node is found), but slow random access ($O(n)$) because it requires traversal.

HashSet vs TreeSet

• HashSet: Backed by a hash table. Offers constant time ($O(1)$) performance for basic operations (add, remove, contains), assuming a good hash function. Elements are unordered.
• TreeSet: Backed by a red-black tree. Elements are sorted according to their natural ordering or a custom Comparator. Provides $O(\log n)$ time cost for basic operations.

HashMap vs TreeMap

• HashMap: Fast, unordered key-value storage. Uses a hash table structure. Keys must implement hashCode() and equals() correctly.
• TreeMap: Sorted key-value storage. Keys are kept sorted, which is useful for range queries.

Iterating Over Collections

Java provides multiple ways to iterate over collections:

Enhanced For-Loop

List<String> names = List.of("Alice", "Bob", "Charlie");
for (String name : names) {
    System.out.println(name);
}

Iterators

Iterators provide a way to safely remove elements during traversal:

List<String> mutableNames = new ArrayList<>(names);
Iterator<String> iterator = mutableNames.iterator();
while (iterator.hasNext()) {
    String name = iterator.next();
    if (name.startsWith("A")) {
        iterator.remove();
    }
}

Streams (Java 8+)

Functional style iteration using the Stream API:

names.stream()
     .filter(name -> name.startsWith("C"))
     .forEach(System.out::println);

Why Use the Collections Framework?

• Reduces Programming Effort: By providing useful data structures and algorithms, the Collections Framework frees you to concentrate on the important parts of your program.
• Increases Program Speed and Quality: The framework provides high-performance implementations of data structures and algorithms.
• Fosters Software Reuse: New data structures that conform to the standard collection interfaces are by nature reusable.

In the next sections, we will delve deeper into specific utilities and advanced concepts like the Collections utility class and the Stream API Collectors.