Java: Collections Framework

The Java Collections Framework (JCF) is a unified architecture for storing, manipulating, and processing groups of objects.

It provides a rich set of interfaces, implementations, and algorithms that eliminate the need to build custom data structures for common use cases.

Collection Hierarchy

The Collections Framework is organized around a small set of core interfaces.

Map does not extend the Collection interface because it stores key-value pairs rather than individual elements.

Collection Interface

The Collection interface defines common operations supported by most collections.

Collection<String> names = new ArrayList<>();

names.add("John");
names.remove("John");
names.contains("John");
names.size();
names.isEmpty();
names.clear();

Most collection implementations inherit these operations.

List

A List represents an ordered collection that allows duplicate elements. Implementations include:

- ArrayList
- LinkedList
- Vector

Lists preserve insertion order and provide positional access.

ArrayList

ArrayList is backed by a dynamically resizable array.

List<String> names = new ArrayList<>();

names.add("Alice");
names.add("Bob");

System.out.println(names.get(0));

Characteristics:

- Maintains insertion order.
- Allows duplicates.
- Allows null elements.
- Provides fast random access.
- Insertion or deletion in the middle requires shifting elements.

Average time complexity:

- Access: O(1)
- Search: O(n)
- Insert at end: O(1) amortized
- Insert/Delete middle: O(n)

LinkedList

LinkedList is implemented as a doubly linked list.

LinkedList<Integer> list = new LinkedList<>();

list.addFirst(10);
list.addLast(20);

Characteristics:

- Maintains insertion order.
- Allows duplicates.
- Efficient insertion and deletion at both ends.
- Sequential access.
- Random access is inefficient.

Average time complexity:

- Access: O(n)
- Insert/Delete beginning: O(1)
- Insert/Delete middle: O(n)

ArrayList vs LinkedList

Choose ArrayList when reads significantly outnumber modifications and frequent indexed access is required.

Choose LinkedList when insertions and deletions occur primarily at the beginning or end of the collection. For most applications, ArrayList remains the preferred choice due to better cache locality and lower memory overhead.

Vector

Vector is a legacy synchronized implementation similar to ArrayList.

Vector<Integer> vector = new Vector<>();

Vector synchronizes every operation, resulting in additional overhead. For modern applications, prefer ArrayList unless synchronization is explicitly required.

Stack

Stack is a legacy class extending Vector.

Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.pop();
stack.peek();

Modern applications should prefer Deque implementations such as ArrayDeque.

Set

A Set stores unique elements. Implementations include:

- HashSet
- LinkedHashSet
- TreeSet

Duplicates are automatically rejected.

HashSet

HashSet stores elements using a hash table.

Set<String> cities = new HashSet<>();

cities.add("Delhi");
cities.add("Mumbai");
cities.add("Delhi");

Characteristics:

- No duplicate elements.
- No ordering guarantee.
- Allows one null element.

Average complexity:

- Add: O(1)
- Remove: O(1)
- Contains: O(1)

Performance depends on good implementations of hashCode() and equals().

LinkedHashSet

LinkedHashSet extends HashSet by maintaining insertion order.

Set<Integer> values = new LinkedHashSet<>();

Internally it combines a hash table with a doubly linked list. Iteration order matches insertion order.

TreeSet

TreeSet stores elements in sorted order.

TreeSet<Integer> numbers = new TreeSet<>();

numbers.add(30);
numbers.add(10);
numbers.add(20);

Output:

[10, 20, 30]

TreeSet uses a Red-Black Tree. Null elements are not permitted.

Average complexity:

- Insert: O(log n)
- Remove: O(log n)
- Search: O(log n)

Queue

A Queue generally follows the FIFO principle. Common implementations include:

- LinkedList
- PriorityQueue
- ArrayDeque

PriorityQueue

PriorityQueue orders elements according to natural ordering or a comparator.

PriorityQueue<Integer> queue = new PriorityQueue<>();

queue.offer(30);
queue.offer(10);
queue.offer(20);

System.out.println(queue.poll());

Output:

The head is always the highest-priority element. Internally implemented using a binary heap.

Deque

Deque supports insertion and removal from both ends. The preferred implementation is ArrayDeque.

Deque<Integer> deque = new ArrayDeque<>();

