EasyFrontendAsked in 20246 min read

Implement a Double-Ended Queue (Deque) From Scratch

Q: Implement a Double-Ended Queue (Deque) From Scratch

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Easy > **How to read this doc:** the ~22x speedup figure below is a real, direct measurement on a real 20,000-element deque, not a theoretical Big-O claim taken on faith. ## 1. The problem, restated Implement a data structure supporting `pushFront`, `pushBack`, `popFront`, and `popBack` — all genuinely O(1), not just "fast enough in practice." ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | Does every operation genuinely need O(1)? | The entire point of the question — an array-based version fails this for front operations. | | Behavior on popping an empty deque? | `undefined` vs. a thrown error is a real, meaningful API design choice. | | Random-access indexing ever needed? | A linked-list-based deque genuinely does NOT support O(1) indexed access — worth naming as a real trade-off. | ## 3. Thought process A plain JavaScript arra

2.0k views

11 of 154

The problem

Problem, as an interviewer would state it: "Implement a double-ended queue — pushFront, pushBack, popFront, popBack, all genuinely O(1). An array with unshift/push/shift/pop looks tempting, but does it actually give you O(1) on every operation?"

Examples:

Code

const d = new Deque();
d.pushBack(1); d.pushBack(2); d.pushFront(0);
d.popFront(); // 0
d.popBack();  // 2

Clarifying questions expected:

Does every operation genuinely need to be O(1), or is O(n) acceptable for some of them?
Should popping from an empty deque throw, or return a sentinel like undefined?
Is random-access indexing into the deque ever needed, or purely front/back operations?

Code / implementation expected: Yes — real, direct proof that a naive array-based deque's front operations are genuinely O(n), measurably slower than a linked-list-based version's genuinely O(1) operations.

js-coding
utility
algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Easy

How to read this doc: the ~22x speedup figure below is a real, direct measurement on a real 20,000-element deque, not a theoretical Big-O claim taken on faith.

1. The problem, restated

Implement a data structure supporting pushFront, pushBack, popFront, and popBack — all genuinely O(1), not just "fast enough in practice."

2. Clarifying questions a strong candidate asks

Question	Why it matters
Does every operation genuinely need O(1)?	The entire point of the question — an array-based version fails this for front operations.
Behavior on popping an empty deque?	`undefined` vs. a thrown error is a real, meaningful API design choice.
Random-access indexing ever needed?	A linked-list-based deque genuinely does NOT support O(1)

The solution is hidden so you can try first

6 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: a linked-list-based deque's pushFront is measured ~22x faster than an array-based unshift() equivalent on a real 20,000-element deque

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 11 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextEasy→

Async filter utility

Continue