Java Collections: From Lists to Maps with Time Complexity in Mind

Java’s Collection Framework is powerful, but knowing when to use ArrayList, LinkedList, HashMap, Queue, or Deque can make a big difference in the performance and readability of your code. In this article, I’ll guide you through real world scenarios, time complexities, and examples to help you choose the right data structure depending on your needs.

1. Large lists where random access is frequent. Fast index access? --> ArrayList

Time Complexity:

• Access by index: O(1)
• Insert/remove at end: O(1) - (except when capacity is exceeded)
• Insert/remove in middle or beginning: O(n)

List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
System.out.println(list.get(1)); // Fast because we know the position of what we are looking for: "Banana"

Don't use ArrayList for frequent insertions or removals at the beginning or middle, it needs to move subsequent elements and reindex them, which can degrade performance.

2. Frequent Insert/Remove at Beginning or End or modifying element during Iteration? --> LinkedList

If your operations involve adding or removing elements at the beginning or end, LinkedList is more efficient.

Time Complexity:

• Add/remove at beginning/end: O(1)
• Access by index: O(n)

List<String> list = new LinkedList<>();
list.add("first");
list.add(0, "Zero");       // Fast
list.addLast("last");      // Fast
list.removeFirst();        // Fast

Don’t use LinkedList for index-based access, it’s slow compared to ArrayList.

3. Key-based lookup? --> HashMap

Time Complexity:

• Get/put by key: O(1)
• Iteration over keys/values: O(n)

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 30);
map.put("Bob", 25);
System.out.println(map.get("Bob")); // Fast lookup

3.1 HashMap vs TreeMap vs LinkedHashMap

// HashMap: Fastest, no insertion ordering
Map<String, String> hashMap = new HashMap<>();

// TreeMap: Sorted by keys, slower but natural ordering
Map<String, Integer> treeMap = new TreeMap<>();

        // Adding key-value pairs in random order
        treeMap.put("zebra", 1);
        treeMap.put("apple", 2);
        treeMap.put("monkey", 3);
        treeMap.put("banana", 4);

        System.out.println("TreeMap: " + treeMap);
        // Output: {apple=2, banana=4, monkey=3, zebra=1} (always sorted by key!)

// LinkedHashMap: Maintains insertion order
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();

        linkedHashMap.put("first", 1);
        linkedHashMap.put("second", 2);
        linkedHashMap.put("third", 3);
        linkedHashMap.put("second", 20); // Updates existing key, maintains position
        linkedHashMap.put("fourth", 4);

        System.out.println("LinkedHashMap: " + linkedHashMap);
        // Output: {first=1, second=20, third=3, fourth=4} (insertion order preserved!)      

4. Need Unique Elements Only? --> Set

When you need to ensure no duplicates in your collection, use a Set.
Time Complexity (HashSet):

• Add/remove/contains: O(1)

Set<String> uniqueEmails = new HashSet<>();
uniqueEmails.add("[e-mail]");
uniqueEmails.add("[e-mail]");
uniqueEmails.add("[e-mail]"); // Duplicate - won't be added

Variants:

• HashSet: Fastest, no ordering
• TreeSet: Sorted unique elements
• LinkedHashSet: Unique + insertion order preserved

5. Process Items In The Order They Arrived (FIFO) --> Queue

Interface: Queue
Implementations: LinkedList, ArrayDeque

Time Complexity:

• Add (offer): O(1)
• Remove (poll): O(1)

Queue<String> queue = new LinkedList<>();
queue.offer("Task1");
queue.offer("Task2");
System.out.println(queue.poll()); // "Task1"

6. Double-Ended Queue --> Deque

Interface: Deque
Implementations: ArrayDeque, LinkedList

Time Complexity:

• Add/remove from both ends: O(1)

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("First");
deque.addLast("Last");
System.out.println(deque.removeLast()); // "Last"