deque.addFirst(10);
deque.addLast(20);
deque.removeFirst();
deque.removeLast();

ArrayDeque is generally faster than Stack and LinkedList for stack and queue operations.

Map

A Map stores unique keys associated with values. Implementations include:

- HashMap
- LinkedHashMap
- TreeMap
- Hashtable

Maps do not implement the Collection interface.

HashMap

HashMap is the most commonly used map implementation.

Map<Integer, String> employees = new HashMap<>();

employees.put(1, "John");
employees.put(2, "Alice");
System.out.println(employees.get(1));

Characteristics:

- Unique keys.
- Allows one null key.
- Allows multiple null values.
- No ordering guarantee.

Average complexity:

- Put: O(1)
- Get: O(1)
- Remove: O(1)

Since Java 8, buckets containing many collisions are converted into balanced trees to improve worst-case lookup performance.

LinkedHashMap

LinkedHashMap preserves insertion order.

Map<Integer, String> map = new LinkedHashMap<>();

It is commonly used when predictable iteration order is required. It also supports access-order iteration, making it useful for implementing LRU caches.

TreeMap

TreeMap stores entries in sorted key order. Internally uses a Red-Black Tree.

TreeMap<Integer, String> map = new TreeMap<>();

Average complexity:

- Put: O(log n)
- Get: O(log n)
- Remove: O(log n)

Null keys are not allowed.

Hashtable

Hashtable is a legacy synchronized map.

Hashtable<Integer, String> table = new Hashtable<>();

Hashtable does not allow null keys or null values. Modern applications generally prefer HashMap or ConcurrentHashMap.

Comparable

Comparable defines the natural ordering of objects.

class Employee implements Comparable<Employee> {
    int id;

    @Override
    public int compareTo(Employee other) {
        return Integer.compare(id, other.id);
    }
}

Only one natural ordering can exist for a class.

Comparator

Comparator provides external sorting logic.

Comparator<Employee> comparator =
        Comparator.comparing(Employee::getName);

Multiple comparators can exist for the same class. Comparators are preferred when sorting by different attributes.

Sorting Collections

Collections can be sorted using the Collections utility class.

Collections.sort(numbers);

Collections.sort(employees, comparator);

Or using the List API.

employees.sort(comparator);

Iterator

An Iterator provides sequential access to collection elements.

Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

Iterator supports safe removal during iteration.

iterator.remove();

ListIterator

ListIterator extends Iterator. It supports:

- Forward traversal.
- Backward traversal.
- Element replacement.
- Insertion.
- Removal.

It is available only for List implementations.

Fail-Fast Iterators

Most collection iterators are fail-fast. Structural modification outside the iterator causes ConcurrentModificationException.

for (String name : names) {
    names.remove(name);
}

Use the iterator's own remove() method instead.

Immutable Collections

Java provides immutable collection factories.

List<Integer> numbers = List.of(1, 2, 3);
Set<String> names = Set.of("A", "B");
Map<Integer, String> map = Map.of(
        1, "One",
        2, "Two"
);

Attempts to modify these collections throw UnsupportedOperationException.

Collections Utility Class

The Collections utility class provides algorithms for collections.

Collections.sort(list);
Collections.reverse(list);
Collections.shuffle(list);
Collections.binarySearch(list, value);
Collections.min(list);
Collections.max(list);
Collections.frequency(list, value);
Collections.unmodifiableList(list);

Choosing the Right Collection

- Use ArrayList for most ordered collections with frequent reads.
- Use LinkedList only when frequent insertions or removals occur at the ends.
- Use HashSet for fast uniqueness checks.
- Use LinkedHashSet when insertion order matters.
- Use TreeSet when sorted data is required.
- Use HashMap for fast key-value lookups.
- Use LinkedHashMap when predictable iteration order or LRU behavior is needed.
- Use TreeMap when sorted keys are required.
- Use PriorityQueue for priority-based processing.
- Use ArrayDeque for stack or queue implementations.

Final Notes

The Collections Framework provides optimized implementations for the most common data structures required in Java applications. Selecting the appropriate collection depends on requirements such as ordering, uniqueness, lookup performance, insertion and deletion patterns, sorting, memory usage, and thread-safety.