Mastering Java Collections From Basics to Expert Proficiency (William Smith) (Z-Library)

Mastering Java Collections From Basics to Expert Proficiency Copyright © 2024 by HiTeX Press All rights reserved. No part of this publication may be reproduced, distributed, or transmitted in any form or by any means, including photocopying, recording, or other electronic or mechanical methods, without the prior written permission of the publisher, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law.

Contents 1 Introduction to Java Collections Framework   1.1 What is the Java Collections Framework?   1.2 Advantages of Using Collections   1.3 Overview of Collection Interfaces   1.4 Hierarchy of the Collections Framework   1.5 Understanding Collection Classes   1.6 Differences Between Collection and Collections   1.7 Common Operations in Collections   1.8 Generics in Collections   1.9 Legacy Collections: Vectors and Hashtable   1.10 Java Collections Framework Improvements (Java 8 and beyond) 2 Understanding Collection Interfaces   2.1 Introduction to Collection Interfaces   2.2 The Iterable Interface   2.3 Understanding the Collection Interface   2.4 List Interface: Ordered Collections   2.5 Set Interface: Unique Collections   2.6 NavigableSet and SortedSet Interfaces   2.7 Queue Interface: Ordered Processing   2.8 Deque Interface: Double-Ended Queues   2.9 Map Interface: Key-Value Associations   2.10 NavigableMap and SortedMap Interfaces   2.11 Relationship Between Collection Interfaces   2.12 Using Default Methods in Interfaces 3 Working with Lists   3.1 Introduction to Lists   3.2 ArrayList: Dynamic Arrays   3.3 LinkedList: Doubly-Linked Lists   3.4 CopyOnWriteArrayList: Thread-Safe Lists   3.5 Vector: Legacy Resizable Array   3.6 Stack: Last-In-First-Out Lists

  3.7 Common List Operations   3.8 Performance Considerations for Lists   3.9 Iterating Over Lists   3.10 Working with SubLists   3.11 Sorting and Searching in Lists   3.12 Custom List Implementations 4 Using Sets for Unique Collections   4.1 Introduction to Sets   4.2 HashSet: Unordered Collections   4.3 LinkedHashSet: Ordered Sets   4.4 TreeSet: Sorted Sets   4.5 ConcurrentSkipListSet: Thread-Safe Sorted Sets   4.6 EnumSet: Specialized Set for Enums   4.7 Common Set Operations   4.8 Performance Considerations for Sets   4.9 Iterating Over Sets   4.10 Set Operations: Union, Intersection, Difference   4.11 Custom Set Implementations 5 Exploring Maps: Key-Value Pairs   5.1 Introduction to Maps   5.2 HashMap: Unordered Key-Value Pairs   5.3 LinkedHashMap: Ordered Key-Value Pairs   5.4 TreeMap: Sorted Key-Value Pairs   5.5 ConcurrentHashMap: Thread-Safe Maps   5.6 WeakHashMap: Maps with Weak Keys   5.7 IdentityHashMap: Key Comparison by Reference   5.8 EnumMap: Specialized Map for Enums   5.9 Common Map Operations   5.10 Performance Considerations for Maps   5.11 Iterating Over Maps   5.12 Custom Map Implementations 6 Queues and Deques: Handling Ordered Collections   6.1 Introduction to Queues and Deques   6.2 Queue Interface: Basic Operations   6.3 PriorityQueue: Natural Order Queues

  6.4 BlockingQueue: Thread-Safe Queues   6.5 ArrayBlockingQueue: Fixed Size Queues   6.6 LinkedBlockingQueue: Linked List Queues   6.7 PriorityBlockingQueue: Thread-Safe Priority Queues   6.8 Deque Interface: Double-Ended Queues   6.9 ArrayDeque: Resizable-Array Implementation   6.10 LinkedList as a Deque   6.11 ConcurrentLinkedDeque: Thread-Safe Double-Ended Queues   6.12 Common Queue and Deque Operations   6.13 Use Cases and Scenarios for Queues and Deques 7 Navigating through Sorted Collections   7.1 Introduction to Sorted Collections   7.2 Understanding Natural Ordering   7.3 Comparator Interface: Custom Ordering   7.4 TreeSet: Naturally Sorted Sets   7.5 TreeMap: Naturally Sorted Maps   7.6 NavigableSet Interface: Enhanced TreeSet Operations   7.7 NavigableMap Interface: Enhanced TreeMap Operations   7.8 ConcurrentSkipListSet: Thread-Safe Sorted Sets   7.9 ConcurrentSkipListMap: Thread-Safe Sorted Maps   7.10 Common Operations on Sorted Collections   7.11 Use Cases for Sorted Collections   7.12 Performance Considerations for Sorted Collections 8 Customizing Collections with Comparators and Sorting   8.1 Introduction to Comparators and Sorting   8.2 Implementing Comparator Interface   8.3 Using Comparator with Collections   8.4 Lambda Expressions and Comparators   8.5 Method References in Comparators   8.6 Sorting Lists with Comparator   8.7 Sorting Sets with Comparator   8.8 Sorting Maps by Keys and Values   8.9 Chaining Comparators   8.10 Reverse Ordering with Comparator   8.11 Comparator vs Comparable   8.12 Custom Sorting Use Cases

