⌘K

Queue using Linked List

EasyProblemExternal linkUpdated Sep 26, 2026

Description

Build a queue on top of a singly linked list.

A queue works like the line at a ticket counter: people join at the back and are served from the front, so the value that arrived first is the first one to leave. This order is called FIFO (First-In, First-Out).

Implement the LinkedListQueue class:

LinkedListQueue() — creates an empty queue.
void push(int x) — adds x to the back of the queue.
int pop() — removes the value at the front of the queue and returns it. If the queue is empty, return -1.
int peek() — returns the value at the front of the queue without removing it. If the queue is empty, return -1.
boolean isEmpty() — returns true if the queue holds no values, false otherwise.

Store the values in linked-list nodes. A Node class with a value and a next link is provided in the starter code. The queue has no fixed capacity: it grows by one node on every push and shrinks by one node on every pop.

Goal: every operation should take constant time, O(1), no matter how many values are waiting in the queue.

Examples

Example 1

Input:

["LinkedListQueue", "push", "push", "push", "peek", "pop", "pop", "pop", "push", "isEmpty", "peek"]
[[], [10], [20], [30], [], [], [], [], [40], [], []]

Output:

[null, null, null, null, 10, 10, 20, 30, null, false, 40]

Explanation:

LinkedListQueue q = new LinkedListQueue(); — the queue starts empty.
q.push(10); — queue: [10]
q.push(20); — queue: [10, 20]
q.push(30); — queue: [10, 20, 30]. 10 is at the front, 30 at the back.
q.peek(); — returns 10, the value that has waited longest. Nothing is removed.
q.pop(); — returns 10 and removes it. queue: [20, 30]
q.pop(); — returns 20. queue: [30]
q.pop(); — returns 30. The queue is now empty.
q.push(40); — queue: [40]. An emptied queue must keep working normally.
q.isEmpty(); — returns false, because 40 is waiting.
q.peek(); — returns 40, which is both the front and the back.

Example 2

Input:

["LinkedListQueue", "isEmpty", "pop", "peek", "push", "peek", "isEmpty"]
[[], [], [], [], [7], [], []]

Output:

[null, true, -1, -1, null, 7, false]

Explanation:

isEmpty() — nothing has been pushed yet, so it returns true.
pop() — there is nothing to remove, so it returns -1.
peek() — there is nothing to look at, so it also returns -1.
push(7) — queue: [7]
peek() — returns 7.
isEmpty() — returns false, because 7 is waiting.

Example 3

Input:

["LinkedListQueue", "push", "push", "pop", "push", "peek", "pop", "pop", "pop"]
[[], [5], [8], [], [6], [], [], [], []]

Output:

[null, null, null, 5, null, 8, 8, 6, -1]

Explanation:

push(5), push(8) — queue: [5, 8]
pop() — returns 5, the older of the two. queue: [8]
push(6) — queue: [8, 6]
peek() — returns 8. 6 is newer, so 8 is still at the front.
pop() — returns 8. queue: [6]
pop() — returns 6. The queue is now empty.
pop() — returns -1, because nothing is left.

Constraints

1 ≤ total number of calls ≤ 1000 (including the constructor)
1 ≤ x ≤ 10^5
The first call is always LinkedListQueue()
pop and peek may be called on an empty queue; they return -1 in that case

Editorial

Brute Force - Walk to the End on Every Push

Intuition

A singly linked list gives us one natural handle: the head, its first node. Every other node is reached by following next links from there.

So which end of the list should be the front of the queue? Removing the head is cheap: move head to head.next and the old first node is gone. That makes the head the natural place for pop and peek. New values must then join at the other end, after the last node.

The most direct plan keeps only the head pointer. To push, start at the head and follow next links until you reach the node whose next is empty. That node is the last one, and the new node is linked after it.

Picture a line where the ticket counter only knows who is standing first. Every newcomer has to walk past the whole line, starting from the front, to find the last person and stand behind them.

Step-by-Step Explanation

Let's trace the first five calls of Example 1: push(10), push(20), push(30), peek(), pop().

