Java Collections Framework
The Java Collections Framework provides a unified architecture for representing and manipulating collections, enabling them to be manipulated independently of implementation details.
Collection Hierarchy
Collection Interface
├── List Interface (Ordered, allows duplicates)
├── Set Interface (Unique elements)
└── Queue Interface (FIFO processing)
Map Interface (Key-value pairs) - Separate hierarchy
List Interface
ArrayList
1List<String> names = new ArrayList<>();
2names.add("Alice");
3names.add("Bob");
4names.add("Charlie");
5
6// Access by index
7String first = names.get(0); // "Alice"
8
9// Remove by index
10names.remove(1); // Removes "Bob"
11
12// Size
13int size = names.size(); // 2Characteristics:
- Dynamic array implementation
- Fast random access (O(1))
- Slow insertion/deletion in middle (O(n))
- Allows null elements
LinkedList
1List<Integer> numbers = new LinkedList<>();
2numbers.add(10);
3numbers.add(20);
4numbers.addFirst(5); // Add at beginning
5numbers.addLast(30); // Add at end
6
7// Access first and last elements
8int first = numbers.getFirst(); // 5
9int last = numbers.getLast(); // 30Characteristics:
- Doubly-linked list implementation
- Fast insertion/deletion (O(1))
- Slow random access (O(n))
- Implements both List and Deque interfaces
Set Interface
HashSet
1Set<String> uniqueNames = new HashSet<>();
2uniqueNames.add("Alice");
3uniqueNames.add("Bob");
4uniqueNames.add("Alice"); // Duplicate ignored
5
6// Check existence
7boolean hasAlice = uniqueNames.contains("Alice"); // true
8
9// Size
10int size = uniqueNames.size(); // 2Characteristics:
- Hash table implementation
- No ordering guarantee
- Fast operations (O(1) average)
- Allows one null element
TreeSet
1Set<Integer> sortedNumbers = new TreeSet<>();
2sortedNumbers.add(30);
3sortedNumbers.add(10);
4sortedNumbers.add(20);
5
6// Automatically sorted
7System.out.println(sortedNumbers); // [10, 20, 30]
8
9// Range operations
10Integer higher = sortedNumbers.higher(20); // 30
11Integer lower = sortedNumbers.lower(20); // 10Characteristics:
- Red-black tree implementation
- Sorted natural ordering
- Slower operations (O(log n))
- No null elements
Map Interface
HashMap
1Map<String, Integer> ages = new HashMap<>();
2ages.put("Alice", 25);
3ages.put("Bob", 30);
4ages.put("Charlie", 35);
5
6// Access values
7int aliceAge = ages.get("Alice"); // 25
8
9// Check key existence
10boolean hasBob = ages.containsKey("Bob"); // true
11
12// Get all keys
13Set<String> names = ages.keySet();Characteristics:
- Hash table implementation
- No ordering guarantee
- Fast operations (O(1) average)
- Allows one null key and multiple null values
TreeMap
1Map<String, Integer> sortedAges = new TreeMap<>();
2sortedAges.put("Charlie", 35);
3sortedAges.put("Alice", 25);
4sortedAges.put("Bob", 30);
5
6// Automatically sorted by key
7System.out.println(sortedAges); // {Alice=25, Bob=30, Charlie=35}
8
9// Range operations
10Map<String, Integer> subMap = sortedAges.headMap("Bob"); // {Alice=25}Characteristics:
- Red-black tree implementation
- Sorted by keys
- Slower operations (O(log n))
- No null keys
Queue Interface
PriorityQueue
1Queue<Integer> priorityQueue = new PriorityQueue<>();
2priorityQueue.add(30);
3priorityQueue.add(10);
4priorityQueue.add(20);
5
6// Retrieves smallest element first
7int smallest = priorityQueue.peek(); // 10
8int removed = priorityQueue.poll(); // 10ArrayDeque (Stack replacement)
1Deque<Integer> stack = new ArrayDeque<>();
2stack.push(10); // Push to top
3stack.push(20);
4stack.push(30);
5
6int top = stack.peek(); // 30
7int popped = stack.pop(); // 30Iterating Collections
For-each loop
1List<String> names = Arrays.asList("Alice", "Bob", "Charlie");
2for (String name : names) {
3 System.out.println(name);
4}Iterator
1Iterator<String> iterator = names.iterator();
2while (iterator.hasNext()) {
3 String name = iterator.next();
4 if (name.equals("Bob")) {
5 iterator.remove(); // Safe removal
6 }
7}Java 8 Streams
1List<String> filtered = names.stream()
2 .filter(name -> name.startsWith("A"))
3 .collect(Collectors.toList());
4
5List<Integer> lengths = names.stream()
6 .map(String::length)
7 .collect(Collectors.toList());Utility Methods
Collections Class
1List<Integer> numbers = Arrays.asList(3, 1, 4, 1, 5);
2
3// Sort
4Collections.sort(numbers);
5
6// Binary search (requires sorted list)
7int index = Collections.binarySearch(numbers, 4);
8
9// Shuffle
10Collections.shuffle(numbers);
11
12// Unmodifiable view
13List<Integer> unmodifiable = Collections.unmodifiableList(numbers);
14
15// Synchronized view
16List<Integer> synchronized = Collections.synchronizedList(numbers);Choosing the Right Collection
| Use Case | Recommended Collection | |----------|----------------------| | Fast random access | ArrayList | | Frequent insertion/deletion | LinkedList | | Unique elements | HashSet | | Sorted unique elements | TreeSet | | Key-value mapping | HashMap | | Sorted key-value mapping | TreeMap | | Priority processing | PriorityQueue | | Stack operations | ArrayDeque |
Performance Considerations
Time Complexity Summary
| Operation | ArrayList | LinkedList | HashSet | HashMap | |-----------|-----------|------------|---------|---------| | Add (end) | O(1)* | O(1) | O(1) | O(1) | | Add (middle) | O(n) | O(1) | N/A | N/A | | Remove (end) | O(1) | O(1) | O(1) | O(1) | | Remove (middle) | O(n) | O(1) | O(1) | O(1) | | Get by index | O(1) | O(n) | N/A | N/A | | Contains | O(n) | O(n) | O(1) | O(1) |
*Amortized O(1) for ArrayList
Best Practices
- Program to interfaces: Use List, Set, Map as variable types
- Choose appropriate implementation: Based on performance needs
- Initialize with proper capacity: To avoid resizing
- Use generics: For type safety
- Consider immutable collections: For thread safety
- Use streams: For functional-style operations
- Be aware of concurrency: Use concurrent collections in multi-threaded code
The Collections Framework is essential for effective Java programming, providing powerful tools for data manipulation and storage.
