LinkedList & Queue Interface — Use LinkedList/Queue interface for FIFO patterns (intro) - Java

SECTION 1

Historical Context & Motivation

Long before computers existed, people were already using the idea of a queue every single day. Think about a line at the school cafeteria: the first person to arrive is the first person served. This first-in, first-out (FIFO) pattern turns out to be one of the most important ideas in computer science. Early programmers needed a way to manage tasks that should be handled in the exact order they arrive — from print jobs to network requests. Java's collections framework gives us clean, built-in tools to implement this pattern.

1950s • Queue Data Structure Formalized

Computer scientists formalized the queue as an abstract data type. Early operating systems used queues to schedule CPU tasks in the order they were submitted.

1996 • Java 1.0 and LinkedList

Java launched with the LinkedList class as part of the original java.util package, providing a doubly-linked list implementation.

1998 • Java Collections Framework (JCF)

Java 1.2 introduced the Collections Framework, bringing interfaces like List and reorganizing collection classes under a unified hierarchy.

2004 • Queue Interface Added (Java 5)

Java 5 added the Queue interface to the collections framework. LinkedList was updated to implement it, giving developers a standard FIFO contract.

2014+ • Modern Java & Streams

Java 8 and beyond brought lambda expressions and streams, making queues even more powerful for processing ordered sequences of data.

The central question this lesson addresses is straightforward: how do you store and retrieve elements in Java so that the first item you add is always the first item you remove? The Queue interface and the LinkedList class work together to solve exactly this problem.

SECTION 2

Core Principles & Definitions

Before diving into code, you need to understand four foundational ideas that make Java's Queue and LinkedList work. Each of these concepts builds on the previous one, so take them in order.

FIFO Principle

First-In, First-Out means the element that has been waiting the longest is the next one to be removed. Items enter at the back (tail) and leave from the front (head).

Interface vs. Implementation

The Queue interface defines what operations a queue must support (like offer, poll, peek). LinkedList is one concrete class that implements it.

Linked Nodes

A linked list stores each element in a node that points to the next (and previous) node. This makes adding and removing from either end an O(1) operation — perfect for a queue.

Program to the Interface

Best practice: declare your variable as Queue<T> rather than LinkedList<T>. This keeps your code flexible — you can swap in a different Queue implementation later without changing the rest of your program.

✦

KEY TAKEAWAY

Think of a queue like a drive-through lane at a fast-food restaurant. Cars enter at the back of the line and are served at the front. You can't cut ahead, and you can't back out once you've joined. In Java, offer() is like pulling into the lane, poll() is like getting your food and driving away, and peek() is like checking who's at the front window without actually serving them.

SECTION 3

Visual Explanation — How a Queue Works

The diagram below shows the internal structure of a LinkedList being used as a Queue. Each box represents a node that holds a value and a reference (pointer) to the next node. New elements enter at the tail, and elements are removed from the head.

Each node in the LinkedList holds one element and a reference to the next node. The head (front) is where poll() removes elements, and the tail (back) is where offer() adds them. The dashed box shows a new element about to be linked.

Notice how the linked structure makes FIFO operations efficient. When you call offer("Eve"), the list simply creates a new node and attaches it after the current tail — no shifting of existing elements is required. When you call poll(), the list removes the head node and updates the head pointer to the next node. Both operations happen in constant time, regardless of how many elements are in the queue.

SECTION 4

How It Works — The Queue API

The Queue interface in Java defines two styles of methods for each operation: one that throws an exception when something goes wrong, and one that returns a special value (like null or false). For most high school projects, the "special value" versions are more convenient because they avoid messy exception handling.

Operation	Throws Exception	Returns Special Value	Description
Insert	`add(e)`	`offer(e)`	Adds element to the tail of the queue
Remove	`remove()`	`poll()`	Removes and returns the head element
Examine	`element()`	`peek()`	Returns the head element without removing it

Queue interface methods — two styles for each operation

Declaring a Queue with LinkedList

Here is the standard way to create a queue in Java. Notice the left side uses the interface type and the right side uses the implementation type:

DECLARATION PATTERN

Queue<String> line = new LinkedList<>();

Queue<String> — the interface type (what operations are available). new LinkedList<>() — the concrete class that provides the actual storage. The <String> is a generic type parameter telling Java this queue holds String objects.

The Three Core Operations

OFFER — ADD TO TAIL

line.offer("Alice"); // Queue: [Alice]

Returns true if the element was added. For a LinkedList-backed queue, this always succeeds because LinkedList is unbounded.

