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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes that's a great point! Thanks for the clear ansnwer $\endgroup$
    – CodyBugstein
    Mar 10, 2013 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, 2013 at 0:08
5
$\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.

Improve this answer
$\endgroup$
1
  • $\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, 2013 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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