Lists, Sets, Queues, and Deques

Introduction

The Java Collections Framework provides reusable interfaces and implementations for storing and processing groups of objects. Selecting a collection is not merely a matter of syntax. It is a design decision involving ordering, duplication, access patterns, memory use, thread-safety, and algorithmic cost.

This chapter examines seven commonly used implementations: ArrayList, LinkedList, HashSet, LinkedHashSet, TreeSet, PriorityQueue, and ArrayDeque. The central distinction is between a collection's interface contract and its implementation strategy. For example, both ArrayList and LinkedList implement List, but their performance characteristics differ substantially.

Learning Objectives

By the end of this chapter, you should be able to:

• distinguish lists, sets, queues, and deques;
• explain ordering and uniqueness guarantees;
• select an appropriate implementation for a programming task;
• analyse common operations using Big-O notation;
• write Java programs using the seven implementations;
• avoid common errors involving equality, mutability, null values, and priority ordering;
• justify a collection choice in a professional application.

1. The Collection Abstraction

A collection stores references to objects. The principal interfaces considered here are:

• List: an ordered sequence that normally permits duplicates and supports positional access.
• Set: a collection that does not permit duplicate elements according to its equality or comparison rule.
• Queue: a collection designed for processing elements, commonly in first-in-first-out (FIFO) order.
• Deque: a double-ended queue supporting insertion and removal at both the front and the rear.

Java generics provide compile-time type safety:

List<String> names = new ArrayList<>();
names.add("Amina");
// names.add(42);              // Compile-time error

The expression new ArrayList<>() creates the implementation, while the variable type List<String> exposes the intended abstraction. Programming to the interface makes future substitution easier.

Ordering and uniqueness

Ordering can mean several different things:

1. Encounter or insertion order: the order in which elements were added.
2. Index order: a list's positions, such as index 0, index 1, and so on.
3. Sorted order: an order defined by natural ordering or a comparator.
4. Priority order: the next element is selected according to priority, but iteration need not be sorted.
5. No contractual order: the implementation does not promise a stable order.

A set's uniqueness is determined by its implementation. Hash-based sets use equals() and hashCode(), while TreeSet uses comparison. Consequently, an object may be considered a duplicate by one set and distinct by another if these definitions are inconsistent.

2. Lists

2.1 ArrayList

ArrayList<E> is a resizable array. Elements occupy logical positions from index 0 through size() - 1.

List<String> courses = new ArrayList<>();
courses.add("Java");
courses.add("Python");
courses.add(1, "Databases");
System.out.println(courses);       // [Java, Databases, Python]
System.out.println(courses.get(0));
courses.set(0, "Advanced Java");

ArrayList is appropriate when:

• indexed access is frequent;
• elements are usually appended;
• iteration is common;
• insertions and removals in the middle are relatively uncommon.

Appending is normally amortized constant time. Occasionally, the backing array must grow and elements are copied, making that particular operation linear. Access by index is constant time because the address can be calculated directly from the base address and element position.

Removing an element from the middle shifts later references left. Therefore, the operation is linear in the number of elements that must be shifted. Removing from the end avoids shifting and is constant time in the usual implementation model.

The capacity of an ArrayList is not its logical size. Capacity is the number of allocated reference slots; size is the number of stored elements. ensureCapacity can reduce repeated reallocations when a large approximate size is known.

2.2 LinkedList

LinkedList<E> is a doubly linked list. Each node stores an element and links to its previous and next nodes.

LinkedList<String> tasks = new LinkedList<>();
tasks.addLast("Compile");
tasks.addLast("Test");
tasks.addFirst("Design");
String first = tasks.removeFirst();

A linked list supports constant-time insertion or removal at an already-known node, including either end. However, finding an element by index requires traversal. Thus, get(i) is linear in the distance traversed, even though insertion after a located node is constant time.

