Queue Using Linked List

Table of Contents +

A queue made from an array works fine. But it has one annoying limit. You pick a size up front. Once those slots fill up, you are stuck. But what if you do not know how many items will arrive? That is the problem we solve here. We build the queue out of a linked list. A linked list is a chain of small boxes. Each box holds a value and points to the next box. Now the queue grows as long as you need. There is no fixed size at all.

📚 What Are We Building?

A queue follows FIFO. That means First In, First Out. The first person who joins the line is the first one served. You add at the back and remove from the front. It works just like a real line at a shop counter.

We will store each item in a node. A node is one small box. It holds a value and a pointer to the next box. To make both ends fast, we keep two pointers.

  • front points to the first node. We remove from here.
  • rear points to the last node. We add here.

Here is what the chain looks like with three items already inside. Read it left to right. The front pointer sits on the oldest item, 10. The rear pointer sits on the newest item, 30.

front

10

20

30

rear

(last node)

See how front holds the oldest item and rear holds the newest one? That is the whole trick. We keep both ends in our hand. So we never walk the list to reach them.

🎯 Why Two Pointers?

Think of a long line of people. Say you only knew where the front was. Then every time someone new wants to join the back, you would have to walk the whole line to find the end. That is slow.

So we keep a rear pointer too. It always remembers the last node. Now adding a new person at the back is instant. We attach them right after rear. Then we move rear forward.

  • front lets us remove the oldest item fast.
  • rear lets us add a new item at the back fast.

Both jobs become O(1). That means the work stays the same no matter how big the queue gets.

🛠️ The Two Main Operations

There are two things a queue must do.

  • enqueue means add an item at the rear.
  • dequeue means remove the item at the front.

Let us think about the tricky cases before we write code. These are the moments where things can go wrong if you are not careful.

When you enqueue, there is one case to watch. Is the queue empty right now? If yes, then this new node is both the front and the rear. If no, you attach it after the current rear.

When you dequeue, there is also a case to watch. Is the queue empty? If yes, there is nothing to remove, so you report that. Removing the last item is special too. After it leaves, the queue is empty. So rear must be cleared as well, not just front.

Caution

The common bug is forgetting rear when the queue becomes empty. You move front off the last node but leave rear pointing at the old node. Then the next enqueue attaches to a node that is already gone. So always clear rear when front becomes null.

📝 Steps to Enqueue (Add at Rear)

We add a new item at the back of the queue. Here is the plan.

  1. Make a new node and put the value inside it. Its next pointer is null.
  2. Is the queue empty? Check if front is null.
  3. If empty, set both front and rear to this new node.
  4. If not empty, set the old rear’s next pointer to the new node.
  5. Move rear forward to the new node.

📝 Steps to Dequeue (Remove from Front)

We remove the oldest item from the front. Here is the plan.

  1. Is the queue empty? Check if front is null. If yes, report that the queue is empty and stop.
  2. Save the value in the front node so we can return it.
  3. Move front forward to the next node.
  4. Was that the last node? If front is now null, set rear to null too.
  5. Return the saved value.

💻 The Code in 5 Languages

Now we put it all together. The code below builds a queue. It enqueues a few numbers. Then it peeks at the front. After that it dequeues until the queue is empty. Read the comments to follow each step.

queue_linked_list.py
# One box in the chain
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.front = None   # front removes
        self.rear = None    # rear adds


    # Add a value at the rear
    def enqueue(self, value):
        node = Node(value)
        if self.front is None:      # queue is empty
            self.front = self.rear = node
        else:                       # attach after old rear
            self.rear.next = node
            self.rear = node
        print(f"Enqueued {value}")


    # Remove a value from the front
    def dequeue(self):
        if self.front is None:      # nothing to remove
            print("Queue is empty")
            return None
        value = self.front.data
        self.front = self.front.next    # move front forward
        if self.front is None:          # removed the last node
            self.rear = None
        return value


q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(f"Front is {q.front.data}")
print(f"Dequeued {q.dequeue()}")
print(f"Dequeued {q.dequeue()}")
print(f"Dequeued {q.dequeue()}")
q.dequeue()                         # queue is empty now

The output of the above code will be:

Output
Enqueued 10
Enqueued 20
Enqueued 30
Front is 10
Dequeued 10
Dequeued 20
Dequeued 30
Queue is empty

Tip

Notice that enqueue and dequeue never use a loop. They just move one or two pointers. That is why both run in O(1) time, no matter how many items the queue holds.

⏱️ Time and Space Cost

Let us look at the cost of each operation. The good news is everything here is fast.

Operation Time Why
enqueue O(1) We attach at rear directly. No walking the list.
dequeue O(1) We remove at front directly. No walking the list.
peek (front) O(1) front already points to the first item.
space O(n) One node per item, plus a pointer in each node.

⚖️ Linked List Queue vs Array Queue

Both store a queue. So which one do you pick? It depends on whether you know the size ahead of time.

Point Linked List Queue Array Queue
Size Grows freely. No fixed limit. Fixed unless you resize the array.
Memory per item Extra, because each node stores a next pointer. Less, just the value.
Memory layout Nodes scattered around memory. One solid block, faster to scan.
enqueue / dequeue O(1) always. O(1), but may need to resize when full.

Note

Use the linked list version when you do not know how big the queue will get. Use the array version when you know the size. The array saves memory and runs a little faster on real machines.

🧩 What You’ve Learned

  • ✅ A queue is FIFO. You add at the rear and remove from the front.
  • ✅ A linked list queue keeps a front pointer and a rear pointer so both ends are fast.
  • ✅ enqueue attaches a new node at rear and moves rear forward.
  • ✅ dequeue saves the front value, moves front forward, and clears rear when the queue becomes empty.
  • ✅ Both enqueue and dequeue run in O(1) time, with no fixed size limit.
  • ✅ The one bug to watch is forgetting to set rear to null when the last item leaves.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why do we keep a separate rear pointer in a linked list queue?

    Why: The rear pointer always remembers the last node, so enqueue attaches a new node instantly without scanning.

  2. 2

    During dequeue, when must you also set rear to null?

    Why: If the removed node was the last one, front becomes null, so rear must be cleared too or the next enqueue breaks.

  3. 3

    What is the time cost of enqueue and dequeue in this linked list queue?

    Why: Both operations only move one or two pointers, so they take constant time no matter the queue size.

  4. 4

    What is the main advantage of a linked list queue over an array queue?

    Why: A linked list queue allocates a new node whenever needed, so it never runs out of fixed slots like an array.

Score: 0 / 4

🚀 What’s Next?

Previous Queue Using Array Next Circular Queue

Share & Connect

Share on LinkedIn