# Java Collections

Java Collections holds data structures that represent any group of individual objects. The Collection interface `java.util.Collection` and Map interface `.java.util.Map` are the two main *root* interfaces of Java collection classes.


## Java Framework

A framework is a set of classes and interfaces with read-made architecture to implement a new feature or class easily. This gives some benefits:

- Consistent API
- basic set of interfaces like Collection, Set, List, or Map
- reduce redundant effort to design collections from scratch
- increases program speed and standardized quality
- simply use the best implementation of a specific data structure

## Class vs Interface

### Class

Class is a user-defined blueprint to create objects. It represents set of properties or methods common to all objects of one type

### Interface

Interface can have methods and variables, but the methods declared in are **by default abstract.** Interface specify what a class must do and now how.

## Primitive Data Type vs Wrapper Objects

| Primitive Data Type | Wrapper Class |
| - | - |
| byte | Byte |
| short | Short |
| int | Integer |
| long | Long |
| float | Float |
| double | Double |
| boolean | Boolean |
| char | Character |

The main difference between these is that the wrapper class treat primitives as objects that we can use in Collection objects which are called generic types. We normally pass wrapper objects as parameters to a method

Other differences include:
- Comparisons
- primitives use `==`
- wrapper classes use `.equals()` method
- Storage Allocation
- primitives sizes are significantly smaller than wrapper objects
- Initialization
- declaring wrapper objects without assigning values are initialized as `null` while this is not the same for primitives
- useful to send `null` parameters into a method / constructor to indicate state / function, able to throw a `NullPointerException` when something is being used incorrectly

## List, Set, Queue, Map

### List

List interface is the child interface of the collection interface to store **ordered collections of objects which are particularly useful for ordered data and allows duplicates.** This interface is implemented by ArrayList, Vector, Stack, etc. We can instantiate a list object with any of these classes.

**ArrayList - Dynamic Arrays**

Not to be confused with linked lists and arrays, ArrayList refers to a array that can be dynamically expanded and scaled. The size of an ArrayList is increased automatically if the collection grows opr shrinks if the objects are removed from the collection. This is useful since traditional array sizes cannot be modified once declared.

However, ArrayList cannot be used for primitive types (`int`, `char`, etc). A wrapper class is necessary for such cases. **ArrayList is not thread-safe is because it is not synchronized, multiple concurrent threads cannot structurally access an ArrayList.** To make ArrayLists thread-safe we must perform external synchronization to lock the collection when it's enumerating data.

Note that ArrayList accepts `null` values but it is not recommended. Since `null` doesn't mean anything, pointing to the value, without proper exception handling, throws a null pointer exception, causing difficulties to maintain the program.

import java.io.*;
import java.util.*;

class CFG {

    // Main Method
    public static void main(String[] args)
    {
        ArrayList<Integer> al = new ArrayList<Integer>();

        for (int i = 1; i <= 5; i++)
            al.add(i);

        // Printing elements
        System.out.println(al);

        al.remove(3);
        System.out.println(al);

        for (int i = 0; i < al.size(); i++)
            System.out.print(al.get(i) + " ");
        for (Integer i : al){
            System.out.println(i);
        }
    }
}

**LinkedList - Collections Implementation of a Doubly Linked List**

LinkedList provides the implementation of a linked list data structure. Fairly straightforward, it's syntax is similar to ArrayList:

import java.util.*;

class main{
    public static void main(String args[]){
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 1; i < 6; i++){
            list.add(i);
        }
        System.out.println(list);
        for (int i = 0; i < list.size(); i++){
            System.out.println(list.get(i));
        }
        for(Integer i : list){
            System.out.println(i);
        }
    }
}

**Vector - Dynamic Arrays (Synchronized)**

Vector is a synchronized dynamic array which makes it thread-safe. It's an old implementation of the list interface. Hence, we recommend newer practices such as implementing concurrent collections like `ConcurrentHashMap`, `CopyOnWriteArrayList`, etc, or externally synchronize collections that are not thread-safe to allow multi-threading operations.

**Stack**

Stack implements the Last-In-First-Out (LIFO) principle that is from the vector class where we can access and operate using push, pop, search and peek. This implementation is also considered legacy. Stack is replaced with `ArrayDequeue` which is also not thread-safe but provides faster implementation.

### Queue

Queue interface adopts the First-In-First-Out (FIFO) principle to store elements where the order matters. This means u can only insert one element on one side of the queue and delete it from the other side.

**Priority Queue - Process Objects Based on Priority through Priority Heap**

Priority Queue is the most frequently used implementation of the queue interface. The element position is closely related to its corresponding priority value.

- This data structure uses **Binary Heap**
- Element insertion and deletion take $O(\log n)$ time by shifting through the binary tree
- not thread-safe, doesn't allow `null` and `non-comparable` objects
- allows `Comparator` to define priority values

import java.util.*;

class GfG {

    // Main Method
    public static void main(String args[])
    {
        // Creating empty priority queue
        PriorityQueue<Integer> pQueue
                = new PriorityQueue<Integer>();

        // Adding items to the pQueue using add()
        pQueue.add(10);
        pQueue.add(20);
        pQueue.add(15);

        // Printing the top element of PriorityQueue
        System.out.println(pQueue.peek());

        // Printing the top element and removing it
        // from the PriorityQueue container
        // removes 10 and updates 15 to the top of the binary heap
        System.out.println(pQueue.poll());

        // Printing the top element again
        System.out.println(pQueue.peek());
    }
}

**ArrayDeque - Double-ended Queue**

In Deque we can insert and remove elements from both ends of the queue. Not to be confused with LinkedList, here is a quick comparison of both classes:

| ArrayDeque | LinkedList |
| - | - |
| Arrays with pointers pointing to top and end | Uses doubly linked list data structures |
| doesn't support `null` | supports `null` |
| JDK 1.6 | JDK 1.2 |
| better for queue implementations | not recommended for queues |

import java.util.*;
class ArrayDequeDemo {
    public static void main(String[] args)
    {
        // Initializing an deque
        ArrayDeque<Integer> de_que
                = new ArrayDeque<Integer>(10);

        // add() method to insert
        de_que.add(10);
        de_que.add(20);
        de_que.add(30);
        de_que.add(40);
        de_que.add(50);

        System.out.println(de_que);

        // clear() method
        de_que.clear();

        // addFirst() method to insert the
        // elements at the head
        de_que.addFirst(564);
        de_que.addFirst(291);

        // addLast() method to insert the
        // elements at the tail
        de_que.addLast(24);
        de_que.addLast(14);

        System.out.println(de_que);

        de_que.removeFirst();

        System.out.println(de_que);

        de_que.removeLast();

        System.out.println(de_que);
    }
}

### Map

The map interface represents key-value collection types such as hash maps, hash tables (redundant), dictionaries, etc. Note that a map contains unique keys which makes it efficient to access data.

- each key can map to at most one value
- order of a map depends on specific implementations

**HashMap - Key-Value Pairs**

HashMap implements hashing which is to convert large String to a small String while retaining the same String. This is due to shorter values that help in indexing and faster searches. Accessing value requires a key:

import java.util.*;

class CFG {

    // Main Method
    public static void main(String[] args) {
        HashMap<String, Integer> empIDS = new HashMap<>();
        empIDS.put("John", 123);
        empIDS.put("Jane", 456);

        System.out.println(empIDS);
        // putting in a same key but different value overrides the current one in the hashmap
        empIDS.put("John", 321);
        System.out.println(empIDS);

        // replace does it similarly but if the key doesn't exist in the first place it does nothing
        empIDS.replace("John", 789);
        empIDS.replace("Someone", 123);
        System.out.println(empIDS);

        // returns boolean value
        System.out.println(empIDS.containsKey("John"));
        System.out.println(empIDS.containsValue(001));

        // get value through key
        System.out.println(empIDS.get("John"));

        // put new key and value only if it doesn't exist in the hashmap
        empIDS.putIfAbsent("John", 001); // value of John doesn't change bc the key is already in the hashmap
        empIDS.putIfAbsent("Someone", 789);
        System.out.println(empIDS);
    }
}

**Loops on Hashmap**

import java.util.*;

class GFG {

    // Main driver method
    public static void main(String[] args)
    {

        // Creating an empty HashMap
        Map<String, Integer> map = new HashMap<>();

        // Inserting entries in the Map
        // using put() method
        map.put("vishal", 10);
        map.put("sachin", 30);
        map.put("vaibhav", 20);

        // Iterating over Map
        for (Map.Entry<String, Integer> e : map.entrySet())

            // Printing key-value pairs
            System.out.println(e.getKey() + " "
                    + e.getValue());
    }
}

| Collection/Class | Thread Safe? | Synchronized by Default? | Multi-threading Notes |
|---------------------------------|-----------------------|--------------------------|------------------------------------------------------------------------------------------------------|
| **ArrayList** | No | No | Not thread-safe. Can use `Collections.synchronizedList(...)` or `CopyOnWriteArrayList` for thread safety. |
| **LinkedList** | No | No | Same as `ArrayList`—must synchronize externally or use other concurrent collections when accessed by multiple threads. |
| **Vector** | Yes (legacy) | Yes | All operations synchronized. However, performance can degrade in multi-threaded access. Typically replaced by newer concurrent classes. |
| **Stack** (subclass of Vector) | Yes (legacy) | Yes | Like `Vector`, operations are synchronized. Often replaced by `Deque` implementations for better concurrency. |
| **HashSet** | No | No | Not synchronized. Use `Collections.synchronizedSet(...)` or a concurrent alternative like `ConcurrentSkipListSet`. |
| **LinkedHashSet** | No | No | Same concurrency notes as `HashSet`. |
| **TreeSet** | No | No | Must synchronize externally if used by multiple threads. `ConcurrentSkipListSet` is a thread-safe alternative. |
| **CopyOnWriteArrayList** | Yes | Internal mechanism | Safe for concurrent reads; modifies by copying the entire list. Best for mostly-read scenarios. |
| **CopyOnWriteArraySet** | Yes | Internal mechanism | Similar to `CopyOnWriteArrayList`; iterators do not throw `ConcurrentModificationException`. |
| **HashMap** | No | No | Not synchronized. Use `ConcurrentHashMap` or `Collections.synchronizedMap(...)` for multi-threaded access. |
| **LinkedHashMap** | No | No | Same concurrency notes as `HashMap`. |
| **TreeMap** | No | No | Must synchronize externally. `ConcurrentSkipListMap` is a thread-safe alternative. |
| **Hashtable** (legacy) | Yes (legacy) | Yes | Synchronized, but considered obsolete for new designs; replaced by `ConcurrentHashMap` in most cases. |
| **ConcurrentHashMap** | Yes | Lock-striping | High-performance concurrent map. Operations are thread-safe without global locking. |
| **ConcurrentSkipListMap** | Yes | Lock-free/Lock-based mix | Sorted, concurrent map. Provides scalable concurrent access and maintains sorted order. |
| **ConcurrentSkipListSet** | Yes | Lock-free/Lock-based mix | Uses `ConcurrentSkipListMap` internally to provide a concurrent sorted set. |
| **PriorityQueue** | No | No | Not synchronized. Must synchronize externally for concurrent use, or use alternative concurrent queue implementations (e.g., `PriorityBlockingQueue`). |