Java Collections Framework: Lists and Data Structures Mastery

Welcome back to the Java Fundamentals series! 👋

Introduction to Java Collections Framework

The Java Collections Framework is a hierarchical set of interfaces and classes that provide common methods for storing, retrieving, and manipulating groups of objects. It's essentially a collection of data structures like lists, sets, maps, and queues.

Key Features

• Unified Architecture: Consistent API across different collection types
• High Performance: Optimized implementations for different use cases
• Interoperability: Collections can work together seamlessly
• Generic Support: Type safety with generics (since Java 5)
• Thread Safety Options: Both synchronized and unsynchronized implementations

Important Note: The Collections Framework deals with objects, not primitives. For primitives, you need to use wrapper classes (autoboxing/unboxing handles this automatically).

Core Collection Interfaces

Understanding the interface hierarchy is crucial for working effectively with collections:

Collection Hierarchy

// Interface hierarchy example
Collection<String> collection = new ArrayList<>(); // Most general
List<String> list = new ArrayList<>();             // More specific
ArrayList<String> arrayList = new ArrayList<>();   // Most specific

Understanding Lists

Lists are ordered collections that allow duplicate elements. They provide indexed access to elements and maintain the insertion order of elements.

List Interface Key Methods

public interface List<E> extends Collection<E> {
    // Positional access
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    
    // Search operations
    int indexOf(Object o);
    int lastIndexOf(Object o);
    
    // List iterators
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    
    // View operations
    List<E> subList(int fromIndex, int toIndex);
}

When to Use Lists

• When you need indexed access to elements
• When order matters and you want to maintain insertion order
• When you need to allow duplicate elements
• When you frequently access elements by position

ArrayList: Dynamic Array Implementation

ArrayList is the most commonly used List implementation. It's backed by a resizable array and provides excellent performance for most operations.

ArrayList Characteristics

• Dynamic Sizing: Automatically grows and shrinks
• Random Access: O(1) access time by index
• Insertion Order: Maintains the order of insertion
• Allows Duplicates: Same element can appear multiple times
• Not Thread-Safe: Requires external synchronization for concurrent access

Creating and Initializing ArrayLists

import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        // Different ways to create ArrayLists
        
        // 1. Empty ArrayList
        List<String> fruits = new ArrayList<>();
        
        // 2. ArrayList with initial capacity
        List<String> cities = new ArrayList<>(20);
        
        // 3. ArrayList from another collection
        List<String> colors = new ArrayList<>(Arrays.asList("Red", "Green", "Blue"));
        
        // 4. ArrayList using Collections
        List<String> numbers = new ArrayList<>(
            Collections.nCopies(5, "Zero")
        );
        
        // 5. Using List.of() (Java 9+) - Creates immutable list
        List<String> animals = new ArrayList<>(List.of("Cat", "Dog", "Bird"));
        
        System.out.println("Colors: " + colors);
        System.out.println("Numbers: " + numbers);
        System.out.println("Animals: " + animals);
    }
}

Adding Elements

public class ArrayListAddOperations {
    public static void main(String[] args) {
        List<String> students = new ArrayList<>();
        
        // Adding elements at the end
        students.add("Alice");
        students.add("Bob");
        students.add("Charlie");
        System.out.println("After adding: " + students);
        
        // Adding element at specific index
        students.add(1, "David"); // Insert at index 1
        System.out.println("After inserting David: " + students);
        
        // Adding multiple elements
        students.addAll(Arrays.asList("Eve", "Frank"));
        System.out.println("After adding multiple: " + students);
        
        // Adding collection at specific index
        students.addAll(2, Arrays.asList("Grace", "Henry"));
        System.out.println("Final list: " + students);
    }
}

Output:

After adding: [Alice, Bob, Charlie]
After inserting David: [Alice, David, Bob, Charlie]
After adding multiple: [Alice, David, Bob, Charlie, Eve, Frank]
Final list: [Alice, David, Grace, Henry, Bob, Charlie, Eve, Frank]

Accessing and Updating Elements