9 Concurrent Collections: Thread-Safe Data Structures   9.1 Introduction to Concurrent Collections   9.2 Understanding Thread Safety   9.3 ConcurrentHashMap: Thread-Safe Maps   9.4 CopyOnWriteArrayList: Thread-Safe Lists   9.5 CopyOnWriteArraySet: Thread-Safe Sets   9.6 BlockingQueue: Thread-Safe Queues   9.7 ConcurrentLinkedQueue: Non-Blocking Queues   9.8 ConcurrentSkipListSet: Thread-Safe Sorted Sets   9.9 ConcurrentSkipListMap: Thread-Safe Sorted Maps   9.10 Atomic Variables with Concurrent Collections   9.11 Performance Considerations for Concurrent Collections   9.12 Use Cases for Concurrent Collections 10 Best Practices and Common Pitfalls in Java Collections   10.1 Introduction to Best Practices and Common Pitfalls   10.2 Choosing the Right Collection   10.3 Efficient Use of Generics   10.4 Immutable Collections   10.5 Handling Null Values   10.6 Avoiding ConcurrentModificationException   10.7 Optimizing Performance   10.8 Using Collection Utility Methods (Collections)   10.9 Memory Management in Collections   10.10 Common Mistakes and How to Avoid Them   10.11 Debugging Collections   10.12 Case Studies of Best Practices in Real Projects

Introduction The Java Collections Framework (JCF) is a fundamental aspect of the Java programming language, providing developers with a robust and versatile toolkit for managing and manipulating groups of objects. Introduced in JDK 1.2, the framework has undergone numerous enhancements, establishing itself as an essential component for effective and efficient Java programming. At its core, the Java Collections Framework provides a unified architecture for representing and manipulating collections, thereby eliminating the need for ad-hoc data structures and associated algorithms. This standardization ensures that common collection-related tasks, such as searching, sorting, and manipulating data, can be performed with minimal complexity and maximum efficiency. One of the key advantages of the JCF is its ability to abstract the underlying data structures via a set of interfaces. These interfaces enable developers to focus on the functionality and behavior of their collections rather than their implementation details. Consequently, the framework fosters code that is not only reusable but also easily understandable and maintainable. The Java Collections Framework encompasses several core interfaces, including Collection, List, Set, Queue, and Map, each catering to different collection types and use cases. For instance, List implementations, like ArrayList and LinkedList, provide ordered collections that allow duplicates, whereas Set implementations, such as HashSet and TreeSet, offer collections that ensure uniqueness. The Queue and Deque interfaces support ordered processing, while the Map interface manages key-value pair associations, with implementations like HashMap and TreeMap catering to different performance characteristics and ordering requirements. Generics are a pivotal aspect of the Java Collections Framework, allowing developers to specify the type of objects that a collection can hold, thus enhancing type safety and reducing runtime errors. By leveraging generics,

collections become more expressive and less error-prone, with the added benefit of eliminating the need for extensive type casting. In addition to the standard collection interfaces and their implementations, the framework includes utility classes such as Collections and Arrays. These classes provide static methods for creating, manipulating, and searching collections, further streamlining common tasks and enhancing developer productivity. Whether sorting a list, shuffling elements, or performing binary searches, these utility methods offer efficient and optimized solutions. With the advent of Java 8, the collections framework experienced significant improvements with the introduction of lambda expressions and the Stream API. These features facilitate functional-style operations on collections, enabling developers to write concise and expressive code for complex data processing tasks. Operations such as filtering, mapping, and reducing can now be performed with ease, leveraging the power of parallelism to enhance performance. As Java continues to evolve, so too does its collections framework. Subsequent releases have introduced new collection types and concurrent implementations, catering to a broader range of applications and addressing the challenges posed by modern multicore processors. Concurrent collections like ConcurrentHashMap and CopyOnWriteArrayList provide thread-safe alternatives without compromising performance, making them indispensable for high- concurrency environments. This book delves into the depths of the Java Collections Framework, offering an exhaustive exploration of its core interfaces, implementations, and utility methods. Each chapter is designed to provide a clear and detailed understanding of the framework’s components, accompanied by examples and best practices. The goal is to equip readers with the knowledge and skills necessary to harness the full potential of the Java Collections Framework, fostering the development of efficient, maintainable, and robust Java applications.

Chapter 1 Introduction to Java Collections Framework The Java Collections Framework is a comprehensive architecture for representing and manipulating collections of objects in Java. This chapter covers the basics of the framework, detailing its advantages, key interfaces, and hierarchy. It explains the distinctions between collection interfaces and classes, introduces common operations, and discusses the role of generics. Additionally, it provides an overview of legacy collections and highlights improvements made in recent Java versions. 1.1 What is the Java Collections Framework? The Java Collections Framework (JCF) is a unified architecture designed to store and manipulate groups of objects. Introduced in Java 2 (JDK 1.2), the framework provides a set of interfaces and classes that operate on collections, allowing for the manipulation of data as a unified entity. This framework streamlines the structuring of collections, providing a coherent and efficient means to manage data. At the core of the Java Collections Framework are several essential interfaces, including Collection, Set, List, Queue, and Map. These interfaces define the contract for collections, specifying the operations that can be performed on them. Interfaces: Collection<T> - The root interface in the collection hierarchy. It represents a group of objects known as elements. The Collection interface is extended by other collection interfaces, such as Set and List. Set<T> - A collection that does not allow duplicate elements. This interface models mathematical sets. List<T> - An ordered collection (also known as a sequence). Lists can contain duplicate elements. Queue<T> - A collection used to hold multiple elements prior to processing. Typically, but not necessarily, elements are processed in a first-in, first-out (FIFO) order. Map<K,V> - An object that maps keys to values. A Map cannot contain duplicate keys; each key can map to at most one value. Classes: A variety of concrete classes implement these interfaces, providing different functionalities and performance characteristics. Key classes include: ArrayList<E> - Implements the List interface with a resizable array. HashSet<E> - Implements the Set interface, backed by a hash table. LinkedList<E> - Implements both the List and Deque interfaces, providing a doubly- linked list. PriorityQueue<E> - Implements a priority queue. HashMap<K,V> - Implements the Map interface with a hash table. To illustrate the structure of the Java Collections Framework, consider the following program, which demonstrates the use of an ArrayList to store and retrieve integers.

import java.util.ArrayList;  import java.util.List;    public class CollectionDemo {     public static void main(String[] args) {        // Create a list with integer elements        List<Integer> numbers = new ArrayList<>();          // Add elements to the list        numbers.add(1);        numbers.add(2);        numbers.add(3);        numbers.add(4);          // Access elements in the list        for (int num : numbers) {           System.out.println("Number: " + num);        }     }  } This program initializes an ArrayList and populates it with integers. The elements are then accessed and printed to the console. Executing the program yields the following output: Number: 1 Number: 2 Number: 3 Number: 4 The Java Collections Framework also benefits from the inclusion of generics, which enable type-safe collections. By using generics, the above ArrayList is restricted to Integer elements, preventing the addition of incompatible types at compile time. A key advantage of the Java Collections Framework is its provision of well-defined algorithms, encapsulated as static methods within the Collections utility class. Examples include sorting, searching, and shuffling. The following example demonstrates sorting a list of strings: import java.util.ArrayList;  import java.util.Collections;  import java.util.List;    public class SortDemo {     public static void main(String[] args) {        // Create a list with string elements        List<String> words = new ArrayList<>();          // Add elements to the list        words.add("apple");        words.add("orange");        words.add("banana");        words.add("grape");   

      // Sort the list        Collections.sort(words);          // Output the sorted list        for (String word : words) {           System.out.println(word);        }     }  } On running this program, the output is: apple banana grape orange This example highlights how the Collections utility class makes operations on collection elements simple and straightforward. Another fundamental aspect of the Java Collections Framework is the separation between interface and implementation. This design fosters flexibility and enables developers to switch between different implementations without modifying the client code that uses collections. For instance, if performance testing reveals that an ArrayList is inefficient for a particular task, a developer can switch to a LinkedList simply by changing the instantiation line: List<String> words = new LinkedList<>(); This allows the internal characteristics of the list to change while the external interface remains consistent for the client code. The Java Collections Framework represents a significant enhancement over traditional collections based on arrays and vectors. It mitigates many of the limitations and inefficiencies inherent in earlier structures through: **Unified and flexible architecture:** Establishing a common type hierarchy allows for greater consistency and interchangeability. **Performance optimization:** Diverse implementations facilitate the choice of the most appropriate data structures based on application requirements. **Enhanced functionality:** Utility classes and static methods provide a range of algorithms and operations that simplify complex tasks. Understanding the foundational aspects of the Java Collections Framework provides a basis for more advanced topics, such as concurrent collections, custom implementation of collections, and advanced usage patterns for optimal performance and scalability. 1.2 Advantages of Using Collections The Java Collections Framework (JCF) provides numerous advantages that enhance both the performance and maintainability of Java applications. Using collections over traditional data structures (such as arrays) brings several key benefits, which are detailed here to illustrate their impact on software development practices.

1. Improved Code Reusability and Maintainability By standardizing how groups of objects are handled, the Java Collections Framework makes it easier to write reusable code. When a developer uses the framework, the same operations like searching, sorting, or iterating can be applied across various collection types interchangeably. This means that once a developer learns the framework, they can apply this knowledge to many different scenarios without reinventing the wheel each time. Consider the following example of iterating over a List: List<String> items = new ArrayList<>();  items.add("item1");  items.add("item2");  items.add("item3");    for (String item : items) {     System.out.println(item);  } The same pattern of iteration can be applied to other collection types such as Set or Queue, showing the uniformity and reuse of patterns. 2. Enhanced Performance and Flexibility Different collection implementations optimize for different use-cases (e.g., quick access, fast iteration, or efficient insertion/deletion). Developers can select the most appropriate collection implementation depending on the required performance characteristics, and easily switch implementations if the requirements change without altering the high-level logic. For example, replacing an ArrayList with a LinkedList can switch the performance from being efficient in random access operations: List<String> items = new ArrayList<>(); to being efficient in insertions and deletions: List<String> items = new LinkedList<>(); ArrayList is preferred for scenarios with frequent random read operations, while LinkedList is better suited for scenarios with frequent insertions/deletions. 3. Reduced Development Time The framework’s rich set of ready-to-use interfaces and classes saves development time. Since the framework is well-tested and optimized, there’s no need to build custom data structure implementations from scratch. For example, Java Collections provides: List interface and its implementations like ArrayList, LinkedList Set interface and its implementations like HashSet, LinkedHashSet, TreeSet Map interface and its implementations like HashMap, LinkedHashMap, TreeMap

These built-in implementations cover most common data handling needs and are optimized for performance. 4. Enhanced Code Readability and Less Error-Prone The use of well-defined interfaces and abstract data types makes code that utilizes the Java Collections Framework easier to read and understand. Since the framework dictates a common pattern of usage, it reduces the likelihood of introducing errors. For example, using a Map to associate keys to values is straightforward: Map<String, Integer> map = new HashMap<>();  map.put("one", 1);  map.put("two", 2);  map.put("three", 3);    System.out.println(map.get("one")); // Outputs 1 The consistent use of put and get methods across different Map implementations simplifies key- value manipulations, reducing the chance of logic errors. 5. Support for Concurrent Collections Modern applications often require handling concurrent access to collections. The Java Collections Framework provides thread-safe implementations for such scenarios. For instance, ConcurrentHashMap is designed for high concurrency use-cases: Map<String, Integer> map = new ConcurrentHashMap<>();  map.put("one", 1);  map.put("two", 2); Using ConcurrentHashMap, multiple threads can safely update the map without external synchronization, which significantly simplifies concurrent program designs. 6. Inbuilt Algorithms and Utility Methods Collections come with a vast array of utility methods for sorting, searching, and performing other common operations via the Collections class. This obviates the need to manually implement these often-complex algorithms. Sorting a list is as simple as: List<Integer> numbers = Arrays.asList(3, 1, 4, 1, 5, 9);  Collections.sort(numbers);  System.out.println(numbers); // Outputs [1, 1, 3, 4, 5, 9] The Collections class offers numerous such utility functions, making the code more concise and less error-prone. Embracing the Java Collections Framework significantly enhances a developer’s efficiency and application robustness through its robust, consistent, and high-performance design. Consistent usage across varying application needs greatly simplifies development while ensuring maintainability and readability.

1.3 Overview of Collection Interfaces The Java Collections Framework leverages a set of interfaces to standardize the operations across different types of collections. These interfaces enable the manipulation of object groups without requiring knowledge of their underlying implementation. The core interfaces of the Java Collections Framework include Collection, List, Set, Queue, and Map. Each interface prescribes a set of methods that collections implementing the interface must support. Collection Interface The Collection interface is the root of the collection hierarchy. It represents a group of objects, known as elements. The Collection interface is extended by sub-interfaces such as List, Set, and Queue. Below is a basic example that demonstrates some fundamental methods defined in the Collection interface: Collection<String> collection = new ArrayList<>();  collection.add("Apple");  collection.add("Banana");  collection.size(); // Returns 2  collection.remove("Apple"); // Removes the element "Apple"  collection.clear(); // Clears the collection 2 List Interface The List interface extends Collection and introduces an ordered collection, also known as a sequence. Duplicates are allowed. The primary operations associated with List include positional access, search, list iteration, and range-view operations. The following is an example demonstrating some of these methods: List<String> list = new ArrayList<>();  list.add("Apple");  list.add("Banana");  list.add("Cherry");  list.get(1); // Returns "Banana"  list.indexOf("Cherry"); // Returns 2  list.set(0, "Apricot"); // Sets the value at index 0 to "Apricot" Banana 2 Set Interface The Set interface represents a collection that does not allow duplicate elements. It models the mathematical set abstraction and is extended by interfaces such as SortedSet and NavigableSet. Key operations include element addition and removal. Here is a snippet illustrating some Set operations: Set<String> set = new HashSet<>();  set.add("Apple");  set.add("Banana");  set.add("Apple"); // Duplicate element, will not be added  set.size(); // Returns 2  set.contains("Banana"); // Returns true

2 true Queue Interface The Queue interface extends Collection to support an ordered sequence of elements meant for holding elements prior to processing. The Queue interface provides additional insertion, extraction, and inspection operations. A typical implementation such as LinkedList can be used as shown below: Queue<String> queue = new LinkedList<>();  queue.add("First");  queue.add("Second");  queue.add("Third");  queue.poll(); // Retrieves and removes the head of the queue, returns "First"  queue.peek(); // Retrieves but does not remove the head, returns "Second" First Second Map Interface The Map interface maps keys to values and does not extend Collection. A map contains key-value pairs and disallows duplicate keys. The primary functionalities include querying, updating, and iterating over keys and values. Below is a demonstration of basic Map operations: Map<Integer, String> map = new HashMap<>();  map.put(1, "One");  map.put(2, "Two");  map.put(1, "Uno"); // Updates the value for key 1  map.get(2); // Returns "Two"  map.keySet(); // Returns a set of all keys Two The Java Collections Framework interfaces provide a structure for a wide range of collection types, allowing programs to handle collections of data uniformly and efficiently. Each interface is designed to represent a different way of organizing and accessing data, significantly enhancing the versatility and reuse of collection-handling code. 1.4 Hierarchy of the Collections Framework The Java Collections Framework is structured hierarchically, providing a cohesive and logical architecture that encompasses various interfaces and classes. At the root of this hierarchy lies the Collection interface, the most generalized form of a collection. Other primary interfaces, such as Set, List, and Queue, extend the Collection interface, each introducing unique behaviors and characteristics. Concurrently, the Map interface, which does not extend Collection, represents mappings of key-value pairs. Collection<E> Set<E> List<E> Queue<E> Map<K,V>

In diagrammatic form, the hierarchy can be visualized as:                         Collection<E>                         /     |     \               Set<E>  List<E>  Queue<E>              /   \            /    \         SortedSet<E>   Deque<E> BlockingQueue<E>              |                         |          NavigableSet<E>        BlockingDeque<E> Additionally, the Map hierarchy is structured as:                          Map<K,V>                         /       \                SortedMap<K,V>  ConcurrentMap<K,V>                        |                NavigableMap<K,V> ### Core Interfaces and Their Implementations **Collection Interface** The Collection<E> interface is the root of the hierarchy. It describes operations that can be performed on a group of objects, and various other interfaces that extend this one are tailored for specific types of collections. **Set Interface** The Set<E> interface represents a collection that does not allow duplicate elements. Key implementations include: HashSet<E> LinkedHashSet<E> TreeSet<E> The SortedSet<E> interface is a subtype of Set<E> that maintains its elements in a sorted order. TreeSet<E> implements SortedSet<E> and further extends the NavigableSet<E> interface, providing methods to navigate through the sorted collection. /* Example usage of TreeSet */  import java.util.TreeSet;    public class SetExample {     public static void main(String[] args) {        TreeSet<Integer> numbers = new TreeSet<>();        numbers.add(3);        numbers.add(1);        numbers.add(2);          for(Integer number : numbers) {           System.out.println(number);        }     }  } 

/* Expected Output */  1  2  3 **List Interface** The List<E> interface represents an ordered collection that allows duplicate elements. Key implementations include: ArrayList<E> LinkedList<E> Vector<E> ArrayList<E> and LinkedList<E> are frequently used. While ArrayList<E> provides fast random access, LinkedList<E> offers efficient insertions and deletions. /* Example usage of ArrayList */  import java.util.ArrayList;    public class ListExample {     public static void main(String[] args) {        ArrayList<String> names = new ArrayList<>();        names.add("Alice");        names.add("Bob");        names.add("Charlie");          for(String name : names) {           System.out.println(name);        }     }  }  /* Expected Output */  Alice  Bob  Charlie **Queue Interface** The Queue<E> interface is designed for holding elements prior to processing. Major implementations include: LinkedList<E> PriorityQueue<E> ArrayDeque<E> The Deque<E> interface, which extends Queue<E>, supports element insertion and removal at both ends. /* Example usage of PriorityQueue */  import java.util.PriorityQueue;   

public class QueueExample {     public static void main(String[] args) {        PriorityQueue<Integer> queue = new PriorityQueue<>();        queue.add(3);        queue.add(1);        queue.add(2);          while(!queue.isEmpty()) {           System.out.println(queue.poll());        }     }  }  /* Expected Output */  1  2  3 **Map Interface** The Map<K,V> interface represents a key-value mapping. Unlike Collection, it does not extend from it. Key implementations include: HashMap<K,V> TreeMap<K,V> LinkedHashMap<K,V> The SortedMap<K,V> interface, similar to SortedSet, maintains its elements in a sorted order. TreeMap<K,V> implements NavigableMap<K,V>, providing extensive navigation operations. /* Example usage of TreeMap */  import java.util.TreeMap;    public class MapExample {     public static void main(String[] args) {        TreeMap<String, Integer> map = new TreeMap<>();        map.put("one", 1);        map.put("two", 2);        map.put("three", 3);          for(Map.Entry<String, Integer> entry : map.entrySet()) {           System.out.println(entry.getKey() + " = " + entry.getValue());        }     }  }  /* Expected Output */  one = 1  three = 3  two = 2 This hierarchical structure is designed to provide both versatility and performance optimization for a variety of collection use cases, enabling the developer to select the most appropriate collection type for

a given task. The resulting framework offers a high degree of reusability and consistency across Java applications. 1.5 Understanding Collection Classes The Java Collections Framework provides an extensive suite of classes that implement the various collection interfaces. Each collection class provides particular features and efficiencies, making it essential for developers to comprehend their distinct characteristics to utilize them effectively. ArrayList: The ArrayList class is a resizable array implementation of the List interface. Unlike arrays, the size of an ArrayList can grow dynamically. When elements are added beyond its initial capacity, the array is automatically resized. This class offers constant time complexity, O(1), for accessing elements by index, and an amortized O(1) for element insertion. However, insertion or deletion of elements at arbitrary positions is slower, with a time complexity of O(n) due to the need to shift the subsequent elements. ArrayList<String> arrayList = new ArrayList<>();  arrayList.add("Element1");  arrayList.add("Element2");  System.out.println("ArrayList: " + arrayList); Output: ArrayList: [Element1, Element2] LinkedList: This class implements both the List and Deque interfaces. It is based on a doubly linked list. LinkedList allows constant time insertions or removals using iterators, O(1), but it provides linear time O(n) access to elements by index. This makes LinkedList suitable for scenarios where frequent insertions and deletions at arbitrary positions are required, while index-based access is of less importance. LinkedList<String> linkedList = new LinkedList<>();  linkedList.add("Element1");  linkedList.add("Element2");  System.out.println("LinkedList: " + linkedList); Output: LinkedList: [Element1, Element2] HashSet: The HashSet class implements the Set interface, backed by a hash table. It does not allow duplicate elements and provides constant-time performance for basic operations like add, remove, and contains, assuming the hash function disperses elements properly among the buckets. HashSet does not maintain any order of elements. HashSet<String> hashSet = new HashSet<>();  hashSet.add("Element1");  hashSet.add("Element2");  System.out.println("HashSet: " + hashSet); Output: HashSet: [Element1, Element2] LinkedHashSet: This class extends the HashSet class and implements Set interface. It is like a HashSet with a linked list running through it that maintains the insertion-order. When iterating through a LinkedHashSet, the elements will be returned in the order in which they were inserted.