Step 1: Start empty: head = null.

Step 2: push(10): the list is empty, so the new node [10] becomes the head.

head → [10] → null

Step 3: push(20): create [20] and start the walk at the head: curr = [10]. Is [10].next empty? Yes, so [10] is the last node.

Step 4: Link [20] after [10]. This push checked 1 node.

head → [10] → [20] → null

Step 5: push(30): create [30] and start the walk at the head again: curr = [10]. Is [10].next empty? No, it points to [20], so [10] is not the last node.

Step 6: Move curr to [20]. Is [20].next empty? Yes, so [20] is the last node.

Step 7: Link [30] after [20]. This push checked 2 nodes, one more than the previous push.

head → [10] → [20] → [30] → null

Step 8: peek(): return head.value = 10. Nothing changes.

Step 9: pop(): save head.value = 10 and move head to [20]. Return 10.

head → [20] → [30] → null

Notice the pattern: the push of the k-th value walks past k − 1 nodes. The list never remembers where it ends, so every push has to find the end again.

Head Pointer Only: Every Push Walks to the End — With only a head pointer, pop and peek are instant, but each push walks from the head to the last node before it can attach, and the walk gets longer as the queue grows.

Algorithm

Setup: keep one pointer, head, which is the front of the queue. It starts as null.

push(x):

Create a node holding x.
If head is null, make the new node the head and stop.
Otherwise set curr = head, and move curr = curr.next while curr.next is not null.
Set curr.next to the new node.

pop():

If head is null, return -1.
Save head.value.
Move head to head.next.
Return the saved value.

peek(): if head is null, return -1; otherwise return head.value.

isEmpty(): return whether head is null.

Code

struct Node {
    int value;
    Node* next;

    Node(int value) : value(value), next(nullptr) {}
};

class LinkedListQueue {
    Node* head = nullptr;  // front of the queue

public:
    LinkedListQueue() {}

    ~LinkedListQueue() {
        while (head != nullptr) pop();  // free every node still queued
    }

    void push(int x) {
        Node* node = new Node(x);
        if (head == nullptr) {
            head = node;
            return;
        }
        Node* curr = head;
        while (curr->next != nullptr) {  // walk to the last node on every push
            curr = curr->next;
        }
        curr->next = node;
    }

    int pop() {
        if (head == nullptr) return -1;
        Node* old = head;
        int value = old->value;
        head = head->next;
        delete old;
        return value;
    }

    int peek() {
        if (head == nullptr) return -1;
        return head->value;
    }

    bool isEmpty() {
        return head == nullptr;
    }
};

class Node:
    def __init__(self, value: int):
        self.value = value
        self.next = None


class LinkedListQueue:
    def __init__(self):
        self.head = None  # front of the queue

    def push(self, x: int) -> None:
        node = Node(x)
        if self.head is None:
            self.head = node
            return
        curr = self.head
        while curr.next is not None:  # walk to the last node on every push
            curr = curr.next
        curr.next = node

    def pop(self) -> int:
        if self.head is None:
            return -1
        value = self.head.value
        self.head = self.head.next
        return value

    def peek(self) -> int:
        if self.head is None:
            return -1
        return self.head.value

    def isEmpty(self) -> bool:
        return self.head is None

class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
    }
}

class LinkedListQueue {
    private Node head;  // front of the queue

    public LinkedListQueue() {
        head = null;
    }

    public void push(int x) {
        Node node = new Node(x);
        if (head == null) {
            head = node;
            return;
        }
        Node curr = head;
        while (curr.next != null) {  // walk to the last node on every push
            curr = curr.next;
        }
        curr.next = node;
    }

    public int pop() {
        if (head == null) return -1;
        int value = head.value;
        head = head.next;
        return value;
    }

    public int peek() {
        if (head == null) return -1;
        return head.value;
    }

    public boolean isEmpty() {
        return head == null;
    }
}

Complexity Analysis

Time Complexity: O(n) for push, O(1) for pop, peek and isEmpty

