Collections Framework

The Collections Framework provides a unified architecture for storing, manipulating, and retrieving groups of objects. It's one of the most important parts of Java's standard library.

Why Use Collections?

Before collections, Java programmers had to use arrays, which have significant limitations:

• Fixed Size: Arrays cannot grow or shrink after creation
• No Built-in Methods: No add, remove, or search operations
• Type Safety: Arrays don't prevent mixing incompatible types at compile time

Collections solve all these problems and provide powerful, type-safe data structures.

The Hierarchy

The root interface is Collection (which extends Iterable). Note that Map is NOT part of the Collection hierarchy but is still considered part of the Collections Framework.

• Collection (extends Iterable)
  • List: Ordered sequence, allows duplicates, index-based access
    • ArrayList - Fast random access, slow insert/delete
    • LinkedList - Fast insert/delete, slow random access
  • Set: Unique elements only
    • HashSet - O(1) operations, unordered
    • TreeSet - O(log n) operations, sorted
    • LinkedHashSet - O(1) operations, insertion order
  • Queue: FIFO (First-In-First-Out) ordering
    • PriorityQueue - Elements ordered by priority
    • ArrayDeque - Double-ended queue, fast operations
• Map (Separate hierarchy): Key-Value pairs
  • HashMap - O(1) operations, unordered keys
  • TreeMap - O(log n) operations, sorted keys
  • LinkedHashMap - O(1) operations, insertion order

Key Interfaces

Interface	Description	Common Implementations
List	Ordered collection with index-based access. Allows duplicate elements.	ArrayList, LinkedList, Vector
Set	Collection with no duplicate elements. Models mathematical set abstraction.	HashSet, TreeSet, LinkedHashSet
Queue	Collection designed for holding elements prior to processing.	PriorityQueue, ArrayDeque
Map	Object that maps unique keys to values. Cannot contain duplicate keys.	HashMap, TreeMap, LinkedHashMap

Choosing the Right Collection

Time Complexity Overview

Collection	Add	Remove	Search	Access by Index
ArrayList	O(1)*	O(n)	O(n)	O(1)
LinkedList	O(1)	O(1)**	O(n)	O(n)
HashSet/HashMap	O(1)	O(1)	O(1)	N/A
TreeSet/TreeMap	O(log n)	O(log n)	O(log n)	N/A

* Amortized time (occasional resize). ** When position is known.

Common Collection Methods

All collections share these methods from the Collection interface:

// Adding elements
collection.add(element);
collection.addAll(otherCollection);

// Removing elements
collection.remove(element);
collection.removeAll(otherCollection);
collection.clear();

// Querying
collection.size();
collection.isEmpty();
collection.contains(element);

// Converting
collection.toArray();
collection.stream();  // Java 8+