public class ArrayListAccessOperations {
    public static void main(String[] args) {
        List<String> languages = new ArrayList<>(
            Arrays.asList("Java", "Python", "C++", "JavaScript", "Go")
        );
        
        // Accessing elements
        System.out.println("First language: " + languages.get(0));
        System.out.println("Last language: " + languages.get(languages.size() - 1));
        
        // Safe access with bounds checking
        int index = 2;
        if (index >= 0 && index < languages.size()) {
            System.out.println("Language at index " + index + ": " + languages.get(index));
        }
        
        // Updating elements
        String oldValue= languages.set(1, "Kotlin");
        System.out.println("Replaced '" + oldValue + "' with 'Kotlin'");
        System.out.println("Updated list: " + languages);
        
        // Getting list size and checking if empty
        System.out.println("List size: " + languages.size());
        System.out.println("Is empty: " + languages.isEmpty());
    }
}

Removing Elements

public class ArrayListRemoveOperations {
    public static void main(String[] args) {
        List<String> items = new ArrayList<>(
            Arrays.asList("Apple", "Banana", "Orange", "Apple", "Grape")
        );
        
        System.out.println("Original list: " + items);
        
        // Remove by value (removes first occurrence)
        boolean removed = items.remove("Apple");
        System.out.println("Removed 'Apple': " + removed);
        System.out.println("After removing by value: " + items);
        
        // Remove by index
        String removedItem = items.remove(1); // Remove "Orange"
        System.out.println("Removed item at index 1: " + removedItem);
        System.out.println("After removing by index: " + items);
        
        // Remove multiple elements
        items.removeAll(Arrays.asList("Apple", "Grape"));
        System.out.println("After removing multiple: " + items);
        
        // Remove with condition (Java 8+)
        List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
        numbers.removeIf(n -> n % 2 == 0); // Remove even numbers
        System.out.println("After removing even numbers: " + numbers);
        
        // Clear all elements
        items.clear();
        System.out.println("After clearing: " + items);
    }
}

Searching Operations

public class ArrayListSearchOperations {
    public static void main(String[] args) {
        List<String> books = new ArrayList<>(Arrays.asList(
            "1984", "To Kill a Mockingbird", "The Great Gatsby", 
            "1984", "Pride and Prejudice", "The Catcher in the Rye"
        ));
        
        // Check if element exists
        System.out.println("Contains '1984': " + books.contains("1984"));
        System.out.println("Contains 'Hamlet': " + books.contains("Hamlet"));
        
        // Find first occurrence
        int firstIndex = books.indexOf("1984");
        System.out.println("First occurrence of '1984' at index: " + firstIndex);
        
        // Find last occurrence
        int lastIndex = books.lastIndexOf("1984");
        System.out.println("Last occurrence of '1984' at index: " + lastIndex);
        
        // Check if all/any elements match condition
        boolean allBooksHaveTitle = books.stream().allMatch(book -> book.length() > 0);
        System.out.println("All books have titles: " + allBooksHaveTitle);
        
        boolean hasLongTitle = books.stream().anyMatch(book -> book.length() > 15);
        System.out.println("Has book with title > 15 chars: " + hasLongTitle);
        
        // Find elements matching condition
        List<String> longTitles = books.stream()
            .filter(book -> book.length() > 10)
            .collect(ArrayList::new, ArrayList::add, ArrayList::addAll);
        System.out.println("Books with long titles: " + longTitles);
    }
}

Iterating Through ArrayLists

import java.util.*;

public class ArrayListIterationMethods {
    public static void main(String[] args) {
        List<String> countries = new ArrayList<>(Arrays.asList(
            "USA", "Canada", "Mexico", "Brazil", "Argentina"
        ));
        
        System.out.println("=== Different Iteration Methods ===");
        
        // 1. Enhanced for loop (for-each)
        System.out.println("1. Enhanced for loop:");
        for (String country : countries) {
            System.out.println("  " + country);
        }
        
        // 2. Traditional for loop with index
        System.out.println("\n2. Traditional for loop:");
        for (int i = 0; i < countries.size(); i++) {
            System.out.println("  " + i + ": " + countries.get(i));
        }
        
        // 3. Iterator
        System.out.println("\n3. Using Iterator:");
        Iterator<String> iterator = countries.iterator();
        while (iterator.hasNext()) {
            String country = iterator.next();
            System.out.println("  " + country);
            // Can safely remove during iteration
            if (country.equals("Mexico")) {
                iterator.remove();
            }
        }
        System.out.println("After removing Mexico: " + countries);
        
        // 4. ListIterator (bidirectional)
        System.out.println("\n4. Using ListIterator (backwards):");
        ListIterator<String> listIterator = countries.listIterator(countries.size());
        while (listIterator.hasPrevious()) {
            System.out.println("  " + listIterator.previous());
        }
        
        // 5. forEach with lambda (Java 8+)
        System.out.println("\n5. forEach with lambda:");
        countries.forEach(country -> System.out.println("  " + country.toUpperCase()));
        
        // 6. Streams (Java 8+)
        System.out.println("\n6. Using Streams:");
        countries.stream()
            .map(String::toLowerCase)
            .forEach(country -> System.out.println("  " + country));
    }
}

