---
title: "Circular queue using linked list"
subject: "Data Structure and Algorithm"
chapter: 4
key: "semester_4/data_structure_and_algorithm:circular-queue-linked-list"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/circular-queue-linked-list
site: BCT Engineering
---

# Circular queue using linked list

Data Structure and Algorithm · Chapter 4: Linked lists

- Asked in: 2073 Magh, 8 marks
- Video: [Circular Queue Implementation - Linked List](https://www.youtube.com/watch?v=vTjFPOYaHnI) — Blue Tree Code
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/circular-queue-linked-list
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-4

## Question

Write complete algorithm to implement circular queue linked list.

## Short answer

Maintain a rear pointer to the list’s last node; enqueue inserts a node after rear and updates rear; dequeue removes the front node (rear->next) and adjusts rear if the queue becomes empty. Both operations are O(1).

## Answer

A **circular queue using a linked list** is a singly linked list whose last node points back to the first node. One pointer `rear` pointing to the last node is enough: `rear->next` is the **front** node. Insertion is done after `rear`, deletion from `rear->next`.

```text
 rear
  |
  v
 [10|*]->[20|*]->[30|*]--+
  ^ (front)               |
  +-----------------------+
```

```c
struct node { int info; struct node *next; };
struct node *rear = NULL;       /* NULL means queue is empty */
```

#### ENQUEUE(x)
1. Create node `p`; if malloc fails print "overflow" and stop. `p->info = x`.
2. If `rear == NULL` (empty): `p->next = p` (points to itself).
3. Else: `p->next = rear->next` (new node points to the front); `rear->next = p`.
4. `rear = p`.

#### DEQUEUE()
1. If `rear == NULL`, print "underflow" and stop.
2. `f = rear->next` (front node); `x = f->info`.
3. If `f == rear` (only one node): `rear = NULL`.
4. Else: `rear->next = f->next`.
5. `free(f)`; return `x`.

#### DISPLAY()
If `rear == NULL` print "empty". Else `p = rear->next; do { print p->info; p = p->next; } while (p != rear->next);`

```c
void enqueue(int x) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (!p) { printf("Overflow\n"); return; }
    p->info = x;
    if (rear == NULL) p->next = p;
    else { p->next = rear->next; rear->next = p; }
    rear = p;
}
int dequeue(void) {
    if (!rear) { printf("Underflow\n"); return -1; }
    struct node *f = rear->next; int x = f->info;
    if (f == rear) rear = NULL;
    else rear->next = f->next;
    free(f);
    return x;
}
```

#### Trace
| Operation | Queue (front to rear) | rear |
|---|---|---|
| enqueue 1, 2, 3 | 1 2 3 | 3 |
| dequeue -> 1 | 2 3 | 3 |
| enqueue 4 | 2 3 4 | 4 |
| dequeue x3 -> 2, 3, 4 | empty | NULL |

(The C code was compiled and run on this sequence: it gives 1, then 2, 3, 4.) Both operations are O(1) and no space is wasted, unlike an array queue.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In the circular linked queue with only rear kept, where is the front?
   A. rear
   B. rear->prev
   C. start
   D. rear->next
   Answer: D. The last node points to the first node. (Key point: Front location)

2. When enqueuing into an empty queue, what is done?
   A. p->next = p and rear = p
   B. p->next = NULL
   C. rear->next = p
   D. front = NULL
   Answer: A. A single node in a ring points to itself. (Key point: Enqueue empty)

3. For a non-empty queue, which steps enqueue?
   A. rear->next = p; p->next = NULL
   B. p->next = rear->next; rear->next = p; rear = p
   C. p->next = rear; rear = p
   D. rear = p only
   Answer: B. The new node goes between rear and front and becomes the new rear. (Key point: Enqueue normal)

4. In dequeue, when f == rear, what happens?
   A. rear->next = f->next
   B. f is not freed
   C. rear = NULL as the queue becomes empty
   D. rear = f->next
   Answer: C. Only one node existed, so it is removed and the queue is empty. (Key point: Dequeue last)

## Related in Data Structure and Algorithm

- [Circular queue algorithm with conditions](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Acircular-queue-algorithm-conditions) — Data Structure and Algorithm, chapter 2
- [Implement BST using doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abst-using-doubly-linked-list) — Data Structure and Algorithm, chapter 6
- [Stack and queue using linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-queue-singly-linked-list) — Data Structure and Algorithm, chapter 4, asked 2×
- [Enqueue and dequeue in circular queue](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Acircular-queue-insert-delete) — Data Structure and Algorithm, chapter 2, asked 2×
- [Circular queue vs linear queue](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Acircular-vs-linear-queue) — Data Structure and Algorithm, chapter 2
- [Circular queue with display operation](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Acircular-queue-enqueue-dequeue-display) — Data Structure and Algorithm, chapter 2