Java Data Structures

Java - Collections Framework (Modern Data Structures)

Efficiently storing and manipulating groups of objects is crucial in programming. While basic arrays exist, Java provides a sophisticated and powerful set of modern data structures through the Java Collections Framework, located primarily in the java.util package.

Important Note on Legacy Classes: Older Java versions included classes like Vector, Stack, Hashtable, Dictionary, and the Enumeration interface. These are now considered legacy and should generally be avoided in new code. The modern Collections Framework offers superior performance, flexibility, and API design.

This tutorial focuses on the core concepts and commonly used components of the modern Collections Framework.

Core Interfaces of the Collections Framework

The framework is built around a set of core interfaces that define different types of collections:

• Collection<E>: The root interface representing a group of objects (elements). It defines basic operations like adding, removing, checking size, and iteration. It’s rarely used directly, but provides common ground for other interfaces.
• List<E>: An ordered collection (sequence) that allows duplicate elements. Elements can be accessed by their integer index (position). Think of it as a dynamic array. Common implementations: ArrayList, LinkedList.
• Set<E>: A collection that does not allow duplicate elements. Order is generally not guaranteed (though some implementations maintain order). Used to store unique items. Common implementations: HashSet, LinkedHashSet, TreeSet.
• Queue<E>: A collection used to hold elements prior to processing, typically following FIFO (First-In, First-Out) order. Common implementations: LinkedList, PriorityQueue.
• Deque<E>: A double-ended queue, allowing element addition/removal from both ends. Extends Queue. Common implementations: LinkedList, ArrayDeque.
• Map<K, V>: (Note: Does not extend Collection) An object that maps keys to values. Each key must be unique. Used for key-value lookups. Common implementations: HashMap, LinkedHashMap, TreeMap.

The <E>, <K>, and <V> notations represent generics, allowing you to specify the type of elements, keys, or values the collection will hold, providing type safety at compile time.

Common Implementations

You typically work with concrete classes that implement these interfaces:

ArrayList<E> (Implements List):

Uses a dynamically resizing array internally. Offers fast random access by index (get(index)). Adding/removing elements can be slower if it requires resizing or shifting elements, especially in the middle.

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

// ...

List<String> names = new ArrayList<>(); // Use Interface type for variable
names.add("Alice");
names.add("Bob");
names.add(0, "Charlie"); // Add at specific index

String secondName = names.get(1); // Access by index (gets "Alice")
System.out.println("Names: " + names); // Output: Names: [Charlie, Alice, Bob]
System.out.println("Second name: " + secondName);

LinkedList<E> (Implements List, Deque):

Uses a doubly-linked list internally. Faster for adding/removing elements at the beginning or end. Slower random access by index compared to ArrayList, as it requires traversing the list.

import java.util.LinkedList;
import java.util.List;

// ...

List<Integer> scores = new LinkedList<>();
scores.add(95);
scores.add(88);
((LinkedList<Integer>) scores).addFirst(100); // Use Deque methods via casting or Deque variable

System.out.println("Scores: " + scores); // Output: Scores: [100, 95, 88]

HashSet<E> (Implements Set):

Stores unique elements using a hash table. Offers fast add, remove, and contains operations (average O(1) time). Does not guarantee any specific order of elements.

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

// ...

Set<String> uniqueTags = new HashSet<>();
uniqueTags.add("java");
uniqueTags.add("programming");
uniqueTags.add("java"); // Duplicate, will be ignored

System.out.println("Contains 'java'? " + uniqueTags.contains("java")); // true
System.out.println("Tags: " + uniqueTags); // Output order not guaranteed, e.g., Tags: [java, programming]

LinkedHashSet<E> (Implements Set):

Similar to HashSet but maintains the insertion order of elements.

TreeSet<E> (Implements SortedSet):

Stores unique elements in a sorted order (natural ordering or using a custom Comparator). Slower for add/remove than HashSet (O(log n)).

HashMap<K, V> (Implements Map):

Stores key-value pairs using a hash table. Provides fast retrieval of a value given its key (average O(1) time). Order is not guaranteed.

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

// ...

Map<String, Integer> ageMap = new HashMap<>();
ageMap.put("Alice", 30);
ageMap.put("Bob", 25);
ageMap.put("Charlie", 35);
ageMap.put("Alice", 31); // Replaces the previous value for key "Alice"

int aliceAge = ageMap.get("Alice"); // Retrieve value by key
System.out.println("Alice's age: " + aliceAge); // Output: Alice's age: 31
System.out.println("Map contains Bob? " + ageMap.containsKey("Bob")); // true
System.out.println("Ages: " + ageMap); // Order not guaranteed

LinkedHashMap<K, V> (Implements Map):

Similar to HashMap but maintains insertion order of keys.

TreeMap<K, V> (Implements SortedMap):

Stores key-value pairs sorted by key (natural ordering or using a custom Comparator). Slower for lookups than HashMap (O(log n)).

Iterating Over Collections

You can iterate over elements in collections using several methods:

1. Enhanced for loop (Preferred for simple traversal):

List<String> fruits = List.of("Apple", "Banana", "Orange"); // Java 9+ immutable list
for (String fruit : fruits) {
    System.out.println(fruit);
}

2. Iterator:

Provides hasNext(), next(), and optionally remove() methods. Required if you need to remove elements during iteration.

import java.util.Iterator;
// ...
Set<Integer> numbers = new HashSet<>(List.of(1, 2, 3, 4, 5));
Iterator<Integer> iterator = numbers.iterator();
while (iterator.hasNext()) {
    Integer number = iterator.next();
    if (number % 2 == 0) {
        iterator.remove(); // Safely remove the current element
    }
}
System.out.println("Odd numbers: " + numbers); // Output: Odd numbers: [1, 3, 5] (order may vary)

3. Streams API (Java 8+):

Provides a powerful functional approach for processing collections (filtering, mapping, reducing, etc.).

List<String> words = List.of("Java", "Collections", "Framework", "Stream");
words.stream()
   .filter(s -> s.length() > 5) // Keep words longer than 5 chars
   .map(String::toUpperCase)    // Convert to uppercase
   .forEach(System.out::println); // Print each result
// Output:
// COLLECTIONS
// FRAMEWORK

Choosing the Right Collection

• Need an ordered list with fast index-based access? Use ArrayList.
• Need an ordered list with frequent additions/removals at the ends? Use LinkedList.
• Need to store unique elements quickly and don’t care about order? Use HashSet.
• Need unique elements stored in insertion order? Use LinkedHashSet.
• Need unique elements stored in sorted order? Use TreeSet.
• Need fast key-value lookups and don’t care about order? Use HashMap.
• Need key-value pairs stored in insertion order? Use LinkedHashMap.
• Need key-value pairs stored sorted by key? Use TreeMap.

The Java Collections Framework is extensive. Explore the java.util package documentation for more specialized collections and utility classes like Collections and Arrays.