Working with Collections Utility Class

The Collections class provides many static utility methods for working with collections.

Sorting Operations

import java.util.*;

public class CollectionsSortingDemo {
    public static void main(String[] args) {
        // Sorting strings
        List<String> names = new ArrayList<>(Arrays.asList(
            "Charlie", "Alice", "Bob", "David", "Eve"
        ));
        
        System.out.println("Original: " + names);
        
        // Natural ordering sort
        Collections.sort(names);
        System.out.println("Sorted ascending: " + names);
        
        // Custom comparator - descending
        Collections.sort(names, Collections.reverseOrder());
        System.out.println("Sorted descending: " + names);
        
        // Sort by length
        Collections.sort(names, Comparator.comparing(String::length));
        System.out.println("Sorted by length: " + names);
        
        // Sorting numbers
        List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9, 3));
        System.out.println("\nOriginal numbers: " + numbers);
        
        Collections.sort(numbers);
        System.out.println("Sorted numbers: " + numbers);
        
        // Custom sorting with lambda
        Collections.sort(numbers, (a, b) -> b.compareTo(a)); // Descending
        System.out.println("Sorted descending: " + numbers);
        
        // Sorting custom objects
        List<Person> people = Arrays.asList(
            new Person("Alice", 30),
            new Person("Bob", 25),
            new Person("Charlie", 35)
        );
        
        Collections.sort(people, Comparator.comparing(Person::getAge));
        System.out.println("\nSorted by age: " + people);
    }
    
    static class Person {
        private String name;
        private int age;
        
        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }
        
        public String getName() { return name; }
        public int getAge() { return age; }
        
        @Override
        public String toString() {
            return name + "(" + age + ")";
        }
    }
}

Other Collections Utility Methods

public class CollectionsUtilityDemo {
    public static void main(String[] args) {
        List<String> items = new ArrayList<>(Arrays.asList(
            "A", "B", "C", "D", "E"
        ));
        
        System.out.println("Original list: " + items);
        
        // Reverse the list
        Collections.reverse(items);
        System.out.println("Reversed: " + items);
        
        // Shuffle randomly
        Collections.shuffle(items);
        System.out.println("Shuffled: " + items);
        
        // Reset for other operations
        items = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E"));
        
        // Rotate elements
        Collections.rotate(items, 2);
        System.out.println("Rotated by 2: " + items);
        
        // Swap elements
        Collections.swap(items, 0, 4);
        System.out.println("Swapped 0 and 4: " + items);
        
        // Fill with same value
        Collections.fill(items, "X");
        System.out.println("Filled with X: " + items);
        
        // Working with numbers for min/max
        List<Integer> numbers = Arrays.asList(5, 2, 8, 1, 9, 3);
        System.out.println("\nNumbers: " + numbers);
        System.out.println("Min: " + Collections.min(numbers));
        System.out.println("Max: " + Collections.max(numbers));
        
        // Replace all occurrences
        List<String> words = new ArrayList<>(Arrays.asList(
            "hello", "world", "hello", "java", "hello"
        ));
        Collections.replaceAll(words, "hello", "hi");
        System.out.println("After replacing 'hello' with 'hi': " + words);
        
        // Binary search (list must be sorted)
        List<Integer> sortedNumbers = Arrays.asList(1, 3, 5, 7, 9, 11, 13);
        int index = Collections.binarySearch(sortedNumbers, 7);
        System.out.println("Index of 7 in sorted list: " + index);
        
        // Frequency count
        List<String> letters = Arrays.asList("a", "b", "c", "a", "b", "a");
        int frequency = Collections.frequency(letters, "a");
        System.out.println("Frequency of 'a': " + frequency);
    }
}

