Collections and Generics

Arrays are powerful but fixed in size. Java's Collections Framework provides dynamic, resizable data structures — lists, sets, maps, and queues. Generics add type safety so collections only hold the types you specify.

---

The Collections Hierarchy

Iterable
  └── Collection
        ├── List      (ordered, allows duplicates)
        ├── Set       (no duplicates)
        └── Queue     (FIFO ordering)

Map (key-value pairs — separate hierarchy)

---

List

A List is an ordered collection that allows duplicates.

ArrayList

import java.util.ArrayList;
import java.util.List;

List<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.add("Alice");  // duplicates allowed

System.out.println(names);        // [Alice, Bob, Alice]
System.out.println(names.get(0)); // Alice
System.out.println(names.size()); // 3

names.remove("Alice");            // removes first occurrence
System.out.println(names);        // [Bob, Alice]

Common List Methods

Method	Description
add(element)	Appends to the end
add(index, element)	Inserts at the specified index
get(index)	Returns element at index
set(index, element)	Replaces element at index
remove(index) or remove(object)	Removes an element
size()	Number of elements
contains(object)	Check if element exists
indexOf(object)	First index of element (-1 if not found)
isEmpty()	True if no elements
sort(comparator)	Sorts the list

ArrayList vs LinkedList

Feature	ArrayList	LinkedList
Backed by	Resizable array	Doubly linked list
Random access	O(1) — fast	O(n) — slow
Insert/delete at ends	O(1) amortized	O(1)
Insert/delete in middle	O(n)	O(1) if you have the node
Best for	Most use cases	Frequent insertions/deletions

Tip: Use ArrayList by default. Switch to LinkedList only if profiling shows it is faster for your specific workload.

---

Set

A Set contains no duplicate elements.

HashSet

import java.util.HashSet;
import java.util.Set;

Set<String> colours = new HashSet<>();
colours.add("Red");
colours.add("Green");
colours.add("Red");  // ignored — already exists

System.out.println(colours);       // [Red, Green] (order not guaranteed)
System.out.println(colours.size()); // 2

Set Implementations

Implementation	Ordering	Null allowed?	Performance
HashSet	No order	Yes (one null)	O(1) add/remove/contains
LinkedHashSet	Insertion order	Yes (one null)	O(1) with ordering overhead
TreeSet	Sorted (natural or custom)	No	O(log n)

---

Map

A Map stores key-value pairs. Keys are unique.

HashMap

import java.util.HashMap;
import java.util.Map;