Dequeue an item from a set of 1 elements

Question

Given a singly linked list implementation of a queue type with front and rear pointers, when you dequeue an item from a set of 1 elements, do you need to need to set the rear pointer to null?

I'm reading C++ Plus Data Structures by Nell Dale, and in chapter 5.2 he writes in his Dequeue method:

if (front == NULL)
  rear == NULL;

I'm wondering why is this necessary. The only reason I can think of is the way he implements Enqueue in regards to an empty set:

if (rear == NULL)
  front = newNode;
else
  rear->next = newNode;
rear = newNode;

But couldn't this condition be changed to if (front == NULL)

eh9 eh9 · Accepted Answer · 2016-06-28T13:22:16

For correct code, you need to maintain the data structure invariants with each operation. The way the original code is written, the invariants look like this:

A1: front points to the first element, if it exists; NULL otherwise
A2: rear points to the last element, if it exists; NULL otherwise

You're claiming that the invariants could alternatively be these:

B1: front points to the first element, if it exists; NULL otherwise
B2: rear points to the last element, if it exists

Now these are similar, but not at all identical. The B invariants don't require any particular value of rear when the list is empty. Now you can use the B invariants to implement the list, sure, since it admits discrimination between empty and non-empty states, and that's enough to provide correct implementations.

But that doesn't say anything about whether A or B is better in practice. If you use the B invariants, a function to peek at the last element cannot simply return the value of rear, since its value can be anything if the queue is empty; you have to test the front value first.

// for the A2 invariant
return rear ;

// for the B2 invariant
return ( front == NULL ) ? NULL : rear ;

This boils down to whether to want to test-and-assign when you dequeue or whether to want to test when you peek at the last element. This is an optimization question, not a correctness one. If you never need to peek at the last element, you can optimize for that.

All this said, this a prime case for the hazards of premature optimization. An extra pointer assignment to NULL is almost never going to be a performance problem. What's much more likely to be a problem is introducing a defect during maintenance when someone relies on the A invariants when the existing code is using the B ones. The A invariants are cognitively simpler, because front and rear are set up analogously, with neither having special behavior. The B invariants might perform better, but at the cost of complexity. Either choice might be better depending on your circumstances.

The Moral Of This Story: Always document your invariants.

Dequeue an item from a set of 1 elements

1 Answers