ArrayList Performance Analysis

Understanding the time complexity of ArrayList operations is crucial for writing efficient code.

Time Complexity Table

Performance Demonstration

import java.util.*;

public class ArrayListPerformanceDemo {
    public static void main(String[] args) {
        // Demonstrate different performance characteristics
        
        // Test 1: Adding at end vs middle
        System.out.println("=== Performance Test: Adding Elements ===");
        testAddPerformance();
        
        // Test 2: Access patterns
        System.out.println("\n=== Performance Test: Access Patterns ===");
        testAccessPerformance();
        
        // Test 3: Removal patterns
        System.out.println("\n=== Performance Test: Removal Patterns ===");
        testRemovalPerformance();
    }
    
    private static void testAddPerformance() {
        int size = 100000;
        
        // Adding at end - O(1) amortized
        List<Integer> list1 = new ArrayList<>();
        long startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            list1.add(i);
        }
        long endTime= System.nanoTime();
        System.out.println("Adding at end: " + (endTime - startTime) / 1_000_000 + " ms");
        
        // Adding at beginning - O(n) for each operation
        List<Integer> list2 = new ArrayList<>();
        startTime = System.nanoTime();
        for (int i = 0; i < 1000; i++) { // Smaller size due to O(n²) complexity
            list2.add(0, i);
        }
        endTime= System.nanoTime();
        System.out.println("Adding at beginning (1000 elements): " + (endTime - startTime) / 1_000_000 + " ms");
    }
    
    private static void testAccessPerformance() {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 100000; i++) {
            list.add(i);
        }
        
        // Random access - O(1)
        Random random= new Random();
        long startTime= System.nanoTime();
        for (int i= 0; i < 10000; i++) {
            int index= random.nextInt(list.size());
            int value= list.get(index);
        }
        long endTime= System.nanoTime();
        System.out.println("Random access (10000 operations): " + (endTime - startTime) / 1_000_000 + " ms");
    }
    
    private static void testRemovalPerformance() {
        // Remove from end
        List<Integer> list1 = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            list1.add(i);
        }
        
        long startTime= System.nanoTime();
        while (!list1.isEmpty()) {
            list1.remove(list1.size() - 1);
        }
        long endTime= System.nanoTime();
        System.out.println("Removing from end: " + (endTime - startTime) / 1_000_000 + " ms");
        
        // Remove from beginning
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < 1000; i++) { // Smaller size due to O(n²) complexity
            list2.add(i);
        }
        
        startTime= System.nanoTime();
        while (!list2.isEmpty()) {
            list2.remove(0);
        }
        endTime= System.nanoTime();
        System.out.println("Removing from beginning (1000 elements): " + (endTime - startTime) / 1_000_000 + " ms");
    }
}

LinkedList: Doubly-Linked List Implementation

LinkedList is another implementation of the List interface, based on a doubly-linked list data structure.

LinkedList Characteristics

• Node-based Structure: Elements stored in nodes with pointers
• Dynamic Size: No need to declare size beforehand
• Efficient Insertion/Deletion: O(1) at ends, O(n) in middle
• Sequential Access: O(n) for random access
• Memory Overhead: Extra memory for storing pointers

LinkedList vs ArrayList

import java.util.*;

public class LinkedListVsArrayList {
    public static void main(String[] args) {
        // Creating LinkedList
        List<String> linkedList = new LinkedList<>();
        List<String> arrayList = new ArrayList<>();
        
        // Adding elements
        linkedList.addAll(Arrays.asList("First", "Second", "Third"));
        arrayList.addAll(Arrays.asList("First", "Second", "Third"));
        
        System.out.println("LinkedList: " + linkedList);
        System.out.println("ArrayList: " + arrayList);
        
        // LinkedList specific methods (when using LinkedList reference)
        LinkedList<String> specificLinkedList = new LinkedList<>();
        specificLinkedList.addFirst("Beginning");
        specificLinkedList.addLast("End");
        specificLinkedList.add("Middle");
        
        System.out.println("LinkedList with specific methods: " + specificLinkedList);
        
        // Queue-like operations
        specificLinkedList.offer("Queue Item"); // Add to end
        System.out.println("After offer: " + specificLinkedList);
        
        String polled = specificLinkedList.poll(); // Remove from beginning
        System.out.println("Polled item: " + polled);
        System.out.println("After poll: " + specificLinkedList);
        
        // Stack-like operations
        specificLinkedList.push("Stack Item"); // Add to beginning
        System.out.println("After push: " + specificLinkedList);
        
        String popped = specificLinkedList.pop(); // Remove from beginning
        System.out.println("Popped item: " + popped);
        System.out.println("After pop: " + specificLinkedList);
    }
}

