Deep Dive into List, Set, and Queue Implementations in Java Collections

In the previous week article, we introduced the Java Collection Framework and its core interfaces. Now, let’s take a closer look at the List, Set, and Queue interfaces and their most commonly used implementations. We’ll explore their use cases, performance characteristics, and practical examples to help you choose the right collection for your needs.

1. Introduction to List, Set, and Queue

The List, Set, and Queue interfaces are part of the Java Collection Framework and serve different purposes:

• List: An ordered collection that allows duplicates.
• Set: A collection that does not allow duplicates.
• Queue: A collection designed for holding elements prior to processing (FIFO or priority-based).

Let’s explore each of these interfaces and their implementations in detail.

2. List Implementations

The List interface represents an ordered collection of elements. It allows duplicates and provides positional access to elements.

2.1 ArrayList

• Description: ArrayList is a resizable array implementation of the List interface.
• Use Case: Ideal for scenarios where you need fast access to elements by index and fewer insertions/deletions in the middle.
• Performance:

Access: O(1)

Insertion/Deletion: O(n) (worst case, when resizing or inserting/deleting in the middle)

Example: Using ArrayList

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) {
        List<String> fruits = new ArrayList<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");

        System.out.println("Fruits: " + fruits); // Output: [Apple, Banana, Cherry]
        System.out.println("First Fruit: " + fruits.get(0)); // Output: Apple
    }
}        

2.2 LinkedList

• Description: LinkedList is a doubly-linked list implementation of the List and Deque interfaces.
• Use Case: Ideal for scenarios with frequent insertions and deletions, especially in the middle of the list.
• Performance:

Access: O(n)

Insertion/Deletion: O(1) (if you have a reference to the node)

Example: Using LinkedList

import java.util.LinkedList;
import java.util.List;

public class LinkedListExample {
    public static void main(String[] args) {
        List<String> colors = new LinkedList<>();
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");

        System.out.println("Colors: " + colors); // Output: [Red, Green, Blue]
        colors.add(1, "Yellow"); // Insert at index 1
        System.out.println("Updated Colors: " + colors); // Output: [Red, Yellow, Green, Blue]
    }
}        

2.3 Vector and Stack

• Description: Vector is a legacy synchronized collection, and Stack is a subclass of Vector that implements a LIFO (Last-In-First-Out) stack.
• Use Case: Vector is rarely used in modern Java because ArrayList is faster for most single-threaded operations. If synchronization is needed, use CopyOnWriteArrayList or ConcurrentLinkedQueue instead.

Example: Using Stack

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("Apple");
        stack.push("Banana");
        stack.push("Cherry");

        System.out.println("Stack: " + stack); // Output: [Apple, Banana, Cherry]
        System.out.println("Popped Element: " + stack.pop()); // Output: Cherry
    }
}        

2.4 Using ListIterator for Efficient Traversal

When working with LinkedList, using ListIterator can improve efficiency by avoiding redundant traversals:

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class ListIteratorExample {
    public static void main(String[] args) {
        List<String> colors = new LinkedList<>();
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");

        ListIterator<String> iterator = colors.listIterator();
        while (iterator.hasNext()) {
            System.out.println("Color: " + iterator.next());
        }
    }
}        

3. Set Implementations

The Set interface represents a collection of unique elements.

3.1 HashSet

• Description: HashSet is an unordered collection that uses hashing to store elements.
• Use Case: Ideal for scenarios where you need fast access and don’t care about the order of elements.
• Performance:

Access/Insertion/Deletion: O(1) (average case)

Example: Using HashSet

import java.util.HashSet;
import java.util.Set;

public class HashSetExample {
    public static void main(String[] args) {
        Set<String> uniqueFruits = new HashSet<>();
        uniqueFruits.add("Apple");
        uniqueFruits.add("Banana");
        uniqueFruits.add("Apple"); // Duplicate, won't be added

        System.out.println("Unique Fruits: " + uniqueFruits); // Output: [Apple, Banana]
    }
}        

3.2 LinkedHashSet