Here n is the number of values currently in the queue. push walks past every node to find the last one, so its cost grows with the queue. pop, peek and isEmpty only look at the head, so they take the same time however long the queue is.

Filling an empty queue with n values costs 0 + 1 + 2 + … + (n − 1) = n(n − 1)/2 node checks, which is O(n²) in total.

Space Complexity: O(n)

Each waiting value lives in one node (its value plus one next link). The walk itself uses only one extra pointer, curr.

Why This Approach Is Not Efficient

The cost of push grows with the queue. Pushing the k-th value walks past k − 1 nodes, so building a queue of n values costs about n²/2 steps, while pushing should cost the same small amount every time.

At this problem's limit of 1,000 calls that is under 500,000 steps, which still runs in time. But a queue is a building block that other programs lean on heavily: a server's line of waiting requests, or a breadth-first search over a very wide graph, can hold a million values at once. Filling a queue to that size with this push takes about 5 × 10^11 node checks, which is minutes to hours of work depending on the language, instead of a fraction of a second. A queue that slows down as it grows defeats its purpose.

Look at what the walk actually finds: the last node. We already knew that node one push ago, because we attached it ourselves, and then we threw that knowledge away.

The fix: keep a second pointer that always points at the last node, and update it on every push. The walk disappears, and push becomes constant time like the other three operations.

Optimal Approach - Front and Rear Pointers

Intuition

Keep two pointers into the list:

front points at the oldest node. pop and peek work here.
rear points at the newest node. push attaches here.

front → [10] → [20] → [30] ← rear

Why must the head be the front, and not the other way round? In a singly linked list, each node knows only the node after it. Removing the first node needs no search: move front one step forward. Removing the last node is different, because the node before it has to become the new last node, and finding that node means walking from the head. So values leave from the head and join at the tail. The only thing the brute force was missing was a record of where the tail is.

Two moments need extra care:

Pushing into an empty queue. There is no last node to link after, so the new node becomes both front and rear.
Popping the last value. When front moves past the final node it becomes null, and rear must be set to null too. If it is not, rear still points at the node that was just removed. The next push then links the new value onto that removed node, where nobody can reach it, and front stays null, so the queue looks empty even though a value was pushed.

Back to the ticket line: the counter now also knows who is standing last, so a newcomer goes straight to the back without walking along the line.

Step-by-Step Explanation

Let's trace all of Example 1: push(10), push(20), push(30), peek(), pop(), pop(), pop(), push(40), isEmpty(), peek().

Step 1: Start empty: front = null, rear = null.

Step 2: push(10): rear is null, so the queue is empty. The new node [10] becomes both front and rear.

Step 3: push(20): link [20] after the current rear: [10].next = [20].

Step 4: Move rear to [20]. No walking was needed.

front → [10] → [20] ← rear

Step 5: push(30): link [30] after the current rear: [20].next = [30].

Step 6: Move rear to [30].

front → [10] → [20] → [30] ← rear

Step 7: peek(): return front.value = 10. Nothing moves.

Step 8: pop(): save front.value = 10 and move front to [20]. Return 10.

Step 9: pop(): save 20 and move front to [30]. Return 20. Now front and rear point at the same node: one value is left.

Step 10: pop(): save 30 and move front to [30].next, which is null. At this moment rear still points at [30], a node that is no longer in the queue.

Step 11: Because front became null, set rear to null as well, then return 30. Both pointers are null again, exactly like the start.

Step 12: push(40): rear is null, so [40] becomes both front and rear, just like Step 2. If Step 11 had been skipped, [40] would have been linked after the removed [30] and front would still be null.

Step 13: isEmpty(): front is not null, so return false.

Step 14: peek(): return front.value = 40.

Every call touched at most two pointers. No call ever walked the list.

Front and Rear Pointers: Constant-Time Queue — Push attaches at the rear and pop removes at the front, so no call ever walks the list. Watch the rear pointer being cleared when the queue empties.

Algorithm

Setup: front = null, rear = null.

push(x):