LinkedList implements both List and Deque. This makes it flexible, but flexibility does not automatically make it the best choice. For many list workloads, ArrayList has better cache locality, lower per-element overhead, and faster iteration. Use LinkedList when its node-based insertion/removal behavior or deque operations are genuinely useful.

2.3 List comparison

Here, n denotes the number of elements. Big-O notation describes growth as n increases; it does not predict exact running time on every machine.

3. Sets

3.1 HashSet

HashSet<E> stores unique elements using a hash table. It makes no guarantee about iteration order.

Set<String> codes = new HashSet<>();
codes.add("KE");
codes.add("GH");
codes.add("KE");
System.out.println(codes.size());   // 2
System.out.println(codes.contains("GH"));

Average-case insertion, lookup, and removal are O(1), assuming a well-distributed hash function and a reasonable load factor. In adverse collision conditions, performance can degrade; modern Java implementations use tree-based structures within heavily colliding buckets in relevant circumstances, but developers should still implement sound hashing.

For an object used as a hash-set element, equals() and hashCode() must obey their contract. If two objects are equal, they must return the same hash code. Mutable fields used in equality or hashing should not be changed while the object is in the set, because the object may become unreachable through normal lookup.

3.2 LinkedHashSet

LinkedHashSet<E> is a hash set with a linked structure that preserves insertion order during iteration.

Set<String> uniqueWords = new LinkedHashSet<>();
uniqueWords.add("red");
uniqueWords.add("blue");
uniqueWords.add("red");
System.out.println(uniqueWords);    // [red, blue]

It generally has average O(1) membership, insertion, and removal, but uses more memory than HashSet. It is valuable when duplicates must be removed without losing the order in which values first appeared—for example, normalising an event stream or preserving user-entered options.

3.3 TreeSet

TreeSet<E> stores unique elements in sorted order. It is commonly implemented using a balanced search tree, so insertion, removal, and lookup are O(log n).

NavigableSet<Integer> marks = new TreeSet<>();
marks.add(72);
marks.add(48);
marks.add(91);
System.out.println(marks);           // [48, 72, 91]
System.out.println(marks.ceiling(70)); // 72

Elements must be mutually comparable, or a compatible Comparator must be supplied:

Set<String> byLength = new TreeSet<>(
    Comparator.comparingInt(String::length)
);

This example contains an important subtlety: strings with equal lengths compare as zero, so the set treats them as duplicates even if equals() says they are different. A comparator used by a sorted set should normally be consistent with equality unless this deliberate equivalence is intended.

TreeSet supports range and neighbour operations such as first, last, lower, higher, floor, ceiling, and subSet. These capabilities justify its higher logarithmic cost when ordered queries are needed.

3.4 Set comparison

Do not infer that a set's printed order is meaningful unless its contract guarantees that order.

4. Queues and Deques

4.1 Queue semantics

A queue typically processes the earliest eligible element first. The Queue interface provides paired methods:

• add / offer: insert, with add potentially throwing if capacity is restricted;
• remove / poll: remove, with remove throwing when empty and poll returning null;
• element / peek: inspect, with element throwing when empty and peek returning null.

For general-purpose code, offer, poll, and peek often communicate empty or capacity conditions more safely.

4.2 PriorityQueue

PriorityQueue<E> is not a FIFO queue. Its head is the least element according to natural ordering or a comparator.

PriorityQueue<Integer> jobs = new PriorityQueue<>();
jobs.offer(30);
jobs.offer(10);
jobs.offer(20);
System.out.println(jobs.poll());      // 10

The implementation is a binary heap. Insertion and removal of the head are O(log n), while peek is O(1). Searching for an arbitrary value is O(n), and iteration does not produce sorted order. To process all elements in priority order, repeatedly call poll, or copy the values into a structure and sort them.

A practical example is a scheduler in which a lower numeric value represents a more urgent job:

record Job(String name, int priority) {}

