The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details. 
Home Queues and Priority Queues Linked Queue  
Search the VIAS Library  Index  
Linked Queue
We would like an implementation of the Queue ADT that can perform all operations in constant time. One way to accomplish that is to implement a linked queue, which is similar to a linked list in the sense that it is made up of zero or more linked Node objects. The difference is that the queue maintains a reference to both the first and the last node, as shown in the figure. Here's what a linked Queue implementation looks like: public class Queue {public Node first, last; public Queue () { first = null; last = null; } public boolean empty () { return first == null; } } So far it is straightforward. In an empty queue, both first and last are null. To check whether a list is empty, we only have to check one of them. insert is a little more complicated because we have to deal with several special cases. public void insert (Object obj) {Node node = new Node (obj, null); if (last != null) { last.next = node; } last = node; if (first == null) { first = last; } } The first condition checks to make sure that last refers to a node; if it does then we have to make it refer to the new node. The second condition deals with the special case where the list was initially empty. In this case both first and last refer to the new node. remove also deals with several special cases. public Object remove () {Node result = first; if (first != null) { first = first.next; } if (first == null) { last = null; } return result; } The first condition checks whether there were any nodes in the queue. If so, we have to copy the next node into first. The second condition deals with the special case that the list is now empty, in which case we have to make last null. As an exercise, draw diagrams showing both operations in both the normal case and in the special cases, and convince yourself that they are correct. Clearly, this implementation is more complicated than the veneer implementation, and it is more difficult to demonstrate that it is correct. The advantage is that we have achieved the goal: both insert and remove are constant time.


Home Queues and Priority Queues Linked Queue 