POLL — REMOVE FROM HEAD

String served = line.poll(); // returns "Alice"

Returns the head element and removes it. If the queue is empty, returns null instead of throwing an exception.

PEEK — LOOK AT HEAD

String next = line.peek(); // returns head or null

Returns the head element without removing it. Useful for checking what's next in line.

SECTION 5

Detailed Breakdown — Queue Operations Step by Step

Let's trace through a complete sequence of queue operations to see exactly how the state changes. The diagram below shows a step-by-step timeline of a queue being built up and then consumed. Each row represents one operation, and the colored boxes show the queue's state after that operation completes.

This trace shows eight operations on a single queue. Green steps (offer) add elements to the tail. Pink steps (poll) remove from the head. Yellow (peek) inspects without modifying. Notice how A is always removed before B, and B before C — that's FIFO.

⚠

Common Pitfall

Calling poll() or peek() on an empty queue returns null. Always check for null or use isEmpty() before processing the result — otherwise you'll hit a NullPointerException later in your code.

SECTION 6

Worked Example — Customer Service Simulation

Let's build a small program that simulates a customer-service queue. Three customers join the line, and they're served one by one. We'll walk through every line of code.

Customer Queue Simulation

1
Step 1 — Import and Declare

First, import the necessary classes and create a queue variable. We declare it as Queue<String> to program to the interface: import java.util.LinkedList; import java.util.Queue; Queue<String> customers = new LinkedList<>();

An empty queue is created: []
2
Step 2 — Enqueue Customers

Use offer() to add three customers. Each call places the new customer at the tail of the queue. customers.offer("Maya"); // [Maya] customers.offer("Raj"); // [Maya, Raj] customers.offer("Zoe"); // [Maya, Raj, Zoe]

Queue state: [Maya, Raj, Zoe]
3
Step 3 — Peek at the Next Customer

Before serving, check who is first without removing them: System.out.println("Next: " + customers.peek()); This prints Next: Maya — the queue is unchanged.

Output: Next: Maya | Queue unchanged
4
Step 4 — Serve Customers with a Loop

Use a while loop to serve all customers. The loop continues as long as poll() returns a non-null value: String current; while ((current = customers.poll()) != null) { System.out.println("Serving: " + current); }

Output order: Serving: Maya → Serving: Raj → Serving: Zoe (FIFO confirmed!)
5
Step 5 — Verify Queue Is Empty

After the loop, the queue is empty. We can confirm: System.out.println(customers.isEmpty()); // true System.out.println(customers.peek()); // null

Queue is empty. isEmpty() returns true; peek() returns null

SECTION 7

Queue vs. Stack vs. ArrayList — When to Use What

Java gives you several data structures for storing collections of objects. Choosing the right one depends on the order in which you need to access elements. The table below compares three common options so you can decide which fits your problem.

Feature	Queue (LinkedList)	Stack	ArrayList
Access Order	FIFO — first in, first out	LIFO — last in, first out	Random — access by index
Add Operation	`offer()` — O(1)	`push()` — O(1)	`add()` — O(1) amortized
Remove Operation	`poll()` — O(1)	`pop()` — O(1)	`remove(0)` — O(n)
Best Use Case	Task scheduling, BFS, print queues	Undo operations, DFS, expression parsing	Frequent lookups by position, sorting
Null-safe remove?	Yes — `poll()` returns null	No — `pop()` throws exception	No — throws exception

Comparison of three common Java data structures

✦

KEY TAKEAWAY

If you need FIFO order (like a printer queue or a message system), use Queue. If you need LIFO order (like an undo button), use a Deque as a stack. If you need to jump to any position by index, use ArrayList. Don't try to use an ArrayList as a queue — removing from the front is O(n) because every other element has to shift over, like everyone in a movie theater moving down one seat.

SECTION 8

Connection to Advanced Queues

The basic Queue interface you've learned is just the starting point. Java provides several more specialized queue types that you'll encounter as you move into AP Computer Science A and beyond. Understanding the basic Queue interface gives you a solid foundation for all of them.

Basic Queue	Advanced Queue Type	Key Difference
`Queue<E>`	`Deque<E>`	Double-ended queue — add/remove from both ends. Can act as a queue or a stack.
`Queue<E>`	`PriorityQueue<E>`	Elements are served by priority (smallest first), not by arrival order.
`Queue<E>`	`BlockingQueue<E>`	Thread-safe queue for multi-threaded programs. Waits when empty or full.
`LinkedList`	`ArrayDeque`	Faster than LinkedList for most queue operations because it uses a resizable array internally.