Create a node holding x.
If rear is null (the queue is empty), set both front and rear to the new node.
Otherwise set rear.next to the new node, then move rear to the new node.

pop():

If front is null, return -1.
Save front.value.
Move front to front.next.
If front is now null, set rear to null as well.
Return the saved value.

peek(): if front is null, return -1; otherwise return front.value.

isEmpty(): return whether front is null.

Code

struct Node {
    int value;
    Node* next;

    Node(int value) : value(value), next(nullptr) {}
};

class LinkedListQueue {
    Node* front = nullptr;  // oldest node: pop and peek read here
    Node* rear = nullptr;   // newest node: push attaches here

public:
    LinkedListQueue() {}

    ~LinkedListQueue() {
        while (front != nullptr) pop();  // free every node still queued
    }

    void push(int x) {
        Node* node = new Node(x);
        if (rear == nullptr) {
            // Empty queue: the new node is both the front and the rear
            front = node;
            rear = node;
        } else {
            rear->next = node;  // link it after the current last node
            rear = node;
        }
    }

    int pop() {
        if (front == nullptr) return -1;
        Node* old = front;
        int value = old->value;
        front = front->next;
        if (front == nullptr) rear = nullptr;  // the queue just became empty
        delete old;
        return value;
    }

    int peek() {
        if (front == nullptr) return -1;
        return front->value;
    }

    bool isEmpty() {
        return front == nullptr;
    }
};

class Node:
    def __init__(self, value: int):
        self.value = value
        self.next = None


class LinkedListQueue:
    def __init__(self):
        self.front = None  # oldest node: pop and peek read here
        self.rear = None   # newest node: push attaches here

    def push(self, x: int) -> None:
        node = Node(x)
        if self.rear is None:
            # Empty queue: the new node is both the front and the rear
            self.front = node
            self.rear = node
        else:
            self.rear.next = node  # link it after the current last node
            self.rear = node

    def pop(self) -> int:
        if self.front is None:
            return -1
        value = self.front.value
        self.front = self.front.next
        if self.front is None:
            self.rear = None  # the queue just became empty
        return value

    def peek(self) -> int:
        if self.front is None:
            return -1
        return self.front.value

    def isEmpty(self) -> bool:
        return self.front is None

class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
    }
}

class LinkedListQueue {
    private Node front;  // oldest node: pop and peek read here
    private Node rear;   // newest node: push attaches here

    public LinkedListQueue() {
        front = null;
        rear = null;
    }

    public void push(int x) {
        Node node = new Node(x);
        if (rear == null) {
            // Empty queue: the new node is both the front and the rear
            front = node;
            rear = node;
        } else {
            rear.next = node;  // link it after the current last node
            rear = node;
        }
    }

    public int pop() {
        if (front == null) return -1;
        int value = front.value;
        front = front.next;
        if (front == null) rear = null;  // the queue just became empty
        return value;
    }

    public int peek() {
        if (front == null) return -1;
        return front.value;
    }

    public boolean isEmpty() {
        return front == null;
    }
}

Complexity Analysis

Time Complexity: O(1) for every operation

push: create one node and change at most two pointers.
pop: read one value and move one or two pointers.
peek and isEmpty: a single check of front.

None of this depends on how many values are waiting, so a sequence of m calls costs O(m) in total, compared with up to O(m²) for the brute force.

Space Complexity: O(n)

n is the number of values currently in the queue. Each one uses one node (its value plus one next link), and the two extra pointers stay the same whatever the size. Nothing is reserved in advance: memory grows by one node on each push and shrinks by one node on each pop. In C++, pop deletes the removed node and the destructor frees any nodes still in the queue; in Java and Python, a removed node is freed automatically once nothing points to it.

Comparison:

	Head pointer only	Front and rear pointers
push	O(n)	O(1)
pop	O(1)	O(1)
peek / isEmpty	O(1)	O(1)
n pushes in total	O(n²)	O(n)
Extra pointers kept	1	2

EASY

EASY

EASY

EASY

MEDIUM

EASY

EASY

MEDIUM

EASY

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY