What Is a Deque? Constant-Time Access at Both Ends
A deque is a double-ended queue: values can enter or leave at either end. A doubly linked implementation makes all four end operations O(1), supporting sliding windows and both queue and stack behaviour.
A deque (pronounced "deck") is a double-ended queue. It supports four core operations: add to the front, add to the back, remove from the front, and remove from the back. A queue uses one end for insertion and the other for removal. A stack uses one end for both. A deque can do either.
How it works
A doubly linked deque stores a front pointer, a back pointer, and a size. Every
node has previous and next links. An end operation reconnects at most
two nodes; it never walks through the deque, so all four end operations are
O(1).
Its representation invariant has four parts: an empty deque has both ends
null; a non-empty deque has front.previous === null and
back.next === null; neighbouring links agree in both directions; and
count equals the number of reachable nodes. Every method below restores all
four before returning.
The empty and one-node cases are the important boundaries. In an empty deque, both pointers are null. In a one-node deque, both pointers name the same node. Removing that node must clear both pointers.
Press Run to execute this example. Use console.log to print a value.
The output is 1, 3, 2, then 0. Both ends are available, and removing one end does not move the middle values.
1
3
2
0
A numeric example
Start empty. pushBack(2) makes 2 both the front and back.
pushFront(1) creates 1 <-> 2. pushBack(3) creates 1 <-> 2 <-> 3.
Removing the front returns 1 and clears 2's previous link. Removing the back
returns 3 and clears 2's next link. Node 2 is again both ends.
Cost
| Operation | Doubly linked deque | Plain TypeScript array |
|---|---|---|
| Push front | O(1) | O(n) with unshift |
| Push back | O(1) | O(1) amortized with push |
| Pop front | O(1) | O(n) with shift |
| Pop back | O(1) | O(1) with pop |
| Read by index | O(n) | O(1) |
The linked deque uses O(n) nodes and two links per node. A circular-buffer deque also gives O(1) amortized end operations in an array by using modular indices and occasionally resizing. The linked representation offers simple pointer updates; the circular buffer generally has better memory locality.
Although each linked end operation is worst-case O(1), allocation and garbage collection still add real constant costs. Big O compares growth rates; it does not claim that every O(1) representation is equally fast.
In the course
A deque is useful for a monotonic sliding window: remove expired indices from the front and dominated values from the back. It also supports 0-1 breadth-first search, where zero-cost edges go to the front and one-cost edges go to the back. Ordinary unweighted breadth-first search needs only the queue subset.
Monotonic deque: one candidate per useful value
For a sliding-window maximum, store indices in decreasing value order. Before reporting a window, remove expired indices from the front. Before adding a new index, remove smaller or equal values from the back: the newer value dominates them because it is at least as large and expires later.
Press Run to execute this example. Use console.log to print a value.
The output is [ 3, 3, 5, 5, 6, 7 ]. The deque stores indices because expiry
depends on position. Its front is always the maximum for the current window;
its values decrease from front to back; and every stored index is still inside
the window. Each index enters once and leaves at most once, so all back-removal
loops together cost O(n). Occasional compaction discards the consumed prefix;
because it happens only after that prefix occupies at least half the backing
array, its total cost is amortized O(n), with O(k) space for window size k.
Common mistakes
Calling shift and unshift constant-time because each is one method call.
They still move array elements.
Updating only one link in a doubly linked node. If next.previous and
previous.next disagree, traversals in opposite directions see different
structures.
Forgetting to clear both pointers when the last node leaves. The empty invariant
is front === null and back === null.
Using a deque when random indexing is the repeated operation. A linked deque must walk to an index.
For a monotonic deque, storing only values makes duplicate expiry ambiguous. Failing to remove expired indices can report a value outside the window. Failing to remove dominated back entries preserves correctness but can waste space and obscures the linear-time proof.
When to use it
Use a deque when work enters or leaves at both ends: sliding-window algorithms, task scheduling, palindrome checks, or algorithms that sometimes prioritise new work at the front. It can also implement an ordinary queue or stack.
When not to
Use an array when random index access is central. Use a plain stack when only the newest value leaves, or a plain queue when only FIFO operations are needed and a head-indexed array is simpler.
FAQ
Is a deque the same as a queue?
A queue is FIFO: add at the back and remove from the front. A deque exposes both ends, so a queue is one restricted way to use a deque.
Why use two links per node?
The previous link lets the back move to its predecessor in O(1). With only
next, removing the back requires an O(n) walk to find that predecessor.
Is every deque operation O(1)?
The four end operations are O(1) in a doubly linked deque. Searching and reading an arbitrary index remain O(n). In a circular buffer, an occasional resize is O(n), so end operations are O(1) amortized.