Day 6 Programming (JAVA COLLECTIONS)

SumeetSumeet
15 min read

It's better to understand the fundamentals of DSA before diving into Java collections.

Data Structures: They define how data is organized and stored. This impacts how efficiently you can access, insert, and delete elements within that structure.

Algorithms: These are the specific instructions for manipulating data. They determine how to:

  • Search: Find a particular element within a data structure (e.g., linear search, binary search).

  • Sort: Arrange elements in a specific order (e.g., bubble sort, merge sort).

  • Manipulate: Perform operations like inserting, deleting, updating, and traversing elements within a data structure.

Java Collections: These are pre-built implementations of common data structures in the Java language. They provide:

  • Convenience: Ready-to-use structures like lists, sets, and maps.

  • Efficiency: Often optimized implementations of common operations.

  • Flexibility: You can use them directly or as building blocks for your own algorithms.

In essence:

  • Data Structures provide the "containers" for your data.

  • Algorithms provide the "recipes" for how to work with that data within those containers.

  • Java Collections offer a set of pre-made, high-quality containers that you can use in your Java programs.

When I first started with collections, I found it confusing and overwhelming. This image illustrates the key classes and interfaces that I believe highlight the essential concepts and techniques of Java collections. Let’s go through them one by one.

What are Java Collections?

Java Collections are a framework that provides a set of classes and interfaces to store and manage groups of objects efficiently. Think of them as powerful tools to work with data, like lists, sets, and maps, instead of creating everything from scratch.

What are Classes?

Classes serve as blueprints for creating objects in Java.

What are Interfaces?

Collection interfaces define the contracts for different types of data structures like lists, sets, queues, and maps.(Note: The interfaces mentioned in previous blog and interfaces mentioned in java collection are different from each other.)

Key Differences:

AspectGeneral InterfaceCollection Interface
PurposeDefine a contract for any class to implement.Define specific data structure behaviors.
ScopeBroad and applicable to any domain.Narrow, focused on data collections.
Packagejava.lang (default) or custom packages.java.util package.
ExamplesRunnable, Comparable, Serializable.List, Set, Map, Queue.
UsageTo define behaviors unrelated to collections.To work with collections of objects.

What is the Collection Interface?

  • The Collection interface defines a general set of methods that all types of collections (like lists, sets, and queues) must implement.

  • It acts as a superinterface for more specific collection types like:

    • List (e.g., ArrayList, LinkedList)

    • Set (e.g., HashSet, TreeSet)

    • Queue (e.g., PriorityQueue, LinkedList)

Common Methods:

  • All classes that implement the Collection interface provide the following common functionalities:

    • Add elements: add(E e)

    • Remove elements: remove(Object o)

    • Check size: size()

    • Check if empty: isEmpty()

    • Clear all elements: clear()

    • Check if contains an element: contains(Object o)

    • Iterate through elements: Using an Iterator.

No Direct Implementation:

  • You don’t directly use the Collection interface. Instead, you use its subinterfaces (like List, Set, etc.) that provide more specific behaviors.

Array List

An ArrayList in Java is a resizable array from the java.util package. Unlike regular arrays, it can grow and shrink dynamically as you add or remove elements.

Key Features

  1. Dynamic Size:

    • Automatically adjusts its size when elements are added or removed.

    • You don't need to know the size in advance.

  2. Indexed Access:

    • Allows access to elements using an index, just like an array.

  3. Allows Duplicates:

    • You can store duplicate elements in an ArrayList.

  4. Maintains Order:

    • Elements are stored and retrieved in the order they were added.

  5. Generic:

    • You can specify the type of elements to store (e.g., ArrayList<String> for Strings).
import java.util.*;

public class CollectionExample {
    public static void main(String[] args) {
        // Using ArrayList (a List implementation)
        Collection<String> fruits = new ArrayList<>();

        // Add elements
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");

        // Check if a collection contains an element
        System.out.println("Does the collection contain Banana? " + fruits.contains("Banana"));

        // Iterate over elements
        System.out.println("Fruits in the collection:");
        for (String fruit : fruits) {
            System.out.println(fruit);
        }

        // Remove an element
        fruits.remove("Banana");
        System.out.println("After removing Banana: " + fruits);

        // Check the size of the collection
        System.out.println("Number of fruits: " + fruits.size());
    }
}

 // Iterate over elements for each , for loop and iterator

        System.out.println("Fruits in the collection:");
        for (String fruit : fruits) {
            System.out.println(fruit);
        }

 // Iterate over elements using for loop
        System.out.println("Fruits in the collection:");
        for (int i = 0; i < fruits.size(); i++) {  // Fixed condition to i < fruits.size()
            System.out.println("Element in the array is: " + fruits.get(i));  // Use get() method
        }