• Description: LinkedHashSet maintains insertion order while ensuring uniqueness.
• Use Case: Ideal for scenarios where you need uniqueness and insertion order.
• Performance:

Access/Insertion/Deletion: O(1) (average case)

Example: Using LinkedHashSet

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        Set<String> orderedFruits = new LinkedHashSet<>();
        orderedFruits.add("Apple");
        orderedFruits.add("Banana");
        orderedFruits.add("Cherry");

        System.out.println("Ordered Fruits: " + orderedFruits); // Output: [Apple, Banana, Cherry]
    }
}        

3.3 TreeSet

• Description: TreeSet is a sorted set that uses a Red-Black Tree for storage.
• Use Case: Ideal for scenarios where you need elements in sorted order.
• Performance:

Access/Insertion/Deletion: O(log n)

Example: Using TreeSet

import java.util.TreeSet;
import java.util.Set;

public class TreeSetExample {
    public static void main(String[] args) {
        Set<String> sortedFruits = new TreeSet<>();
        sortedFruits.add("Banana");
        sortedFruits.add("Apple");
        sortedFruits.add("Cherry");

        System.out.println("Sorted Fruits: " + sortedFruits); // Output: [Apple, Banana, Cherry]
    }
}        

4. Queue Implementations

The Queue interface represents a collection designed for holding elements prior to processing.

4.1 PriorityQueue

• Description: PriorityQueue orders elements based on their natural order or a custom comparator.
• Use Case: Ideal for scenarios where you need to process elements based on priority.
• Performance:

Insertion/Deletion: O(log n)

Example: Using PriorityQueue

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        Queue<Integer> numbers = new PriorityQueue<>();
        numbers.add(10);
        numbers.add(5);
        numbers.add(20);

        System.out.println("Queue: " + numbers); // Output: [5, 10, 20]
        System.out.println("Poll: " + numbers.poll()); // Output: 5 (removes and returns the head)
    }
}        

4.2 ArrayDeque

• Description: ArrayDeque is a resizable array implementation of the Deque interface.
• Use Case: Ideal for scenarios where you need a double-ended queue (FIFO or LIFO).
• Performance:

Access/Insertion/Deletion: O(1) (average case)

Example: Using ArrayDeque

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("Apple");
        deque.addLast("Banana");
        deque.addLast("Cherry");

        System.out.println("Deque: " + deque); // Output: [Apple, Banana, Cherry]
        System.out.println("Removed First: " + deque.removeFirst()); // Output: Apple
    }
}        

When to Use PriorityQueue vs. ArrayDeque

• Use PriorityQueue when elements need to be processed in priority order instead of insertion order.
• Use ArrayDeque when you need a double-ended queue that supports efficient insertion and removal from both ends.

5. Performance Comparison

Here’s a quick comparison of the performance of common implementations:

6. Real-World Use Cases

• ArrayList: Storing a list of user names or product details.
• LinkedList: Implementing a playlist or undo/redo functionality.
• HashSet: Storing unique email addresses or usernames.
• TreeSet: Maintaining a sorted list of high scores or leaderboard rankings.
• PriorityQueue: Task scheduling or processing orders based on priority.
• ArrayDeque: Implementing a cache or sliding window algorithm.

7. Choosing the Right Collection

Here’s a quick decision guide to help you select the right collection:

Requirement Recommended Collection

Fast lookups and index-based access ArrayList

Frequent insertions/deletions LinkedList

Unique elements, unordered HashSet

Unique elements, sorted TreeSet

Maintain insertion order in Set LinkedHashSet

Priority-based processing PriorityQueue

Double-ended queue ArrayDeque

8. Conclusion

In this article, we explored the List, Set, and Queue interfaces and their most commonly used implementations. We discussed their use cases, performance characteristics, and provided practical examples to help you choose the right collection for your needs. We also covered efficient traversal techniques, when to use different queue implementations, and a decision guide to help you make better choices.

In the next article, we’ll dive into the Map interface and its implementations, along with advanced topics like concurrent collections and custom sorting.

For a complete learning journey, follow me: Eugene Koshy