When to Choose LinkedList vs ArrayList

public class ListChoiceGuideline {
    public static void main(String[] args) {
        System.out.println("=== ArrayList vs LinkedList Guidelines ===\n");
        
        System.out.println("Choose ArrayList when:");
        System.out.println("✓ Frequent random access by index");
        System.out.println("✓ More reads than writes");
        System.out.println("✓ Memory efficiency is important");
        System.out.println("✓ Cache performance matters");
        System.out.println("✓ Simple operations (get, set)");
        
        System.out.println("\nChoose LinkedList when:");
        System.out.println("✓ Frequent insertion/deletion at beginning or middle");
        System.out.println("✓ Queue or stack-like operations");
        System.out.println("✓ Size varies significantly");
        System.out.println("✓ Memory allocation is dynamic");
        System.out.println("✓ Iterator-based processing");
        
        // Performance comparison example
        comparePerformance();
    }
    
    private static void comparePerformance() {
        System.out.println("\n=== Performance Comparison ===");
        
        int size = 10000;
        
        // Test insertion at beginning
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        
        // ArrayList - inserting at beginning
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            arrayList.add(0, i);
        }
        long arrayListTime= System.nanoTime() - start;
        
        // LinkedList - inserting at beginning
        start= System.nanoTime();
        for (int i= 0; i < size; i++) {
            linkedList.add(0, i);
        }
        long linkedListTime= System.nanoTime() - start;
        
        System.out.printf("Insertion at beginning (%d elements):\n", size);
        System.out.printf("ArrayList: %.2f ms\n", arrayListTime / 1_000_000.0);
        System.out.printf("LinkedList: %.2f ms\n", linkedListTime / 1_000_000.0);
        
        // Test random access
        start= System.nanoTime();
        for (int i= 0; i < 1000; i++) {
            arrayList.get(i % arrayList.size());
        }
        arrayListTime= System.nanoTime() - start;
        
        start= System.nanoTime();
        for (int i= 0; i < 1000; i++) {
            linkedList.get(i % linkedList.size());
        }
        linkedListTime= System.nanoTime() - start;
        
        System.out.printf("\nRandom access (1000 operations):\n");
        System.out.printf("ArrayList: %.2f ms\n", arrayListTime / 1_000_000.0);
        System.out.printf("LinkedList: %.2f ms\n", linkedListTime / 1_000_000.0);
    }
}

Best Practices and Common Patterns

1. Safe List Operations

import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;

public class SafeListOperations {
    public static void main(String[] args) {
        // Safe iteration and modification
        demonstrateSafeIteration();
        
        // Null safety
        demonstrateNullSafety();
        
        // Thread safety
        demonstrateThreadSafety();
        
        // Immutable lists
        demonstrateImmutableLists();
    }
    
