Implement queue with a linked list; why would it be bad to insert at the head and remove at the tail?

Question

In my textbook, Data Structures and Algorithms in Java, the author says when implementing a queue using a linked list you choose the front of the queue to be at the head of the list, and the rear of the queue to be at the tail of the list. In this way, you remove from the head and insert at the tail.

The author then asks cryptically, "Why would it be bad to insert at the head and remove at the tail?" without providing an answer.

I can't see what the difference really is. In effect, "Head" and "Tail" are just arbitrary names we define. What would be so bad if to enqueue() we add a head and create a reference to the old head, and to dequeue() we take from the tail and move the tail over?

What is the answer to the author's question?

Answer 1

In a single linked list, every element has a pointer to the next element. If you have an additional pointer to the tail element, it takes you a constant number og operations to add to the list at the tail: get the tail pointer, add an element after the tail, put this new element as new tail. Removing from the head also takes a constant number of operations: make you new item new, head, point to old head.

However, removing from the tail demands a pointer to the predecessor to the current tail. This takes you as many operations as there are elements, namely linearly many.

Another solution is to use a doubly linked list, then you can choose what you will, but it uses twice as much memory.

Answer 2

Removing from the head and inserting at the tail are both constant time operations with a singly linked list, assuming head and tail pointers. Inserting at the tail is also constant time. But removing from the tail means moving the tail pointer toward the head, and since you don't have a back pointer you can't do that without traversing the whole list to find the element previous to the tail. This makes insertion a linear time instead of a constant time operation and that's why it's worse.