# Unit 4: Java Collections Framework ## 1. Java Collections Framework ### 1.1. Collections and Collection Framework Hierarchy * **Collections Framework:** A set of classes and interfaces that support the representation and manipulation of collections of objects. It simplifies programming by providing ready-to-use data structures. * **Hierarchy:** A hierarchical structure of interfaces and classes. * **Top-level Interface:** `Object` * **Root Interface:** `Collection` (defines basic collection operations) * **Key Interfaces:** `List`, `Set`, `Queue` * **Map Interface:** Not part of `Collection` hierarchy but a fundamental part of the framework. * **Abstract Implementations:** `AbstractCollection`, `AbstractList`, `AbstractSet`, `AbstractQueue`, `AbstractMap` (provide common implementations to reduce coding effort). * **Concrete Implementations:** `ArrayList`, `LinkedList`, `HashSet`, `TreeSet`, `HashMap`, `TreeMap`, etc. **[Figure: Java Collections Framework Hierarchy]** This diagram illustrates the parent-child relationships between interfaces and classes in the Java Collections Framework. Understanding this hierarchy is crucial for choosing the appropriate collection type for a given task and for understanding inheritance. ### 1.2. Iterator Interface * `java.util.Iterator`: An interface that allows traversing a collection element by element. * **Key Methods:** * `boolean hasNext()`: Returns `true` if the iteration has more elements. * `E next()`: Returns the next element in the iteration. * `void remove()`: Removes from the underlying collection the last element returned by this iterator. (Optional operation) * `void forEachRemaining(Consumer action)`: Performs the given action for each remaining element. (Java 8+) * **Exam Point:** Essential for iterating over collections, especially when removal is required during iteration. Avoids `ConcurrentModificationException`. ### 1.3. Collection Interface * `java.util.Collection`: The root interface for most collections. * **Key Methods:** * `boolean add(E e)`: Adds the specified element to this collection. * `boolean addAll(Collection c)`: Adds all of the elements in the specified collection to this collection. * `void clear()`: Removes all of the elements from this collection. * `boolean contains(Object o)`: Returns `true` if this collection contains the specified element. * `boolean isEmpty()`: Returns `true` if this collection contains no elements. * `Iterator iterator()`: Returns an iterator over the elements in this collection. * `boolean remove(Object o)`: Removes a single instance of the specified element from this collection. * `boolean removeAll(Collection c)`: Removes all of this collection's elements that are also contained in the specified collection. * `int size()`: Returns the number of elements in this collection. * `Object[] toArray()`: Returns an array containing all of the elements in this collection. * **Exam Point:** Defines the fundamental operations for all collections (except `Map`). ## 2. List Interface and Implementations * `java.util.List`: An ordered collection (also known as a sequence). Lists allow duplicate elements and provide indexed access. * **Key Methods (additional to Collection):** * `void add(int index, E element)`: Inserts the specified element at the specified position in this list. * `E get(int index)`: Returns the element at the specified position in this list. * `E remove(int index)`: Removes the element at the specified position in this list. * `E set(int index, E element)`: Replaces the element at the specified position in this list with the specified element. * `int indexOf(Object o)`: Returns the index of the first occurrence of the specified element in this list. * `int lastIndexOf(Object o)`: Returns the index of the last occurrence of the specified element in this list. ### 2.1. ArrayList * **Implementation:** Dynamic array. * **Characteristics:** * **Fast random access** (`get`, `set` operations are O(1)). * **Slow insertion/deletion** in the middle (O(n) because elements need to be shifted). * **Resizes automatically** when capacity is exceeded. * **Use Case:** When frequent access to elements is needed, and insertions/deletions are rare. ### 2.2. LinkedList * **Implementation:** Doubly linked list. * **Characteristics:** * **Fast insertion/deletion** at the beginning, end, or middle (O(1) if iterator is positioned). * **Slow random access** (`get`, `set` operations are O(n) as it requires traversal). * **Use Case:** When frequent insertions/deletions are needed, and random access is less important. ### 2.3. Vector * **Implementation:** Dynamic array (similar to `ArrayList`). * **Characteristics:** * **Synchronized:** All methods are thread-safe. This makes it slower than `ArrayList` in single-threaded environments. * **Legacy class:** Generally preferred to use `ArrayList` with explicit synchronization if needed. * **Use Case:** Older codebases or when thread-safety is a strict requirement and performance is not the primary concern. ### 2.4. Stack * **Implementation:** Extends `Vector`. LIFO (Last-In, First-Out) data structure. * **Key Methods:** * `E push(E item)`: Pushes an item onto the top of this stack. * `E pop()`: Removes the object at the top of this stack and returns that object. * `E peek()`: Looks at the object at the top of this stack without removing it. * `boolean empty()`: Tests if this stack is empty. * **Use Case:** Implementing stack operations, e.g., function call stack, undo/redo functionality. ## 3. Queue Interface * `java.util.Queue`: An object designed for holding elements prior to processing. Typically orders elements in a FIFO (First-In, First-Out) manner. * **Key Methods:** * `boolean add(E e)`: Inserts the specified element into this queue. Throws an exception if capacity restricted and no space available. * `boolean offer(E e)`: Inserts the specified element into this queue. Returns `false` if capacity restricted and no space available. * `E remove()`: Retrieves and removes the head of this queue. Throws an exception if queue is empty. * `E poll()`: Retrieves and removes the head of this queue. Returns `null` if queue is empty. * `E element()`: Retrieves, but does not remove, the head of this queue. Throws an exception if queue is empty. * `E peek()`: Retrieves, but does not remove, the head of this queue. Returns `null` if queue is empty. * **Implementations:** `LinkedList`, `PriorityQueue`, `ArrayDeque`. * **Exam Point:** Used for processing elements in a specific order, often for task scheduling or breadth-first searches. ## 4. Set Interface and Implementations * `java.util.Set`: A collection that contains no duplicate elements. * **Key Characteristics:** * Does not allow duplicate elements. * No guaranteed order (unless specified by implementation). * `add` operation returns `false` if the element is already present. * **Exam Point:** Useful for storing unique items and performing efficient membership tests. ### 4.1. HashSet * **Implementation:** Based on a hash table. * **Characteristics:** * **No duplicate elements.** * **No guaranteed order** of elements (order may change). * **Fast performance** for `add`, `remove`, `contains` (average O(1)). * Does not allow `null` elements (prior to Java 8, it allowed one null; Java 8+ still allows one null). * **Use Case:** When order is not important and fast lookup is required. ### 4.2. LinkedHashSet * **Implementation:** Hash table and a doubly linked list. * **Characteristics:** * **No duplicate elements.** * **Maintains insertion order.** Elements are returned in the order they were inserted. * Performance is similar to `HashSet` (average O(1)) but with a slight overhead due to the linked list. * **Use Case:** When unique elements are needed, and the order of insertion must be preserved. ### 4.3. SortedSet and TreeSet * `java.util.SortedSet`: A `Set` whose elements are sorted according to their natural ordering, or by a `Comparator` provided at `SortedSet` creation time. * **`java.util.TreeSet`:** * **Implementation:** Balanced tree (typically Red-Black tree). * **Characteristics:** * **No duplicate elements.** * **Elements are stored in sorted order.** * **Performance:** O(log n) for `add`, `remove`, `contains`. * Requires elements to be comparable (implement `Comparable`) or a `Comparator` must be provided. * **Key Methods (inherited from `SortedSet`):** * `Comparator comparator()`: Returns the comparator used to order this set, or `null` if it uses the natural ordering of its elements. * `SortedSet subSet(E fromElement, E toElement)`: Returns a view of the portion of this set whose elements range from `fromElement`, inclusive, to `toElement`, exclusive. * `SortedSet headSet(E toElement)`: Returns a view of the portion of this set whose elements are strictly less than `toElement`. * `SortedSet tailSet(E fromElement)`: Returns a view of the portion of this set whose elements are greater than or equal to `fromElement`. * `E first()`: Returns the first (lowest) element currently in this set. * `E last()`: Returns the last (highest) element currently in this set. * **Use Case:** When unique elements are needed and they must be kept in sorted order. ## 5. Map Interface and Implementations * `java.util.Map`: An object that maps keys to values. A map cannot contain duplicate keys, and each key can map to at most one value. * **Key Methods:** * `V put(K key, V value)`: Associates the specified value with the specified key in this map. Returns the previous value associated with `key`, or `null` if there was no mapping for `key`. * `V get(Object key)`: Returns the value to which the specified key is mapped, or `null` if this map contains no mapping for the key. * `V remove(Object key)`: Removes the mapping for a key from this map if it is present. * `boolean containsKey(Object key)`: Returns `true` if this map contains a mapping for the specified key. * `boolean containsValue(Object value)`: Returns `true` if this map maps one or more keys to the specified value. * `Set keySet()`: Returns a `Set` view of the keys contained in this map. * `Collection values()`: Returns a `Collection` view of the values contained in this map. * `Set> entrySet()`: Returns a `Set` view of the mappings contained in this map. * **Exam Point:** Fundamental for key-value data representation. ### 5.1. HashMap * **Implementation:** Hash table. * **Characteristics:** * **No duplicate keys.** * **No guaranteed order** of key-value mappings. * **Fast performance** for `put`, `get`, `remove` (average O(1)). * Allows one `null` key and multiple `null` values. * **Use Case:** General-purpose map when order is not important and fast lookups are desired. ### 5.2. LinkedHashMap * **Implementation:** Hash table and a doubly linked list. * **Characteristics:** * **No duplicate keys.** * **Maintains insertion order** by default. Can also maintain access order. * Performance is similar to `HashMap` (average O(1)) with slight overhead. * **Use Case:** When key-value pairs need to be stored uniquely, and the order of insertion (or access) needs to be preserved. ### 5.3. TreeMap * **Implementation:** Balanced tree (typically Red-Black tree). * **Characteristics:** * **No duplicate keys.** * **Keys are stored in sorted order** (natural order or by `Comparator`). * **Performance:** O(log n) for `put`, `get`, `remove`. * Requires keys to be comparable or a `Comparator` must be provided. * **Use Case:** When unique key-value pairs are needed, and the keys must be retrieved in sorted order. ### 5.4. Hashtable * **Implementation:** Hash table. * **Characteristics:** * **Synchronized:** Thread-safe, making it slower than `HashMap`. * **Legacy class:** Generally prefer `HashMap` with explicit synchronization or `ConcurrentHashMap`. * **Does not allow `null` keys or `null` values.** * **Use Case:** Older codebases requiring thread-safe maps. ## 6. Sorting Mechanisms ### 6.1. Comparable Interface * `java.lang.Comparable`: An interface that must be implemented by objects that want to be compared to each other (i.e., sorted in their natural order). * **Key Method:** * `int compareTo(T o)`: Compares this object with the specified object for order. * Returns a **negative integer** if `this` object is less than `o`. * Returns **zero** if `this` object is equal to `o`. * Returns a **positive integer** if `this` object is greater than `o`. * **Exam Point:** Used by classes like `TreeSet` and `TreeMap` when no explicit `Comparator` is provided to define their "natural ordering". ### 6.2. Comparator Interface * `java.util.Comparator`: An interface used to define custom comparison logic between objects, overriding their natural ordering if necessary. * **Key Method:** * `int compare(T o1, T o2)`: Compares its two arguments for order. * Returns a **negative integer** if `o1` is less than `o2`. * Returns **zero** if `o1` is equal to `o2`. * Returns a **positive integer** if `o1` is greater than `o2`. * **Exam Point:** Provides flexibility to sort objects based on different criteria. Used by `Collections.sort()`, `Arrays.sort()`, and `TreeSet`/`TreeMap` constructors. **Example Usage:** * `Collections.sort(list, comparator);` * `Arrays.sort(array, comparator);` * `new TreeSet<>(comparator);` ## 7. Properties Class * `java.util.Properties`: A subclass of `Hashtable` that is used to manage configuration settings or application properties. * **Characteristics:** * Stores key-value pairs where both keys and values are **Strings**. * Can load properties from an `.properties` file (text file). * Useful for storing application configuration (e.g., database credentials, file paths). * **Key Methods:** * `String getProperty(String key)`: Gets the property with the specified key. * `String getProperty(String key, String defaultValue)`: Gets the property with the specified key. If the key is not found, returns `defaultValue`. * `void setProperty(String key, String value)`: Sets the property with the specified key. * `load(InputStream inStream)`: Loads properties from an input stream. * `store(OutputStream out, String comments)`: Writes properties to an output stream. * **Exam Point:** Essential for managing application configurations in a portable way.