    private static void demonstrateSafeIteration() {
        System.out.println("=== Safe Iteration ===");
        
        List<String> items = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E"));
        
        // WRONG: Modifying list during for-each iteration
        // This will throw ConcurrentModificationException
        try {
            for (String item : items) {
                if (item.equals("C")) {
                    items.remove(item); // Don't do this!
                }
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("Error: " + e.getClass().getSimpleName());
        }
        
        // CORRECT: Using Iterator for safe removal
        items = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E"));
        Iterator<String> iterator = items.iterator();
        while (iterator.hasNext()) {
            String item = iterator.next();
            if (item.equals("C")) {
                iterator.remove(); // Safe removal
            }
        }
        System.out.println("After safe removal: " + items);
        
        // CORRECT: Using removeIf (Java 8+)
        items = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E"));
        items.removeIf(item -> item.equals("C"));
        System.out.println("After removeIf: " + items);
        
        // CORRECT: Iterating backwards for removal by index
        items = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E"));
        for (int i = items.size() - 1; i >= 0; i--) {
            if (items.get(i).equals("C")) {
                items.remove(i);
            }
        }
        System.out.println("After backward iteration removal: " + items);
    }
    
    private static void demonstrateNullSafety() {
        System.out.println("\n=== Null Safety ===");
        
        List<String> items = new ArrayList<>(Arrays.asList("A", null, "C", null, "E"));
        System.out.println("List with nulls: " + items);
        
        // Safe null checking
        for (String item : items) {
            if (item != null) {
                System.out.println("Non-null item: " + item);
            }
        }
        
        // Remove nulls safely
        items.removeIf(Objects::isNull);
        System.out.println("After removing nulls: " + items);
        
        // Safe operations with potentially null lists
        List<String> possiblyNullList = null;
        List<String> safeList = Optional.ofNullable(possiblyNullList)
                                        .orElse(new ArrayList<>());
        System.out.println("Safe list size: " + safeList.size());
    }
    
    private static void demonstrateThreadSafety() {
        System.out.println("\n=== Thread Safety ===");
        
        // Thread-safe alternatives
        List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());
        List<String> copyOnWriteList = new CopyOnWriteArrayList<>();
        
        // Vector (legacy but thread-safe)
        List<String> vector = new Vector<>();
        
        System.out.println("Thread-safe list types created successfully");
        
        // Note: Even with synchronized lists, you need external synchronization
        // for iteration in multi-threaded environments
    }
    
    private static void demonstrateImmutableLists() {
        System.out.println("\n=== Immutable Lists ===");
        
        // Java 9+ List.of() - immutable
        List<String> immutableList = List.of("A", "B", "C");
        System.out.println("Immutable list: " + immutableList);
        
        // Collections.unmodifiableList() - view of mutable list
        List<String> mutableList = new ArrayList<>(Arrays.asList("X", "Y", "Z"));
        List<String> unmodifiableView = Collections.unmodifiableList(mutableList);
        System.out.println("Unmodifiable view: " + unmodifiableView);
        
        // The original list can still be modified
        mutableList.add("W");
        System.out.println("After modifying original: " + unmodifiableView);
        
        // Arrays.asList() - fixed-size list
        List<String> fixedSizeList = Arrays.asList("P", "Q", "R");
        System.out.println("Fixed-size list: " + fixedSizeList);
        // fixedSizeList.add("S"); // Would throw UnsupportedOperationException
    }
}

2. Performance Optimization Tips

public class ListPerformanceOptimization {
    public static void main(String[] args) {
        // Tip 1: Use appropriate initial capacity
        demonstrateInitialCapacity();
        
        // Tip 2: Bulk operations
        demonstrateBulkOperations();
        
        // Tip 3: Appropriate list type selection
        demonstrateListTypeSelection();
        
        // Tip 4: Memory optimization
        demonstrateMemoryOptimization();
    }
    
    private static void demonstrateInitialCapacity() {
        System.out.println("=== Initial Capacity Optimization ===");
        
        int expectedSize = 10000;
        
        // Without initial capacity - multiple resizing operations
        long start = System.nanoTime();
        List<Integer> list1 = new ArrayList<>();
        for (int i = 0; i < expectedSize; i++) {
            list1.add(i);
        }
        long time1= System.nanoTime() - start;
        
        // With initial capacity - no resizing needed
        start= System.nanoTime();
        List<Integer> list2 = new ArrayList<>(expectedSize);
        for (int i = 0; i < expectedSize; i++) {
            list2.add(i);
        }
        long time2= System.nanoTime() - start;
        
        System.out.printf("Without initial capacity: %.2f ms\n", time1 / 1_000_000.0);
        System.out.printf("With initial capacity: %.2f ms\n", time2 / 1_000_000.0);
        System.out.printf("Improvement: %.1fx faster\n", (double) time1 / time2);
    }
    
