Java
  • Implement custom generic collection classes and data structures
  • Create generic algorithms for sorting, searching, and manipulation
  • Build utility methods for advanced collection operations
  • Optimize collection performance and memory usage

Generic Collections Deep Dive

You know generics, type bounds, and wildcards. Time to apply them to real scenarios—building custom data structures and understanding how the Collections Framework actually works.

Understanding Collection Type Hierarchy

Here's how generics work across the collection hierarchy:

Iterable<E>
    └── Collection<E>
            ├── List<E>
            │       ├── ArrayList<E>
            │       └── LinkedList<E>
            ├── Set<E>
            │       ├── HashSet<E>
            │       └── TreeSet<E>
            └── Queue<E>
                    └── Deque<E>

Map<K,V>
    ├── HashMap<K,V>
    └── TreeMap<K,V>

Each interface and class is generic, allowing type-safe operations throughout.

Building Custom Generic Collections

A Type-Safe Stack

Let's build a stack that demonstrates key generic concepts:

public class Stack<E> {
    private Object[] elements;
    private int size = 0;
    private static final int DEFAULT_CAPACITY = 16;
    
    public Stack() {
        elements = new Object[DEFAULT_CAPACITY];
    }
    
    public void push(E element) {
        ensureCapacity();
        elements[size++] = element;
    }
    
    @SuppressWarnings("unchecked")
    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        E result = (E) elements[--size];
        elements[size] = null;  // Help garbage collection
        return result;
    }
    
    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (E) elements[size - 1];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    private void ensureCapacity() {
        if (size == elements.length) {
            elements = Arrays.copyOf(elements, 2 * size + 1);
        }
    }
}

Why Object[] instead of E[]? Due to type erasure, you can't create a generic array directly (new E[capacity] is illegal). The workaround is using Object[] with careful casting.

Adding Iteration Support

To make our stack usable in for-each loops:

public class Stack<E> implements Iterable<E> {
    // ... previous code ...
    
    @Override
    public Iterator<E> iterator() {
        return new StackIterator();
    }
    
    private class StackIterator implements Iterator<E> {
        private int current = size - 1;  // Start from top
        
        @Override
        public boolean hasNext() {
            return current >= 0;
        }
        
        @Override
        @SuppressWarnings("unchecked")
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return (E) elements[current--];
        }
    }
}

Now you can write:

Stack<String> stack = new Stack<>();
stack.push("first");
stack.push("second");
stack.push("third");

for (String item : stack) {
    System.out.println(item);  // third, second, first
}

The Pair and Tuple Pattern

Many operations return multiple values. Generic pairs and tuples solve this elegantly:

Immutable Pair

public final class Pair<A, B> {
    private final A first;
    private final B second;
    
    private Pair(A first, B second) {
        this.first = first;
        this.second = second;
    }
    
    public static <A, B> Pair<A, B> of(A first, B second) {
        return new Pair<>(first, second);
    }
    
    public A getFirst() { return first; }
    public B getSecond() { return second; }
    
    // Transform methods
    public <C> Pair<C, B> mapFirst(Function<A, C> mapper) {
        return Pair.of(mapper.apply(first), second);
    }
    
    public <C> Pair<A, C> mapSecond(Function<B, C> mapper) {
        return Pair.of(first, mapper.apply(second));
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Pair)) return false;
        Pair<?, ?> pair = (Pair<?, ?>) o;
        return Objects.equals(first, pair.first) && 
               Objects.equals(second, pair.second);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(first, second);
    }
    
    @Override
    public String toString() {
        return "(" + first + ", " + second + ")";
    }
}

Usage shows the power of type inference:

// Method returning multiple values
public Pair<User, List<Order>> getUserWithOrders(Long userId) {
    User user = userRepository.findById(userId);
    List<Order> orders = orderRepository.findByUser(userId);
    return Pair.of(user, orders);
}

// Usage
Pair<User, List<Order>> result = getUserWithOrders(123L);
User user = result.getFirst();
List<Order> orders = result.getSecond();

// Transform the pair
Pair<String, Integer> nameAndCount = result
    .mapFirst(User::getName)
    .mapSecond(List::size);

Generic Utility Methods

Type-Safe Collection Operations

public class CollectionUtils {
    
    // Find first element matching predicate
    public static <T> Optional<T> findFirst(Collection<T> collection, 
                                            Predicate<T> predicate) {
        for (T element : collection) {
            if (predicate.test(element)) {
                return Optional.of(element);
            }
        }
        return Optional.empty();
    }
    
    // Partition a collection by predicate
    public static <T> Pair<List<T>, List<T>> partition(Collection<T> collection,
                                                        Predicate<T> predicate) {
        List<T> matching = new ArrayList<>();
        List<T> nonMatching = new ArrayList<>();
        
        for (T element : collection) {
            if (predicate.test(element)) {
                matching.add(element);
            } else {
                nonMatching.add(element);
            }
        }
        
        return Pair.of(matching, nonMatching);
    }
    
    // Zip two lists together
    public static <A, B> List<Pair<A, B>> zip(List<A> listA, List<B> listB) {
        int size = Math.min(listA.size(), listB.size());
        List<Pair<A, B>> result = new ArrayList<>(size);
        
        for (int i = 0; i < size; i++) {
            result.add(Pair.of(listA.get(i), listB.get(i)));
        }
        
        return result;
    }
    
    // Create frequency map
    public static <T> Map<T, Long> frequency(Collection<T> collection) {
        Map<T, Long> result = new HashMap<>();
        for (T element : collection) {
            result.merge(element, 1L, Long::sum);
        }
        return result;
    }
}

Usage Examples

List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

// Find first even number
Optional<Integer> firstEven = CollectionUtils.findFirst(numbers, n -> n % 2 == 0);
// Optional[2]

// Partition into even and odd
Pair<List<Integer>, List<Integer>> partitioned = 
    CollectionUtils.partition(numbers, n -> n % 2 == 0);
// ([2, 4, 6, 8, 10], [1, 3, 5, 7, 9])

// Zip names and ages
List<String> names = Arrays.asList("Alice", "Bob", "Charlie");
List<Integer> ages = Arrays.asList(25, 30, 35);
List<Pair<String, Integer>> people = CollectionUtils.zip(names, ages);
// [(Alice, 25), (Bob, 30), (Charlie, 35)]

// Count word frequency
List<String> words = Arrays.asList("apple", "banana", "apple", "cherry", "banana", "apple");
Map<String, Long> wordCounts = CollectionUtils.frequency(words);
// {apple=3, banana=2, cherry=1}

Generic Comparators and Sorting

Building Flexible Comparators

public class ComparatorUtils {
    
    // Compare by extracted key
    public static <T, U extends Comparable<U>> Comparator<T> comparing(
            Function<T, U> keyExtractor) {
        return (a, b) -> keyExtractor.apply(a).compareTo(keyExtractor.apply(b));
    }
    
    // Chain comparators (then compare by)
    public static <T> Comparator<T> thenComparing(
            Comparator<T> first, 
            Comparator<T> second) {
        return (a, b) -> {
            int result = first.compare(a, b);
            return result != 0 ? result : second.compare(a, b);
        };
    }
    
    // Null-safe comparator
    public static <T> Comparator<T> nullsFirst(Comparator<T> comparator) {
        return (a, b) -> {
            if (a == null && b == null) return 0;
            if (a == null) return -1;
            if (b == null) return 1;
            return comparator.compare(a, b);
        };
    }
}

Usage:

class Person {
    String name;
    int age;
    String city;
    // constructor, getters...
}

List<Person> people = /* ... */;

// Sort by name
people.sort(ComparatorUtils.comparing(Person::getName));

// Sort by age, then by name
Comparator<Person> byAgeThenName = ComparatorUtils.thenComparing(
    ComparatorUtils.comparing(Person::getAge),
    ComparatorUtils.comparing(Person::getName)
);
people.sort(byAgeThenName);

Choosing the Right Collection

Understanding when to use which collection is crucial:

List Implementations

Implementation Best For Avoid When
ArrayList<E> Random access, iteration Frequent insertions/deletions in middle
LinkedList<E> Insertions/deletions at ends Random access by index

Set Implementations

Implementation Best For Characteristics
HashSet<E> Fast lookup, no order needed O(1) operations, unordered
LinkedHashSet<E> Fast lookup with insertion order Slightly slower than HashSet
TreeSet<E> Sorted elements O(log n) operations

Map Implementations

Implementation Best For Characteristics
HashMap<K,V> General purpose O(1) operations, unordered
LinkedHashMap<K,V> Insertion/access order Good for LRU caches
TreeMap<K,V> Sorted keys O(log n) operations

Working with Generics and Inheritance

Covariant Return Types

When overriding methods, you can return a more specific type:

interface Container<E> {
    Container<E> copy();
}

class ArrayList<E> implements Container<E> {
    @Override
    public ArrayList<E> copy() {  // More specific return type
        return new ArrayList<>(this);
    }
}

Generic Methods in Interfaces

interface Transformer<T> {
    // Regular method using class type parameter
    T transform(T input);
    
    // Generic method with its own type parameter
    <R> R transformTo(T input, Function<T, R> converter);
}

Building custom generic collections means using Object[] internally and casting carefully. Implement Iterable<E> for for-each support. Make them immutable when you can. Provide static factory methods for cleaner APIs. The Collections Framework uses all these patterns—now you know why.