Basic Queue vs. Advanced Variants

In particular, ArrayDeque is worth knowing about because Java's official documentation recommends it over LinkedList when you need a pure queue or stack. It avoids the memory overhead of creating a separate node object for every element. That said, LinkedList is still the most common choice in textbooks and AP exams, so mastering it first is the right move.

ℹ

Looking Ahead

Queues are essential in Breadth-First Search (BFS), one of the most important graph algorithms you'll learn in AP CS or college courses. BFS explores all neighbors at the current depth before moving deeper — and it uses a queue to track which node to visit next.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain the difference between poll() and peek(). If you called peek() three times in a row on a non-empty queue, would the return value change between calls? Why or why not?

Show answer

Both poll() and peek() return the head element, but poll() also removes it, while peek() leaves the queue unchanged. Therefore, calling peek() three times on a non-empty queue would return the same value every time because the head element is never removed. The queue's state remains identical after each call.

Question 2: BASIC CALCULATION

Given the following code, what does the final System.out.println output? Queue<Integer> q = new LinkedList<>(); q.offer(10); q.offer(20); q.offer(30); q.poll(); q.offer(40); System.out.println(q.peek());

Show answer

The output is 20. Here's the trace: after the three offer calls, the queue is [10, 20, 30]. The poll() removes 10 (the head), leaving [20, 30]. Then offer(40) adds 40 to the tail: [20, 30, 40]. Finally, peek() returns the head without removing it, which is 20.

Question 3: INTERMEDIATE

Write a method called reverseQueue that takes a Queue<String> and returns a new Queue<String> with the elements in reverse order. You may use any additional data structure. (Hint: which data structure naturally reverses order?)

Show answer

Use a Stack (or Deque used as a stack) as an intermediary. Poll all elements from the original queue and push them onto the stack. Then pop all elements from the stack and offer them into a new queue. Because a stack reverses order (LIFO), the new queue will have the original elements in reverse. The key insight is that pairing FIFO with LIFO produces a reversal. Example:

Deque<String> stack = new ArrayDeque<>(); while (!q.isEmpty()) stack.push(q.poll()); Queue<String> reversed = new LinkedList<>(); while (!stack.isEmpty()) reversed.offer(stack.pop());

Question 4: APPLIED

You're building a chat application that displays the last 5 messages. When a 6th message arrives, the oldest message should be removed. Write a code snippet using a Queue<String> that accepts a new message and enforces this 5-message limit. Include the condition check.

Show answer

Declare the queue: Queue<String> chatHistory = new LinkedList<>(); When a new message arrives: chatHistory.offer(newMessage); if (chatHistory.size() > 5) { chatHistory.poll(); } The offer() adds the new message at the tail. If the size exceeds 5, poll() removes the oldest message from the head. This pattern is sometimes called a "sliding window" and is very common in real applications like log viewers, chat windows, and data stream processing.

Question 5: CRITICAL THINKING

A classmate argues: "I can just use an ArrayList and call remove(0) to get FIFO behavior, so there's no reason to learn Queue." Write a paragraph explaining why this reasoning is flawed. Consider both performance and code design.

Show answer

While an ArrayList with remove(0) does produce FIFO behavior functionally, it has two major problems. First, performance: remove(0) on an ArrayList is O(n) because every remaining element must shift one position to the left. In a LinkedList-backed Queue, poll() is O(1) — a massive difference when the collection grows large. Second, code design: declaring your variable as Queue<E> communicates intent to anyone reading the code. It immediately signals FIFO semantics and restricts the available methods to queue-appropriate operations. Using ArrayList exposes methods like get(i) and set(i, e) that violate queue discipline, making bugs more likely. Programming to the interface is a core principle of clean, maintainable Java code.

SUMMARY

Lesson Summary

Summary

The Queue interface defines a FIFO (first-in, first-out) contract with three key operations: offer() adds to the tail, poll() removes from the head (returning null if empty), and peek() inspects the head without removing it. The LinkedList class implements this interface using a doubly-linked node structure, giving both offer() and poll() O(1) time complexity.

Always program to the interface by declaring variables as Queue<T> rather than LinkedList<T>. This makes your code more readable (it signals FIFO intent), more flexible (you can swap implementations), and less error-prone (you won't accidentally use non-queue methods). Queues are foundational in computing — from task scheduling and print jobs to the Breadth-First Search algorithm you'll encounter in more advanced courses.