Which of the following data structures can erase from its beginning or its end in O(1) time?

What the interviewer wants to learn

  • Whether you know the fundamental properties of common data structures.
  • If you can quickly identify the operations each structure supports and their time complexities.
  • Your ability to reason about trade‑offs (e.g., memory overhead vs. operation speed).

How to structure your answer

1. Restate the question briefly to confirm understanding.

2. List the candidate data structures.

3. For each, state the time complexity of erasing from the front and the back, citing the underlying implementation (array, linked list, deque, etc.).

4. Summarize which structures meet the O(1) requirement for both ends.

5. Optionally, mention any edge cases (empty container, amortized vs. worst‑case).

Example answer

"The question asks which data structures can remove an element from either the beginning or the end in constant time. The usual suspects are:

  • **Array‑based list (e.g., Python’s list, Java’s ArrayList)** – removing from the end is O(1) because we just decrement the size, but removing from the front requires shifting all remaining elements, so it’s O(n).
  • **Singly linked list** – we can pop from the front in O(1) by moving the head pointer, but popping from the back needs traversal to the previous node, which is O(n).
  • **Doubly linked list** – both head and tail pointers are maintained, so we can delete from either end in O(1).
  • **Deque (double‑ended queue) implemented as a circular buffer or a doubly linked list** – it provides O(1) erase at both ends by design.

Therefore, a doubly linked list and a properly implemented deque satisfy the O(1) requirement for erasing from both the beginning and the end."

Mistakes to avoid

  • **Confusing amortized with worst‑case**: some array‑based deques give O(1) amortized but occasional O(n) resizing; clarify if the interview expects worst‑case guarantees.
  • **Leaving out edge cases**: mention what happens when the structure is empty (operation may raise an exception or be a no‑op).
  • **Listing only one side**: the question explicitly asks for both ends; don’t claim O(1) for just one side.
  • **Over‑explaining unrelated structures**: keep the answer focused on the listed options; extra detail can dilute the point.

More system design questions