PriorityQueue<Job> queue = new PriorityQueue<>(
    Comparator.comparingInt(Job::priority)
);
queue.offer(new Job("Report", 3));
queue.offer(new Job("Security alert", 1));
System.out.println(queue.poll().name()); // Security alert

The comparator must be consistent with the application's meaning of priority. A priority queue is not stable by default: if two elements have equal priority, their relative processing order is not guaranteed.

4.3 ArrayDeque

ArrayDeque<E> is a resizable circular array implementing Deque<E>. It supports efficient operations at both ends and is usually preferred over Stack for stack behavior and over LinkedList for many deque workloads.

Deque<String> history = new ArrayDeque<>();
history.push("Page A");
history.push("Page B");
System.out.println(history.pop());       // Page B

Deque<Integer> numbers = new ArrayDeque<>();
numbers.addLast(2);
numbers.addFirst(1);
numbers.addLast(3);

For a stack, use push and pop; for a FIFO queue, use offerLast and pollFirst. Insertion and removal at either end are amortized O(1). ArrayDeque does not permit null, which avoids ambiguity because null is used by methods such as poll and peek to signal absence.

ArrayDeque is not thread-safe. If multiple threads access a mutable deque, use suitable external synchronisation or a concurrent collection designed for the workload.

4.4 Queue and deque comparison

5. Complexity and Space Considerations

The following summary assumes ordinary implementations, valid comparators, and average-case hashing where indicated.

Space complexity is generally O(n) for all these structures, because storage grows with the number of elements. Constants differ: linked nodes store additional references, hash structures maintain buckets and links, and array structures may reserve unused capacity. The actual memory cost also includes the objects referenced; a collection normally stores references rather than copies of the objects.

6. Choosing a Collection: A Decision Framework

Ask the following questions:

1. Are duplicates meaningful? If yes, begin with a List; if no, use a Set.
2. Is indexed access frequent? Prefer ArrayList.
3. Must insertion order be preserved while removing duplicates? Prefer LinkedHashSet.
4. Are sorted order or range queries required? Prefer TreeSet.
5. Is the next item selected by priority? Prefer PriorityQueue.
6. Are operations concentrated at one or both ends? Prefer ArrayDeque.
7. Is thread safety required? These implementations are not automatically safe for concurrent mutation. Select a concurrent design or coordinate access explicitly.

Use the narrowest interface that expresses the requirement. For example, expose Queue<Job> when callers should enqueue and dequeue jobs, rather than exposing the implementation's entire API.

7. Worked Application: A Support-Ticket Service

Background

Consider an illustrative help-desk service. Incoming tickets have an identifier, customer, severity, and arrival sequence. The service must retain every ticket, prevent duplicate identifiers, display tickets in arrival order, and process urgent tickets first.

Problem analysis

One structure cannot optimally express every requirement:

• a map would be ideal for direct lookup by identifier, but the present focus is on the specified collection types;
• a LinkedHashSet can preserve unique ticket identifiers in arrival order, but a ticket object whose severity changes would be problematic if comparison fields were mutable;
• a PriorityQueue is appropriate for processing severity, but it does not preserve arrival order among equal priorities unless a tie-breaker is included.

Approach

Use an immutable record and a comparator with two criteria:

record Ticket(String id, int severity, long arrival) {}

Set<String> receivedIds = new LinkedHashSet<>();
PriorityQueue<Ticket> pending = new PriorityQueue<>(
    Comparator.comparingInt(Ticket::severity)
              .thenComparingLong(Ticket::arrival)
);

void receive(Ticket ticket) {
    if (receivedIds.add(ticket.id())) {
        pending.offer(ticket);
    }
}

If severity 1 is most urgent, the comparator processes lower severity values first. The arrival number resolves ties, producing predictable first-come order within a severity level.

Outcome

LinkedHashSet.add rejects duplicate identifiers while retaining arrival order for reporting. PriorityQueue.poll selects the next ticket efficiently. The design separates reporting order from processing priority, rather than forcing one collection to perform incompatible roles.

