6
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes that's a great point! Thanks for the clear ansnwer $\endgroup$ – CodyBugstein Mar 10 '13 at 21:10
  • 1
    $\begingroup$ Nitpickery: the doubly-linked list uses twice as many links, but this is only twice as much memory if your data structures are literally empty other than their navigation links, in which case a queue is rather pointless... $\endgroup$ – Steven Stadnicki Mar 12 '13 at 0:08
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 Thanks for the clear answer as well. I accepted Pal's answer because it is slightly better, but this would do the trick too. $\endgroup$ – CodyBugstein Mar 10 '13 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.