Module 10: The Collections Framework

The Java Collections Framework (JCF) provides a unified architecture for storing and manipulating groups of objects. It eliminates the need to manually build linked lists, dynamic arrays, hash tables, and search trees.

The Three Main Collection Interfaces

• List: An ordered sequence of elements that allows duplicate values. Elements are indexed with zero-based integers. (Implementations: ArrayList, LinkedList, Vector).
• Set: An unordered collection that guarantees no duplicate elements. (Implementations: HashSet, LinkedHashSet, TreeSet).
• Queue: Designed specifically for holding elements prior to processing, typically in First-In, First-Out (FIFO) or priority order. (Implementations: ArrayDeque, PriorityQueue, LinkedList).

Note on Map: A Map stores key-value pairs rather than individual elements. Because a mapping of keys to values has fundamentally different operational semantics (e.g. put, get, keySet), Map sits in a separate hierarchy and does NOT extend Collection.

Choosing between ArrayList and LinkedList is a classic algorithmic engineering trade-off:

Comparative Analysis

• ArrayList: Backed internally by a dynamically resizing array.
  • Random Access get(i): $O(1)$ constant time (direct memory indexing).
  • Middle Insertions/Deletions: $O(n)$ linear time because subsequent elements must shift left or right in memory.
  • Capacity Growth: Expands by 50% ($1.5 imes$) whenever its internal buffer reaches capacity.
• LinkedList: Backed by a doubly-linked chain of node objects.
  • Head/Tail Insertions/Deletions: $O(1)$ constant time (only pointer links change).
  • Random Access get(i): $O(n)$ linear time (must traverse pointers from head or tail).
  • Memory Overhead: Higher memory consumption due to node object allocation and two reference pointers (next and prev) per element.

Sets guarantee that no duplicate elements exist within the collection. Java provides two primary set implementations:

• HashSet: Backed internally by a HashMap instance.
  • Provides average $O(1)$ time complexity for add, remove, and contains.
  • Elements have unspecified iteration order.
  • Detects duplicates using the elements' hashCode() and equals() methods.
• TreeSet: Backed internally by a self-balancing binary search tree (specifically, a Red-Black Tree / TreeMap).
  • Provides guaranteed $O(log n)$ time complexity for fundamental operations.
  • Maintains elements in strictly sorted natural ascending order (or according to a custom Comparator).
  • Detects duplicates using compareTo() or compare() (returns 0).

A Map associates unique keys with corresponding values. Duplicate keys are prohibited; inserting a duplicate key overwrites the existing value associated with that key.

Map<String, Integer> ages = new HashMap<>();
ages.put("Amit", 21);
ages.put("Neha", 23);