Iterator

you can use an Iterator instead of a for loop and for-each loop to iterate over the elements of the list. The Iterator is a part of the Java Collection Framework and provides a way to traverse collections element by element.

Key Methods in Iterator

  1. hasNext():

    • Returns true if there are more elements to iterate over.

  2. next():

    • Returns the next element in the collection.

  3. remove():

    • Removes the last element returned by the next() method from the collection. (This should be used carefully as it modifies the collection during iteration.)
import java.util.*;

public class CollectionExample {
    public static void main(String[] args) {
        // Using ArrayList (a List implementation)
        List<String> fruits = new ArrayList<>();  // Change type to List<String>

        // Add elements
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");

        // Check if a collection contains an element
        System.out.println("Does the collection contain Banana? " + fruits.contains("Banana"));

        // Iterate over elements using an Iterator
        System.out.println("Fruits in the collection:");
        Iterator<String> iterator = fruits.iterator();
        while (iterator.hasNext()) { // Check if there is another element
            String fruit = iterator.next(); // Get the next element
            System.out.println("Element in the array is: " + fruit);
        }

        // Remove an element
        fruits.remove("Banana");
        System.out.println("After removing Banana: " + fruits);

        // Check the size of the collection
        System.out.println("Number of fruits: " + fruits.size());
    }
}

Why Use an Iterator?

  • Iterators provide a generic way to traverse any type of collection, whether it’s a List, Set, or Map.

  • With an Iterator, you can avoid index-based traversal, making the code more flexible for non-indexed collections like Set.

  • Iterators support safe removal of elements while iterating, which can avoid ConcurrentModificationException.

List → LinkedList

A LinkedList in Java is a part of the java.util package and implements both the List and Deque interfaces. It represents a doubly-linked list, where each element (node) contains a reference to the previous and next element.

Key Features

  1. Dynamic Size:

    • Grows or shrinks as elements are added or removed (no fixed size).

  2. Efficient Insertions/Deletions:

    • Adding or removing elements at the beginning or middle is faster compared to an ArrayList (no shifting required).

  3. Maintains Order:

    • Elements are stored and retrieved in the order they were added.

  4. Doubly-Linked Nodes:

    • Each node points to the previous and next node.

  5. Can Be Used as a Queue or Stack:

    • Supports operations from the Deque interface, like addFirst, addLast, removeFirst, and removeLast.
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // Create a LinkedList
        LinkedList<String> fruits = new LinkedList<>();

        // Add elements
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.addFirst("Cherry"); // Adds at the beginning
        fruits.addLast("Date");   // Adds at the end

        // Print elements
        System.out.println(fruits); // Output: [Cherry, Apple, Banana, Date]

        // Access elements
        System.out.println(fruits.get(1)); // Output: Apple

        // Remove elements
        fruits.removeFirst(); // Removes Cherry
        fruits.removeLast();  // Removes Date
        System.out.println(fruits); // Output: [Apple, Banana]

        // Check size
        System.out.println(fruits.size()); // Output: 2
    }
}

Why Use LinkedList?

  • Best for scenarios where frequent insertions/deletions in the middle or beginning are required.

List → Stack

A Stack in Java is a last-in, first-out (LIFO) collection that allows you to store elements and retrieve them in the reverse order of their addition.

Key Features:

  1. LIFO Order: The last element added is the first one to be removed.

  2. Push and Pop Operations:

    • Push: Adds an element to the top of the stack.

    • Pop: Removes and returns the element from the top of the stack.

  3. Peek: Retrieves (but doesn't remove) the element at the top of the stack.

  4. Empty Check: You can check if the stack is empty with isEmpty().

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("Apple");
        stack.push("Banana");

        System.out.println(stack.peek());  // Output: Banana

        System.out.println(stack.pop());  // Output: Banana
        System.out.println(stack.pop());  // Output: Apple
    }
}

Set

The Set interface in Java is part of the java.util package and represents a collection that does not allow duplicate elements. It models a mathematical set and ensures that no two elements in the collection are the same.

Key Features:

  1. No Duplicates:
    A Set does not allow duplicate elements. If you try to add an element that already exists, it won’t be added.

  2. Unordered Collection:
    The elements in a Set are unordered, meaning they do not maintain the order in which they were added (except in specific implementations like LinkedHashSet).

  3. Basic Operations:

    • Add: Adds an element to the set (if not already present).

    • Remove: Removes a specific element from the set.

    • Contains: Checks if a specific element exists in the set.

    • Size: Returns the number of elements in the set.

    • Clear: Removes all elements from the set.