    private static void demonstrateBulkOperations() {
        System.out.println("\= Bulk Operations=");
        
        List<Integer> source = Arrays.asList(1, 2, 3, 4, 5);
        
        // Individual additions
        long start = System.nanoTime();
        List<Integer> list1 = new ArrayList<>();
        for (Integer item : source) {
            list1.add(item);
        }
        long time1 = System.nanoTime() - start;
        
        // Bulk addition
        start = System.nanoTime();
        List<Integer> list2 = new ArrayList<>();
        list2.addAll(source);
        long time2 = System.nanoTime() - start;
        
        // Constructor with collection
        start = System.nanoTime();
        List<Integer> list3 = new ArrayList<>(source);
        long time3 = System.nanoTime() - start;
        
        System.out.printf("Individual additions: %d ns\n", time1);
        System.out.printf("Bulk addAll(): %d ns\n", time2);
        System.out.printf("Constructor: %d ns\n", time3);
    }
    
    private static void demonstrateListTypeSelection() {
        System.out.println("\n=== List Type Selection ===");
        
        // For frequent access operations - use ArrayList
        List<Integer> accessList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
        
        // For frequent insertion/deletion - consider the position
        LinkedList<Integer> insertionList = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
        
        // Demonstrate why position matters
        System.out.println("Choose ArrayList for: frequent get/set operations");
        System.out.println("Choose LinkedList for: frequent add/remove at ends");
        System.out.println("Both are similar for: sequential iteration");
    }
    
    private static void demonstrateMemoryOptimization() {
        System.out.println("\n=== Memory Optimization ===");
        
        // Trim to size after bulk operations
        List<Integer> list = new ArrayList<>(1000);
        for (int i = 0; i < 100; i++) {
            list.add(i);
        }
        
        System.out.println("List size: " + list.size());
        
        // Trim excess capacity
        if (list instanceof ArrayList) {
            ((ArrayList<Integer>) list).trimToSize();
            System.out.println("Trimmed to size for memory efficiency");
        }
        
        // Use appropriate collection size
        List<String> smallList = new ArrayList<>(4); // For small, known-size lists
        List<String> mediumList = new ArrayList<>(16); // For medium lists
        List<String> largeList = new ArrayList<>(100); // For large lists
        
        System.out.println("Created lists with appropriate initial capacities");
    }
}

3. Common Use Cases and Patterns

import java.util.*;
import java.util.stream.Collectors;

public class CommonListPatterns {
    public static void main(String[] args) {
        // Pattern 1: List as a buffer/queue
        demonstrateListAsBuffer();
        
        // Pattern 2: List transformations
        demonstrateListTransformations();
        
        // Pattern 3: List filtering and searching
        demonstrateListFiltering();
        
        // Pattern 4: List partitioning
        demonstrateListPartitioning();
    }
    
    private static void demonstrateListAsBuffer() {
        System.out.println("=== List as Buffer/Queue ===");
        
        List<String> buffer = new ArrayList<>();
        
        // Producer adds items
        buffer.add("Item 1");
        buffer.add("Item 2");
        buffer.add("Item 3");
        System.out.println("Buffer after adding: " + buffer);
        
        // Consumer processes items
        while (!buffer.isEmpty()) {
            String item = buffer.remove(0); // Remove from front
            System.out.println("Processing: " + item);
        }
        System.out.println("Buffer after processing: " + buffer);
    }
    
    private static void demonstrateListTransformations() {
        System.out.println("\n=== List Transformations ===");
        
        List<String> names = Arrays.asList("alice", "bob", "charlie", "david");
        
        // Transform to uppercase
        List<String> upperNames = names.stream()
            .map(String::toUpperCase)
            .collect(Collectors.toList());
        System.out.println("Uppercase names: " + upperNames);
        
        // Transform to lengths
        List<Integer> nameLengths = names.stream()
            .map(String::length)
            .collect(Collectors.toList());
        System.out.println("Name lengths: " + nameLengths);
        
        // Transform to Person objects
        List<Person> people = names.stream()
            .map(name -> new Person(name, name.length() * 5)) // Mock age
            .collect(Collectors.toList());
        System.out.println("People: " + people);
    }
    
