Deleting the Last Node in a Singly Linked List Queue
The canteen at a higher secondary school issues tokens through a C++ program that implements a queue as a singly linked list. Each node stores a token number and a pointer to the next node; the class keeps head for the front and tail for the rear. Enqueue inserts after tail; dequeue removes the front node. During a 30-minute break the counter serves 120 tokens and the queue never holds more than 30 waiting. After the last token is served, the program crashes when the next student arrives. The teacher finds that dequeue() executes head = head->next; but never frees the removed node and never changes tail. A student proposes replacing the linked list with an array of 50 token numbers, arguing that the maximum is known and the code would be shorter. The teacher wants a fix that is correct even when the queue becomes empty, and a reasoned choice between the two implementations.
1. Identify the two defects in `dequeue()` and describe the exact sequence that produces the crash.
Read the worked answer
The first defect is that the removed node is never freed, so every served token leaks one node. The second defect is that tail is not updated when the queue becomes empty. Suppose the queue has one node. head = head->next makes head null, but tail still points to the old node, which is now unreachable from head. The next enqueue executes something like tail->next = newNode, writing through a stale pointer. That is undefined behaviour and commonly crashes or corrupts memory. There is also a missing empty-queue check: calling dequeue when head is null would dereference a null pointer. A correct dequeue must first reject an empty queue, save the front node, advance head, set tail to null if head became null, and only then delete the saved node.
2. Write corrected `dequeue()` and `enqueue()` functions for this queue, including the empty-queue cases. Explain why the order of statements matters.
Read the worked answer
bool dequeue(int &out) {
if (head == nullptr) return false;
Node *temp = head;
out = temp->data;
head = head->next;
if (head == nullptr) tail = nullptr;
delete temp;
return true;
}
void enqueue(int value) {
Node *n = new Node{value, nullptr};
if (tail == nullptr) {
head = tail = n;
} else {
tail->next = n;
tail = n;
}
}
The order matters because tail must stop pointing at the old node before that node is deleted. If delete temp ran first, the later check on head would still work, but any use of tail or temp after deletion would be invalid. Saving temp keeps the node alive long enough to copy its data and relink head. Setting tail = nullptr when the queue becomes empty makes the next enqueue take the empty-queue branch instead of writing through a dangling pointer. The enqueue empty case is also essential: when both head and tail are null, the new node becomes both ends.
3. The student recommends an array of 50 token numbers instead of a linked list. Which implementation should the teacher choose, and what condition would reverse your recommendation?
Read the worked answer
For this canteen, the array is the better choice. The observed maximum is 30 waiting, so an array of 50 gives a safe margin. If it is used as a circular queue with front and rear indices, enqueue and dequeue are O(1), no heap allocation is needed, and there are no dangling-pointer or memory-leak bugs. The code is also easier to audit in a school lab. The linked list becomes preferable only if the maximum cannot be bounded, if the queue must grow without a fixed limit, or if nodes must be inserted or removed in the middle. A condition that would reverse the decision is a requirement to handle an unpredictable rush exceeding 50 entries without rejecting students; then a linked list or a dynamically resizing circular buffer is more suitable. The array must still check for full and empty conditions, and a plain array that shifts all elements on every dequeue would be a poor choice.