# Collections Fundamentals

Course: [Java](https://www.devtutorials.ai/learn/java) · Section: Collections Framework
Source: https://www.devtutorials.ai/learn/java/collections-framework/collections-fundamentals

> See why collections beat arrays, how List, Set and Map fit into the Collections Framework, how to choose between them, and how to loop with for-each and Iterator.

Think about a kitchen.

You do not keep everything in one big box. Spoons go in a drawer with slots. Spices go on a rack, one jar per spice, no repeats. Recipes go in a book where you look them up by name. Plates go in a stack, and you take the top one first.

Each kind of storage fits a different job. Picking the right one makes cooking easier.

Java's Collections Framework is the same idea for data. It gives you ready-made containers, each built for a different job.

In simple words: a collection is a container that holds a group of objects, and the Collections Framework is Java's set of ready-made containers.

## What You Will Learn

In this lesson, you will learn:

1. Why programs need collections, and where arrays fall short.
2. What a collection and the Collections Framework are.
3. How the main interfaces fit together: `Iterable`, `Collection`, `List`, `Set` and `Map`.
4. How to choose the right collection for a job.
5. How to loop through a collection with for-each and with an `Iterator`.
6. The most common implementations: `ArrayList`, `HashSet`, `HashMap`, `Queue` and `Stack`.
7. Where collections are used in real applications.

## Start With a Working Example

Press **Run**.

```java runnable title="Three collections, three different jobs"
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        List<String> cart = new ArrayList<>();
        cart.add("Pen");
        cart.add("Notebook");
        cart.add("Pen");
        System.out.println("Cart: " + cart);

        Set<String> uniqueItems = new TreeSet<>(cart);
        System.out.println("Different items: " + uniqueItems);

        Map<String, Integer> prices = new TreeMap<>();
        prices.put("Pen", 20);
        prices.put("Notebook", 45);
        System.out.println("Price of a notebook: " + prices.get("Notebook"));
    }
}
```

Expected output:

```text
Cart: [Pen, Notebook, Pen]
Different items: [Notebook, Pen]
Price of a notebook: 45
```

The **list** keeps every item in order, even the repeated pen. The **set** keeps each item only once. The **map** looks up a price by its item name.

### Try This

Add `cart.add("Bag");` before the cart is printed. The list grows by itself. You never had to say how big it was.

## Introduction to Collections Framework

Almost every real program works with **groups** of things: students in a class, products in a shop, messages in an inbox, orders in a queue.

You have stored groups in arrays so far. Arrays are useful, but they are basic. Real programs need more:

- a list that grows when you add items;
- a group that refuses duplicates;
- a way to look up a value by a name, not a number;
- a line where the first in is the first out.

Java provides all of these in the `java.util` package, as the **Collections Framework**.

## Why Collections Are Needed

Collections save you from writing common data-handling code again and again.

Without them, every program would need its own code to:

- grow an array when it fills up;
- check for duplicates before adding;
- search for an item by a key;
- remove an item and shift everything after it.

That code is easy to get wrong. The Collections Framework gives you tested, fast versions of all of it.

## Limitations of Arrays

Arrays have four big limits.

### Fixed Size

An array's size is set when you create it. To add one more item to a full array, you must create a bigger array and copy everything across.

### No Built-in Helpers

Arrays have no methods for adding, removing or searching. You write a loop each time.

### Removing Is Awkward

To remove an item from the middle, you must shift every later item one place left yourself.

### Only Index Lookup

You find an item by its position number. You cannot look up "the price of a pen" by the word "Pen".

```java runnable title="Adding one item: array vs ArrayList"
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String[] arrayNames = {"Asha", "Ravi"};
        String[] bigger = Arrays.copyOf(arrayNames, arrayNames.length + 1);
        bigger[2] = "Meena";
        arrayNames = bigger;
        System.out.println("Array: " + Arrays.toString(arrayNames));

        List<String> listNames = new ArrayList<>(List.of("Asha", "Ravi"));
        listNames.add("Meena");
        System.out.println("List: " + listNames);

        listNames.remove("Ravi");
        System.out.println("After removing Ravi: " + listNames);
    }
}
```

Expected output:

```text
Array: [Asha, Ravi, Meena]
List: [Asha, Ravi, Meena]
After removing Ravi: [Asha, Meena]
```

The array needed a new, bigger copy just to add one name. The list needed one line, `add`. Removing a name was one more line, with no manual shifting.

| | Array | Collection |
|---|---|---|
| Size | Fixed when created | Grows and shrinks as needed |
| Add or remove | Write your own code | Built-in methods |
| Holds primitives directly? | Yes, `int[]` | No, uses wrappers like `Integer` |
| Lookup by key | No | Yes, with a `Map` |
| Prevent duplicates | No | Yes, with a `Set` |
| Printing | Needs `Arrays.toString` | Prints its items directly |

## What is a Collection?

A **collection** is an object that holds a group of other objects, called its **elements**.

A collection can usually:

- **add** elements;
- **remove** elements;
- tell you its **size**;
- tell you whether it **contains** an element;
- let you **loop** through every element.

Collections hold **objects**, not primitives. To store whole numbers, you use `Integer`, not `int`. Java converts between them automatically (autoboxing), so `list.add(5)` still works.

## What is the Collections Framework?

The **Collections Framework** is a unified set of interfaces, classes and helper methods for storing and processing groups of objects.

It has three parts:

| Part | What it is | Examples |
|---|---|---|
| **Interfaces** | Describe what each kind of collection can do | `List`, `Set`, `Map`, `Queue` |
| **Implementations** | Real classes you create objects from | `ArrayList`, `HashSet`, `HashMap`, `ArrayDeque` |
| **Algorithms** | Ready-made helper methods | `Collections.sort`, `Collections.max`, `Collections.reverse` |

The interfaces say **what**. The implementations say **how**. You usually write your variable with the interface type and create it with an implementation class:

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

Do not mix up `Collection` (no **s**), the interface, with `Collections` (with an **s**), a helper class of static methods like `Collections.sort(list)` and `Collections.max(list)`.

## Benefits of Collections Framework

- **Less code.** Adding, removing, searching and sorting are already written.
- **Fewer bugs.** The code is tested and used by millions of programs.
- **Good speed.** Each implementation is designed for fast common operations.
- **Easy to swap.** Code written against `List` works with any kind of list.
- **Shared language.** Every Java developer knows `List`, `Set` and `Map`.

## Collection Hierarchy Overview

The interfaces form a family tree.

```text
                   Iterable
                      │
                  Collection                     Map  (separate family)
          ┌───────────┼────────────┐              │
         List        Set         Queue         HashMap
          │           │            │           TreeMap
      ArrayList    HashSet       Deque         LinkedHashMap
      LinkedList   LinkedHashSet   │
                   TreeSet       ArrayDeque
                                 PriorityQueue (Queue)
```

Two things to notice:

- `List`, `Set` and `Queue` all extend `Collection`, which extends `Iterable`.
- `Map` is **not** a `Collection`. It holds **pairs** of keys and values, not single elements, so it has its own family.

## Iterable Interface

**`Iterable`** is the root of the family. It has one job: it can give you an **iterator**, an object that walks through the elements one at a time.

Anything that is `Iterable` can be used in a **for-each** loop. That is why `for (String name : names)` works on every list and set.

## Collection Interface

**`Collection`** extends `Iterable`. It adds the methods every list, set and queue shares.

| Method | What it does |
|---|---|
| `add(e)` | Adds an element |
| `remove(e)` | Removes an element |
| `size()` | Returns how many elements there are |
| `isEmpty()` | Returns `true` when there are none |
| `contains(e)` | Returns `true` if the element is present |
| `clear()` | Removes every element |
| `addAll(other)` | Adds every element from another collection |

```java runnable title="The same Collection methods on a list and a set"
import java.util.ArrayList;
import java.util.Collection;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<>();
        Collection<String> set = new TreeSet<>();

        fill(list);
        fill(set);

        System.out.println("List: " + list + ", size " + list.size());
        System.out.println("Set:  " + set + ", size " + set.size());
        System.out.println("List has Kochi? " + list.contains("Kochi"));
    }

    static void fill(Collection<String> c) {
        c.add("Pune");
        c.add("Kochi");
        c.add("Pune");
    }
}
```

Expected output:

```text
List: [Pune, Kochi, Pune], size 3
Set:  [Kochi, Pune], size 2
List has Kochi? true
```

`fill` only knows it has a `Collection`. It works on both. The list kept the duplicate `Pune`. The set refused it.

## List Interface

A **`List`** is an **ordered** collection that **allows duplicates**. Each element has an index, starting at `0`, just like an array.

Use a list when order matters, or when the same value can appear more than once.

Extra methods include `get(index)`, `set(index, value)`, `add(index, value)` and `indexOf(value)`.

Main implementations: `ArrayList` (the usual choice) and `LinkedList`.

## Set Interface

A **`Set`** holds **unique** elements. Adding a value that is already there does nothing.

Use a set when duplicates make no sense: email addresses, roll numbers or tags.

Main implementations:

- `HashSet`: fastest, but no guaranteed order;
- `LinkedHashSet`: keeps the order you added them;
- `TreeSet`: keeps them sorted.

## Map Interface

A **`Map`** stores **key-value pairs**. Each **key** is unique and points to one **value**.

Think of a dictionary. The word is the key. The meaning is the value. You look up the meaning by the word.

Main methods: `put(key, value)`, `get(key)`, `containsKey(key)`, `remove(key)` and `keySet()`.

Main implementations: `HashMap` (the usual choice), `LinkedHashMap` (keeps insertion order) and `TreeMap` (keeps keys sorted).

| Interface | Ordered? | Duplicates? | Look up by |
|---|---|---|---|
| `List` | Yes, by index | Allowed | Index |
| `Set` | Depends on the class | Not allowed | The value itself |
| `Map` | Depends on the class | Keys: no. Values: yes | Key |

## Choosing the Right Collection

### Array vs Collection

Use an **array** when the size is fixed and known, or for primitive data where speed matters, such as a grid of pixels.

Use a **collection** when the number of items changes, or when you need adding, removing, searching or sorting.

### List vs Set

Use a **list** when order matters, or duplicates are allowed. A shopping cart can hold two pens.

Use a **set** when every item must be unique. A list of registered emails must never repeat one.

### Set vs Map

Use a **set** when you only need to know **whether** something is there. "Has this student already signed up?"

Use a **map** when you need to look up **extra information** about it. "What is this student's mark?"

| Question you are asking | Use |
|---|---|
| "Give me the items in order, repeats allowed" | `List` |
| "Is this item already here?" | `Set` |
| "What value goes with this key?" | `Map` |
| "Who is next, in arrival order?" | `Queue` |
| "What was the last thing added?" | Stack (`ArrayDeque`) |

**Easy Way to Remember:** **List** = order. **Set** = unique. **Map** = lookup by key.

## Traversing Collections

**Traversing** means visiting every element once.

### for-each Loop

The for-each loop works on any `Iterable`. It is the simplest way to read every element.

```text
for (String name : names) {
    System.out.println(name);
}
```

For a `Map`, loop over its `keySet()`, its `values()`, or its `entrySet()` (key and value together).

### Iterator Introduction

An **`Iterator`** is an object that walks through a collection step by step. You get one by calling `iterator()`.

It has three main methods:

| Method | What it does |
|---|---|
| `hasNext()` | Returns `true` if there is another element |
| `next()` | Returns the next element and moves forward |
| `remove()` | Removes the element `next()` just returned |

The for-each loop actually uses an iterator behind the scenes. You use one directly when you need to **remove** elements while looping. Read the code, then look at the output below it.

```java readonly title="for-each to read, Iterator to remove safely"
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        List<Integer> marks = new ArrayList<>(List.of(72, 35, 88, 28, 64));

        for (int m : marks) {
            System.out.print(m + " ");
        }
        System.out.println();

        Iterator<Integer> it = marks.iterator();
        while (it.hasNext()) {
            int m = it.next();
            if (m < 40) {
                it.remove();
            }
        }
        System.out.println("Passing marks: " + marks);

        Map<String, Integer> stock = new TreeMap<>(Map.of("Pens", 40, "Bags", 6));
        for (Map.Entry<String, Integer> e : stock.entrySet()) {
            System.out.println(e.getKey() + " -> " + e.getValue());
        }
    }
}
```

Output:

```text
72 35 88 28 64
Passing marks: [72, 88, 64]
Bags -> 6
Pens -> 40
```

The iterator removed `35` and `28` safely, while looping.

`entrySet()` gives each key-value pair as a `Map.Entry`, so you can read both parts.

Never call `list.remove(...)` inside a for-each loop over that same list. Java detects the change and stops the program with a `ConcurrentModificationException`. Use the iterator's own `remove()`, or `list.removeIf(m -> m < 40)`.

## Common Collection Implementations

### ArrayList

A resizable list backed by an array. Fast to read by index and to add at the end. It is the most used collection in Java.

### HashSet

A set that stores elements in a **hash table**: a structure that finds items by turning them into a number. Adding, removing and checking are very fast. It does not keep any order.

### HashMap

A map that stores key-value pairs in a hash table. Looking up a value by its key is very fast. It does not keep any order either.

### Queue

A **queue** hands out elements in **first in, first out** (FIFO) order, like people in a line. Common classes are `ArrayDeque`, `LinkedList` and `PriorityQueue`.

### Stack

A **stack** hands out elements in **last in, first out** (LIFO) order, like a pile of plates. Java has an old `Stack` class. For new code, `ArrayDeque` is recommended as a stack.

```java runnable title="Five common implementations in one program"
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<String> playlist = new ArrayList<>();
        playlist.add("Song A");
        playlist.add("Song B");
        System.out.println("ArrayList first song: " + playlist.get(0));

        Set<Integer> rollNumbers = new HashSet<>();
        rollNumbers.add(101);
        rollNumbers.add(101);
        System.out.println("HashSet size after adding 101 twice: " + rollNumbers.size());

        Map<String, String> capitals = new HashMap<>();
        capitals.put("Kerala", "Thiruvananthapuram");
        System.out.println("HashMap capital of Kerala: " + capitals.get("Kerala"));

        Queue<String> line = new ArrayDeque<>();
        line.offer("Asha");
        line.offer("Ravi");
        System.out.println("Queue serves first: " + line.poll());

        Deque<String> plates = new ArrayDeque<>();
        plates.push("Plate 1");
        plates.push("Plate 2");
        System.out.println("Stack takes first: " + plates.pop());
    }
}
```

Expected output:

```text
ArrayList first song: Song A
HashSet size after adding 101 twice: 1
HashMap capital of Kerala: Thiruvananthapuram
Queue serves first: Asha
Stack takes first: Plate 2
```

The queue gave back the **first** name added. The stack gave back the **last** plate added.

| Class | Interface | Order | Duplicates | Best for |
|---|---|---|---|---|
| `ArrayList` | `List` | Insertion order | Yes | Most lists |
| `HashSet` | `Set` | No order | No | Fast "is it there?" checks |
| `HashMap` | `Map` | No order | Unique keys | Fast lookup by key |
| `ArrayDeque` | `Queue`, `Deque` | FIFO or LIFO | Yes | Queues and stacks |
| `PriorityQueue` | `Queue` | Smallest first | Yes | Jobs by priority |

You will study each of these in depth in the next three lessons.

## Collections Framework in Real-World Applications

| Application | Collection | Why |
|---|---|---|
| Online shop cart | `List` | Keeps items in order, allows two of the same item |
| User sign-up | `Set` | Stops the same email registering twice |
| Product catalogue | `Map` | Finds a product by its ID instantly |
| Customer support tickets | `Queue` | Serves the earliest ticket first |
| Text editor undo | Stack | Undoes the most recent change first |
| Hospital emergency room | `PriorityQueue` | Treats the most serious case first |
| Word counter | `Map` | Maps each word to how many times it appears |
| Leaderboard | `TreeMap` or sorted `List` | Keeps scores in order |

## Common mistakes

The following mistakes are common when starting with the Collections Framework. Each row shows what you see, why it happens and how to fix it.

| Symptom | Cause | Fix |
|---|---|---|
| `unexpected type; required: reference, found: int` | A primitive type in the angle brackets | Use the wrapper class |
| `ConcurrentModificationException` | The collection changed during a for-each loop | Use `Iterator.remove()` or `removeIf` |
| Items print in a strange order | `HashSet` or `HashMap` keeps no order | Use `LinkedHashSet`, `TreeSet` or `TreeMap` |
| `incompatible types` when using a map as a collection | `Map` does not extend `Collection` | Use the `Map` type, or its `keySet()` / `values()` |
| `cannot find symbol: class List` | `java.util` classes were not imported | Import them |

## What to Remember

- A collection holds a group of objects. The Collections Framework gives you ready-made ones in `java.util`.
- Arrays have a fixed size and no helper methods. Collections grow, shrink, search and sort.
- `Iterable` → `Collection` → `List`, `Set` and `Queue`. `Map` is a separate family.
- **List** keeps order and allows duplicates. **Set** keeps items unique. **Map** looks up values by key.
- Loop with for-each to read. Use an `Iterator` (or `removeIf`) to remove while looping.
- The most common classes are `ArrayList`, `HashSet`, `HashMap` and `ArrayDeque` (for queues and stacks).

Next: ArrayList