    private static void demonstrateListFiltering() {
        System.out.println("\n=== List Filtering ===");
        
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
        
        // Filter even numbers
        List<Integer> evenNumbers = numbers.stream()
            .filter(n -> n % 2 == 0)
            .collect(Collectors.toList());
        System.out.println("Even numbers: " + evenNumbers);
        
        // Filter and transform
        List<String> evenSquares = numbers.stream()
            .filter(n -> n % 2 == 0)
            .map(n -> "Square of " + n + " = " + (n * n))
            .collect(Collectors.toList());
        System.out.println("Even squares: " + evenSquares);
        
        // Find first match
        Optional<Integer> firstEven = numbers.stream()
            .filter(n -> n % 2 == 0)
            .findFirst();
        firstEven.ifPresent(n -> System.out.println("First even number: " + n));
        
        // Check conditions
        boolean allPositive = numbers.stream().allMatch(n -> n > 0);
        boolean anyGreaterThan5 = numbers.stream().anyMatch(n -> n > 5);
        System.out.println("All positive: " + allPositive);
        System.out.println("Any greater than 5: " + anyGreaterThan5);
    }
    
    private static void demonstrateListPartitioning() {
        System.out.println("\n=== List Partitioning ===");
        
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
        
        // Partition into even and odd
        Map<Boolean, List<Integer>> partitioned = numbers.stream()
            .collect(Collectors.partitioningBy(n -> n % 2 == 0));
        
        System.out.println("Even numbers: " + partitioned.get(true));
        System.out.println("Odd numbers: " + partitioned.get(false));
        
        // Group by remainder when divided by 3
        Map<Integer, List<Integer>> grouped = numbers.stream()
            .collect(Collectors.groupingBy(n -> n % 3));
        
        System.out.println("Grouped by remainder (mod 3): " + grouped);
        
        // Split list into chunks
        List<List<Integer>> chunks = partition(numbers, 3);
        System.out.println("Chunks of size 3: " + chunks);
    }
    
    // Utility method to partition list into chunks
    private static <T> List<List<T>> partition(List<T> list, int chunkSize) {
        List<List<T>> chunks = new ArrayList<>();
        for (int i = 0; i < list.size(); i = chunkSize) {
            chunks.add(list.subList(i, Math.min(i + chunkSize, list.size())));
        }
        return chunks;
    }
    
    static class Person {
        private String name;
        private int age;
        
        public Person(String name, int age) {
            this.name= name;
            this.age= age;
        }
        
        @Override
        public String toString() {
            return name + "(" + age + ")";
        }
    }
}

Best Practices Summary

1. Interface Programming

// ✅ Good - program to interface
List<String> list = new ArrayList<>();

// ❌ Avoid - programming to implementation
ArrayList<String> list = new ArrayList<>();

2. Initialization Best Practices

// ✅ Good - with initial capacity when size is known
List<String> list = new ArrayList<>(expectedSize);

// ✅ Good - immutable list for constants
List<String> constants = List.of("RED", "GREEN", "BLUE");

// ✅ Good - defensive copying
public List<String> getItems() {
    return new ArrayList<>(internalList); // Return copy
}

3. Iteration Safety

// ✅ Good - safe removal during iteration
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (shouldRemove(it.next())) {
        it.remove();
    }
}

// ✅ Good - using removeIf for conditional removal
list.removeIf(this::shouldRemove);

4. Null Safety

// ✅ Good - null checking
if (list != null && !list.isEmpty()) {
    // Process list
}

// ✅ Good - using Optional
Optional.ofNullable(list)
    .orElse(Collections.emptyList())
    .forEach(this::process);

5. Performance Considerations

// ✅ Good - appropriate list type for use case
List<String> frequentAccess = new ArrayList<>(); // For get/set operations
List<String> frequentInserts = new LinkedList<>(); // For add/remove at ends

// ✅ Good - bulk operations
list.addAll(otherList); // Instead of individual adds

// ✅ Good - pre-sizing when possible
List<String> list = new ArrayList<>(knownSize);

Conclusion

• ArrayList: Best for frequent access operations and when memory efficiency matters
• LinkedList: Optimal for frequent insertion/deletion operations, especially at ends
• Collections Utility: Provides powerful utility methods for sorting, searching, and manipulating lists
• Performance Awareness: Understanding time complexity helps in choosing the right operations
• Best Practices: Always program to interfaces, handle null safely, and choose appropriate collection types

Happy coding! 💻