Common Implementations of Set:

  1. HashSet:

    • Stores elements in an unordered way and uses hashing for fast access.

    • Best for general-purpose use when you don’t need ordering.

  2. LinkedHashSet:

    • Maintains the insertion order (the order in which elements were added) while still preventing duplicates.

  3. TreeSet:

    • Stores elements in sorted order according to their natural ordering or a comparator.
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Apple");  // Duplicate, will not be added
        set.remove("Apple"); // Remove Elements:Apple
        System.out.println(set.contains("Banana"));  //Check if Element Exists = true
        System.out.println(set.size());  // Number of elements


        System.out.println(fruits);  // Output: [Banana]
        set.clear();  // Removes all elements

    }
}

When to Use Set:

  • Use a Set when you need to store a unique collection of elements and don't care about the order.
    Great for things like storing unique IDs or usernames.

Queue

The Queue interface in Java is part of the java.util package and represents a collection designed for holding elements prior to processing. It follows a first-in, first-out (FIFO) order, meaning the first element added to the queue will be the first one to be removed.

Key Features of Queue:

  1. FIFO Order:
    The first element inserted is the first one to be removed, like a queue in real life (e.g., a line at a checkout counter).

  2. Operations:

    • Offer: Adds an element to the queue (if possible).

    • Poll: Retrieves and removes the front element of the queue.

    • Peek: Retrieves but doesn't remove the front element.

    • Is Empty: Checks if the queue is empty.

    • Size: Returns the number of elements in the queue.

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        // Add elements
        queue.offer("Apple");
        queue.offer("Banana");

        // Retrieve and remove the front element
        System.out.println(queue.poll());  // Output: Apple

        // Retrieve front element without removal
        System.out.println(queue.peek());  // Output: Banana

        //Check if Queue is Empty
        boolean isEmpty = queue.isEmpty();  // Returns true or false


        System.out.println(queue.size());  // Returns the number of elements



    }
}

ArrayDeque.

ArrayDeque is a class in Java that implements the Queue interface and also the Deque (Double-Ended Queue) interface. It provides a resizable array-based implementation of a queue with efficient insertions and deletions from both ends.

Key Features of ArrayDeque:

  1. FIFO Order:
    Like other queues, ArrayDeque follows the first-in, first-out (FIFO) order for basic queue operations (add, remove).

  2. Double-Ended Operations:
    As a Deque, it allows adding and removing elements from both ends of the queue (front and back), making it more flexible than a regular queue.

  3. Resizable Array:
    It uses an array internally that grows automatically when needed, providing efficient performance for operations.

  4. Fast Operations:

    • O(1) time complexity for adding or removing elements from both ends of the deque (when there is no resizing).
import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();

        // Add elements to the end and front
        deque.offer("Apple");
        deque.offer("Banana");
        deque.offerFirst("Watermelon");  // Adds to the front
        String front = deque.peek();  // Retrieves but does not remove from the front
        String last = deque.peekLast();  // Retrieves but does not remove from the end



        // Remove and retrieve elements
        System.out.println(deque.poll());       // Output: Watermelon (removed from the front)
        System.out.println(deque.pollLast());   // Output: Banana (removed from the end)
    }
}

When to Use ArrayDeque:

  • Use ArrayDeque when you need:

    1. Efficient queue operations (FIFO).

    2. Both ends manipulation (insertion and removal from both ends).

    3. Dynamic resizing for flexible array-based storage.


PriorityQueue

The PriorityQueue class in Java is a part of the Queue interface, and it represents a queue where elements are ordered based on their priority rather than their insertion order. It uses a binary heap for internal storage.

Key Features of PriorityQueue:

  1. Priority-Based Ordering:

    • By default, elements are ordered in natural order (e.g., numerical order for numbers or alphabetical order for strings).

    • You can customize the order using a Comparator.

  2. No Guaranteed FIFO Order:
    Unlike a regular queue, the order of elements in the PriorityQueue depends on their priority, not the order in which they were added.

  3. Efficient Operations:

    • Adding (offer) and removing (poll) elements both have a time complexity of O(log n).

  4. Does Not Allow Null Elements:

    • Null values are not permitted in a PriorityQueue.
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Add elements
        pq.offer(10);
        pq.offer(5);
        pq.offer(15);

        // Remove elements based on priority
        System.out.println(pq.poll());  // Output: 5 (smallest element)
        System.out.println(pq.peek()); // Output: 10 (next smallest element)
    }
}

Map

