You need a pack lane (FIFO) and an undo stack (LIFO). LinkedList implements Deque, so it compiles. java.util.Stack is named Stack, so it also compiles. Both are the wrong default. One chases nodes. The other is a synchronized Vector with indexes you should not use.
ArrayDeque is the resizable ring buffer the JDK already named for those jobs. The Queue and Deque post owns the interface pairs. Deque as a layout owns the ADT diagrams. This post is the class you new: how the ring decides cost, why null is illegal, and when LinkedList still loses even though it is also a Deque.
The default for stack and queue
Program to Deque. Construct ArrayDeque. That pairing is the series default on the Collections Roadmap.
Deque<Order> lane = new ArrayDeque<>();
Deque<Order> undo = new ArrayDeque<>();
lane.offerLast(order("o-100", "SKU-1", "19.99"));
Order next = lane.pollFirst();
undo.push(next);
Order rolledBack = undo.pop();It implements Deque and, on Java 21, SequencedCollection — getFirst, getLast, reversed. It does not implement List. There is no get(i). That missing method is a feature.
| Fact | What it means on the hot path |
|---|---|
| Ring buffer | Ends are amortized O(1) — no remove(0) slide |
| Unbounded | offer does not return false for space; it grows |
No null | Empty slots in the array are null; a payload null would look like a hole |
Not a List | You cannot index. Do not iterate i times to fake get(i) |
| Not thread-safe | Another thread needs a concurrent deque or a blocking deque |
| Fail-fast iterator | Structural change during iteration → CME; see the roadmap |
new ArrayDeque<>(n) is an initial capacity, not a max. This is not ArrayBlockingQueue. When the ring is full, it grows. offer on ArrayDeque fails only for null.
Ring buffer: head, tail, wrap
Decision-level internals, not a copy of the OpenJDK file. The layout theory with wrap pictures is ds-deque. Here is what you need to pick the class.
An Object[] holds the elements. head is the index of the first element (removeFirst / pop / poll). tail is the index where the next addLast will write. The array is a circle: when an index walks off the end, it wraps with a mask. Capacity stays a power of two so wrap is bitwise AND, not %.
index: 0 1 2 3 4 5 6 7
slot: D E _ _ _ A B C
^tail ^head
logical order: A, B, C, D, EaddLast writes at tail and advances tail. addFirst moves head backward and writes there. removeFirst clears head (stores null so the slot is a hole again) and advances head. No element slides. That is why this beats ArrayList.remove(0) as a queue: the list copies a prefix; the ring moves an index.
Empty is head == tail. Full is “the next advance of tail would land on head.” Then the implementation allocates a larger array, copies the wrapped sequence into a linear layout, and resets the two indices.
Deque<Order> lane = new ArrayDeque<>(4); // enough for four, then grow
lane.addLast(order("o-1", "SKU-A", "1.00"));
lane.addLast(order("o-2", "SKU-B", "2.00"));
lane.addFirst(order("o-0", "SKU-Z", "0.50")); // wrap toward the other end
Order first = lane.removeFirst(); // o-0Both ends stay cheap because you move an index, not a block of references. Search and “element 17” are still a scan. If those are the hot operations, you wanted ArrayList.
Growth without Vector’s tax
java.util.Stack extends Vector. You inherit a synchronized, indexable list: a lock on every push, a capacityIncrement story, and insertElementAt sitting there for anyone who forgets this was supposed to be LIFO. Unused Vector capacity is a second array you are not using as a ring — it is leftover list capacity on a type that also pretends to be a stack. Legacy Collections is the museum tour.
ArrayDeque grows like a dynamic array: typically double, copy, continue. Usual insert is O(1). The growth copy is O(n) and amortized away the same way ArrayList.add is. The unused slots are holes in the circle (null cells between tail and head), not a synchronized Vector you did not want.
Deque<String> undo = new ArrayDeque<>(); // default initial ring: 16
for (int i = 0; i < 20; i++) {
undo.push("edit-" + i); // grows once past 16
}
String last = undo.pop(); // edit-19There is no trimToSize you will call in anger. If a deque spiked and you need the memory back, allocate a new one. Do not switch to Stack to “control capacity.”
The same LIFO job on Stack pays a lock you did not ask for and an index API you should not use:
Stack<Order> legacy = new Stack<>();
legacy.push(order("o-100", "SKU-1", "19.99"));
legacy.insertElementAt(order("o-099", "SKU-0", "4.00"), 0); // still a Vector
Order top = legacy.pop();
Deque<Order> undo = new ArrayDeque<>();
undo.push(order("o-100", "SKU-1", "19.99"));
// undo.get(0); // does not compile — the ring is not a Listsize() is how many orders are in the ring. You cannot ask the public API for the array length. Do not size-check in a loop hoping to avoid growth; if you already know the spike, pass it to the constructor once.
Note: Initial capacity is a hint for “I already know I have 10_000 orders.” It is not a bound. A bounded pack lane that must block when full is BlockingQueue, not a smaller ArrayDeque.
Lab: pick lane plus undo
Same Order / LineItem records as the rest of the series.
public record Order(
String id,
String customerEmail,
List<LineItem> items,
BigDecimal total,
boolean active) {}
public record LineItem(String sku, int quantity, BigDecimal unitPrice) {}
static Order order(String id, String sku, String total) {
BigDecimal price = new BigDecimal(total);
return new Order(
id,
id + "@ex.com",
List.of(new LineItem(sku, 1, price)),
price,
true);
}One ring for the pack lane, one ring for undo. A sliding window of the last three packed ids sits on a third deque — addLast, removeFirst when size exceeds three. That window is the same type, not a List.
Deque<Order> lane = new ArrayDeque<>();
Deque<Order> undo = new ArrayDeque<>();
Deque<String> lastPackedIds = new ArrayDeque<>();
lane.offerLast(order("o-100", "SKU-1", "19.99"));
lane.offerLast(order("o-101", "SKU-2", "12.00"));
lane.offerLast(order("o-102", "SKU-3", "5.00"));
Order packed = lane.pollFirst(); // o-100
undo.push(packed);
lastPackedIds.addLast(packed.id());
if (lastPackedIds.size() > 3) {
lastPackedIds.removeFirst();
}
Order mistake = undo.pop();
lane.offerFirst(mistake); // restored at the head
lastPackedIds.removeLast(); // window follows undoreversed() is a view of the same ring, not a copy. Walking newest-first without draining the lane:
for (Order newestFirst : lane.reversed()) {
System.out.println(newestFirst.id());
}Mutate through that view and the original deque changes. Snapshot with List.copyOf(lane.reversed()) when later packs must not leak into the report. Views vs copies live on the roadmap.
Expected pack order after the undo:
lane head → o-100, o-101, o-102
undo → empty
window → emptyPack three, then a fourth, and the window drops the oldest id:
for (String id : List.of("o-100", "o-101", "o-102", "o-103")) {
lastPackedIds.addLast(id);
if (lastPackedIds.size() > 3) {
lastPackedIds.removeFirst();
}
}
// window: o-101, o-102, o-103That is still one ArrayDeque. You did not need a List to remember “the last three.”
Not a List, not thread-safe, no nulls
Three refusals that show up in reviews.
Not a List. There is no index. This will not compile:
Deque<Order> lane = new ArrayDeque<>();
// Order third = lane.get(2); // no such methodDo not write a loop that polls into a throwaway list just to read [2]. If you need get(i), you needed ArrayList from the start. If you need ends and indexes, keep two structures or accept LinkedList’s costs — next section.
Not thread-safe. Two packers on one ArrayDeque is a data race. The iterator is fail-fast, which is not a memory barrier. Share a deque across threads with ConcurrentLinkedDeque or LinkedBlockingDeque, or do not share. Collections.synchronizedDeque still needs the iterator locked by you.
No null. The backing array uses null for empty slots. offer(null) throws NullPointerException. That also keeps pollFirst() honest: null means empty, not “a missing order.”
Deque<Order> lane = new ArrayDeque<>();
lane.offer(null); // NullPointerException
Order empty = lane.poll(); // null — the lane was emptyArrayDeque is not a concurrent queue and not a list. If the review comment is “but LinkedList does both,” keep reading.
LinkedList as List plus Deque — and why it still usually loses
LinkedList implements List and Deque. When a signature demands both, it is the honest JDK class. That combination is rare. The usual request is “I might need get(i) later,” which is not a need.
Ends on LinkedList are O(1) after a node allocation and a pointer chase. Each element is an object with two links. The ring is one array of references. Sequential scans hit cache. A linked list walks the heap. For a stack, a queue, or a sliding window, the ring wins on allocation and locality.
LinkedList.get(i) is O(n) and does not implement RandomAccess. Using it as a list because it is also a deque is how get(i) sneaks into a hot loop.
Deque<Order> asDeque = new LinkedList<>();
asDeque.offer(order("o-100", "SKU-1", "19.99"));
List<Order> asList = (List<Order>) asDeque;
Order surprise = asList.get(0); // compiles; still a node walkPrefer ArrayDeque over LinkedList-as-queue, and over LinkedList-as-stack. Reach for LinkedList when you already hold a node and need to splice, or when an API you do not own requires List and you genuinely live at the ends. Application checkout code almost never has that pair.
Allowing null is the other LinkedList “win.” It makes poll ambiguous. Skip it.
When not ArrayDeque
- You need index
i—ArrayList. Do not fake indexes on a deque. - You need a bounded, waiting hand-off. Producer blocks when full, consumer blocks when empty:
ArrayBlockingQueue/LinkedBlockingDeque. See BlockingQueue. - You need next-best, not next-arrived. That is PriorityQueue, a heap, not a ring.
- You need
Listmethods (subList,listIteratorat an index,set). That is a list.LinkedListwill compile. Measure before you keep it. - You need
nullelements. Fix the model. Do not switch implementations to storenull. - Another thread mutates it. Concurrent deque or confine the ring to one thread.
A queue of unique SKUs is still not a set. Put uniqueness in a HashSet and the lane in an ArrayDeque, or you will pack the same order twice.
Set<String> seen = new HashSet<>();
Deque<Order> lane = new ArrayDeque<>();
List<Order> arrivals = List.of(
order("o-100", "SKU-1", "19.99"),
order("o-100", "SKU-1", "19.99"),
order("o-101", "SKU-2", "12.00"));
for (Order incoming : arrivals) {
if (seen.add(incoming.id())) {
lane.offerLast(incoming);
}
}
lane.size(); // 2 — second o-100 skippedThe set answers “already queued?” The deque answers “who is next?” One type each.
Interview lens
Interviewers want “why not LinkedList / Stack,” not the bitmask.
Complexity they expect. addFirst / addLast / removeFirst / removeLast: amortized O(1). peekFirst / peekLast: O(1). contains / remove(Object): O(n). Growth copy: O(n) occasionally, amortized into the inserts. get(i): not on the type.
What to draw. A circle of slots, head and tail arrows, one wrap from the last index to 0. Write “empty: head == tail” and “grow when tail would land on head.” Beside it: Stack → Vector (lock + indexes); LinkedList → nodes. Circle ArrayDeque as the default.
Typical questions:
| Question | Honest answer |
|---|---|
Why does ArrayDeque beat LinkedList as a queue? | Contiguous ring, no per-element node, better cache. Ends stay amortized O(1) without pointer chasing. |
Why no null? | Holes in the array are null. A payload null is indistinguishable from a hole, and poll already returns null for empty. |
Is it a List? | No. No indexes. That is deliberate. |
| How does it grow? | Power-of-two ring; double and copy when full. new ArrayDeque<>(n) is initial size, not a max. |
Why not java.util.Stack? | Stack extends Vector: synchronized list from 1.0. Use Deque + ArrayDeque. |
| Thread-safe? | No. Use a concurrent / blocking deque, or do not share. |
| Stack and queue with one class? | Yes. Same ring, different ends (push/pop vs offerLast/pollFirst). |
When is LinkedList the deque? | Almost never. When you truly need List + Deque, or node splice. |
Wrong answer: “Use LinkedList for a queue because it is a linked list.” Textbook lists are not the JDK default. ArrayDeque is the queue and the stack until you have a measured reason otherwise.
Cheat sheet
Type ArrayDeque — Deque + SequencedCollection (Java 21); not List
Layout ring: Object[], head, tail, power-of-two wrap
Ends amortized O(1) contains / remove(Object) O(n)
Grow double + copy; constructor n is initial, not max
Nulls forbidden (NPE)
Threads not safe
Stack Deque.push / pop not java.util.Stack
Queue offerLast / pollFirst not ArrayList.remove(0)
Window addLast, removeFirst when size > n
Vs list LinkedList is List+Deque and still usually loses
Vs legacy Vector/Stack: see java-legacy-collectionsDo:
Deque<Order> q = new ArrayDeque<>();for stack, queue, and sliding window.- Size the constructor when you already know the spike; still treat it as unbounded.
- Link ds-deque when someone asks how wrap works on a whiteboard.
Don’t:
- Reach for
LinkedListbecause the word “list” appears in a queue textbook. - Use
java.util.StackorVectorfor LIFO. - Call
get(i)by draining into a list on every lookup.
Wrap-up
ArrayDeque is a ring buffer with two indices. That is enough for a FIFO pack lane, a LIFO undo stack, and a sliding window of recent ids — without Vector, without java.util.Stack, and without a node object per order. It refuses null, refuses indexes, and refuses to be shared across threads. LinkedList remains the List+Deque type and still loses for ordinary end work.
Unique SKUs are a different contract. That is the next default implementation in this wave.