Learning points

• Collection choice should follow requirements, not habit.
• A priority queue's iteration order is not a processing guarantee; poll is the meaningful operation.
• Immutable elements reduce the risk of broken hashing or ordering.
• Explicit tie-breaking improves reproducibility and fairness.

8. Common Errors and Best Practices

Relying on unspecified order

Never write tests that expect a particular HashSet order. If order matters, select LinkedHashSet or TreeSet deliberately.

Using a list for membership tests

Repeated ArrayList.contains calls can produce O(n) work per lookup. For large data sets requiring repeated membership checks, a hash set is usually more suitable.

Assuming PriorityQueue iteration is sorted

Only the head is guaranteed to be the next priority element. Use repeated poll calls when sorted removal is required.

Mutating set elements

Changing a field used by equals, hashCode, or comparison while an object is stored can make lookup and removal unreliable. Prefer immutable key-like objects.

Confusing capacity and size

A collection's capacity is implementation storage; its size is the number of elements. An empty ArrayList may have nonzero capacity, while a full list may grow during insertion.

Ignoring null policies

HashSet and LinkedHashSet permit one null; TreeSet with natural ordering generally does not; ArrayDeque rejects null; queue methods may use null to indicate absence. Do not treat null policy as interchangeable across collections.

Concurrent access

The implementations discussed are not general-purpose concurrent collections. A read-only collection safely shared after publication differs from a collection being mutated by multiple threads. In multithreaded Java programs, consider ConcurrentLinkedQueue, blocking queues, immutable snapshots, or explicit locks where appropriate.

9. Contemporary Professional Practice

Modern Java development increasingly uses immutable data, records, streams, and clear interface-based APIs. Streams can transform or filter collections, but they do not replace the need to choose an appropriate storage structure. A stream pipeline over a HashSet still has no meaningful insertion order, while a pipeline over a LinkedHashSet can preserve encounter order unless an operation changes that behaviour.

Performance claims should be validated with representative measurements rather than assumptions. For serious benchmarking, tools such as Java Microbenchmark Harness (JMH) are preferable to informal timing with System.nanoTime, because warm-up, just-in-time compilation, garbage collection, and dead-code elimination can distort results.

Collection selection also has governance implications. If collections hold personal, financial, or security-related data, developers must control access, avoid accidental logging, define retention policies, and consider whether ordering or duplicate removal could affect auditability. A collection is a technical structure, but its behaviour can influence fairness, traceability, and compliance.

Chapter Summary

ArrayList is a strong default for ordered data with frequent indexed access and appends. LinkedList supports efficient end operations but pays for node overhead and slow indexed access. HashSet provides fast average membership operations without an order guarantee. LinkedHashSet adds insertion order, while TreeSet provides sorted uniqueness and logarithmic operations with useful range queries. PriorityQueue selects its least element according to a priority rule, but its iterator is not sorted. ArrayDeque efficiently supports queues and stacks at both ends and rejects null elements.

The correct choice depends on ordering, uniqueness, access pattern, priority semantics, memory considerations, and concurrency requirements. Good Java design exposes suitable interfaces, uses consistent equality and comparison rules, avoids mutable keys, and tests assumptions about performance and order.

Key Terms

Collection: An object that groups and manages multiple elements.

List: An ordered collection that normally permits duplicates and positional access.

Set: A collection that does not permit duplicate elements under its equality or comparison rule.

Queue: A collection designed to process elements, commonly in FIFO order.

Deque: A double-ended queue supporting operations at both ends.

ArrayList: A resizable-array implementation of List.

LinkedList: A doubly linked implementation of List and Deque.

HashSet: A hash-table-based set with no guaranteed iteration order.

LinkedHashSet: A hash-based set that preserves insertion order.

TreeSet: A sorted set based on comparison and a balanced tree structure.

PriorityQueue: A heap-based queue whose head has the highest defined priority, usually the least element.

ArrayDeque: A resizable-array deque suitable for queue and stack operations.