The Map interface in Java represents a collection that maps keys to values. It is used when you want to store and access data as key-value pairs.

Key Features of Map:

  1. Key-Value Pair Storage:

    • Each key is unique, but values can be duplicated.

    • A key can map to only one value.

  2. No Iteration Order Guarantee:

    • The order of keys is not guaranteed unless using specific implementations like LinkedHashMap.

  3. Efficient Lookup:

    • Maps allow quick access to values using keys, with operations like put, get, and containsKey.

  4. Common Implementations:

    • HashMap: Fast and does not maintain order.

    • LinkedHashMap: Maintains insertion order.

    • TreeMap: Maintains keys in sorted order.

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

public class Main {
    public static void main(String[] args) {
        // Create a Map
        Map<String, Integer> map = new HashMap<>();

        // Add key-value pairs
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);

        // Retrieve a value
        System.out.println("Alice's age: " + map.get("Alice")); // Output: 25

        // Check if a key exists
        System.out.println("Contains Bob? " + map.containsKey("Bob")); // Output: true

        // Remove a key-value pair
        map.remove("Charlie");

        // Iterate over keys and values
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

HashMap

HashMap is a Map implementation that uses a hash table to store key-value pairs. It provides constant-time performance (O(1)) for basic operations like adding, removing, and retrieving elements.

Key Features:

  1. No Order Guarantee:

    • The order of keys is unpredictable and may change over time.

  2. Allows Null Keys/Values:

    • Allows one null key and multiple null values.

  3. Fast for Most Use Cases:

    • Ideal for cases where order does not matter, and you need fast lookups.
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);

        System.out.println("Alice's age: " + map.get("Alice"));  // Output: 25
        System.out.println("Contains Bob? " + map.containsKey("Bob")); // Output: true
    }
}

  • When to Use:
    Use HashMap when:

    • You don't care about the order of keys.

    • Performance is a priority (e.g., lookups and inserts).

TreeMap

TreeMap is a Map implementation that uses a red-black tree to store key-value pairs. It maintains the keys in sorted order (natural or custom).

  • Key Features:

    1. Sorted Order:

      • Keys are sorted naturally (e.g., alphabetical for strings, ascending for numbers) or by a custom comparator.

    2. No Null Keys:

      • Does not allow null keys but allows multiple null values.

    3. Moderate Performance:

      • Operations like adding, removing, and retrieving take O(log n) time due to the tree structure.
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>();

        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);

        System.out.println("First key: " + map.firstKey());  // Output: Alice
        System.out.println("Sorted Map: " + map);  // Output: {Alice=25, Bob=30, Charlie=35}
    }
}

  • When to Use:
    Use TreeMap when:

    • You need the keys in sorted order.

    • You want to navigate through a range of keys (e.g., headMap, tailMap).

LinkedHashMap

LinkedHashMap is a Map implementation that combines the features of a HashMap and a doubly-linked list. It maintains the insertion order of keys, making it predictable while still offering efficient operations.

Key Features:

  1. Maintains Order:

    • Preserves the order in which key-value pairs were added.

    • You can also configure it to maintain access order (i.e., order of most recently accessed keys).

  2. Efficient Operations:

    • Similar performance to HashMap for adding, removing, and retrieving elements (O(1)).

  3. Allows Nulls:

    • Allows one null key and multiple null values, like HashMap.

  4. Predictable Iteration:

    • Iterating over a LinkedHashMap will always return elements in the order they were inserted (or accessed, if configured).
import java.util.LinkedHashMap;

public class Main {
    public static void main(String[] args) {
        // Create a LinkedHashMap
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

        // Add key-value pairs
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);

        // Iterate in insertion order
        System.out.println("LinkedHashMap in insertion order:");
        for (String key : map.keySet()) {
            System.out.println(key + " -> " + map.get(key));
        }

        // Access a key (for access-order example)
        map.get("Alice"); // Access Alice

        // Display map after access (access order doesn't affect default behavior)
        System.out.println("\nAfter accessing 'Alice': " + map);
    }
}

When to Use:

  • When you need predictable iteration order of keys.

  • When implementing access-based caches (e.g., using LinkedHashMap with access order).

0
Subscribe to my newsletter

Read articles from Sumeet directly inside your inbox. Subscribe to the newsletter, and don't miss out.

java collections

Written by

Sumeet
Sumeet

Skilled in managing carrier-grade ISP infrastructure, enterprise environments, and server operations. Enthusiastic about optimizing high-performance networks and exploring emerging technologies. Committed to continuous learning and driven to leverage cloud solutions and automation tools to enhance innovation and efficiency.