Natural ordering: The ordering defined by a type's Comparable implementation.

Comparator: An object that defines an ordering independently of the element class.

Hash code: An integer used to help locate an object in a hash-based structure.

Load factor: A hash-table threshold relationship influencing when resizing occurs.

Amortized complexity: Average cost per operation over a sequence that may include occasional expensive operations.

Encounter order: The order in which elements are observed during iteration.

Big-O notation: A description of how resource requirements grow with input size.

Immutability: A property indicating that an object's state cannot change after construction.

Review Questions

Short Answer Questions

1. Why is ArrayList.get(index) generally faster than LinkedList.get(index)?
2. What ordering does LinkedHashSet preserve?
3. Why does a PriorityQueue iterator not necessarily produce sorted output?
4. State one important difference between HashSet and TreeSet.
5. Why can mutating an object stored in a HashSet cause lookup problems?

Long Answer Questions

1. Compare ArrayList and LinkedList in terms of structure, access, insertion, removal, memory, and suitable applications.
2. Explain how equality, hashing, and comparison determine uniqueness in HashSet and TreeSet.
3. Describe the operations and performance model of ArrayDeque, including its use as both a stack and a queue.
4. Explain why collection order should be treated as a contract rather than inferred from observed output.
5. Develop a collection-selection framework for a system that requires duplicates, sorted reporting, priority processing, and fast membership testing.

Analytical / Application Questions

1. A program repeatedly checks whether millions of identifiers have already been processed. It does not require ordering. Which collection would you choose, and what correctness conditions must identifier objects satisfy?
2. A scheduler must process lower numeric priorities first and preserve arrival order when priorities are equal. Design the comparator and explain why iteration alone is insufficient.
3. A developer uses ArrayList as a FIFO queue by repeatedly removing index 0. Analyse the complexity problem and propose a better implementation.

Multiple Choice Questions with Answers

Question 1

Which collection is most appropriate for frequent indexed access and append operations?

A. ArrayList

B. TreeSet

C. PriorityQueue

D. HashSet

Correct Answer: A. ArrayList

Question 2

Which collection preserves insertion order while preventing duplicates?

A. HashSet

B. LinkedHashSet

C. TreeSet

D. ArrayDeque

Correct Answer: B. LinkedHashSet

Question 3

What is the typical complexity of contains in a HashSet under good hashing assumptions?

A. O(n²)

B. O(log n)

C. Average O(1)

D. O(n) always

Correct Answer: C. Average O(1)

Question 4

What determines the next element returned by PriorityQueue.poll()?

A. Insertion order only

B. The priority ordering

C. Random selection

D. The iterator's display order

Correct Answer: B. The priority ordering

Question 5

Which implementation provides sorted unique elements and logarithmic typical updates?

A. ArrayList

B. LinkedHashSet

C. TreeSet

D. ArrayDeque

Correct Answer: C. TreeSet

Question 6

Why can LinkedList.get(index) be slow?

A. It sorts before every access

B. It must generally traverse nodes to reach the index

C. It hashes the index twice

D. It copies all elements into a tree

Correct Answer: B. It must generally traverse nodes to reach the index

Question 7

Which collection rejects null elements as part of its normal contract?

A. HashSet

B. LinkedHashSet

C. ArrayDeque

D. ArrayList

Correct Answer: C. ArrayDeque

Question 8

What is the usual complexity of PriorityQueue.peek()?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: A. O(1)

Question 9

Which implementation is especially suitable for efficient operations at both ends?

A. ArrayDeque

B. TreeSet

C. HashSet

D. ArrayList

Correct Answer: A. ArrayDeque

Question 10

What problem can occur when a field used by hashCode changes while an object is in a HashSet?

A. The set automatically sorts the object

B. The object may no longer be found or removed normally

C. The set converts into a list

D. All duplicate objects are deleted

Correct Answer: B. The object may no longer be found or removed normally