Hi, I have to make a linked-node based priority queue for an assignment. For some reason, however, the enqueue and dequeue just won't work. I have honestly no idea why, because I think the algorithm should work.

Can anyone point out the problem? It would be greatly appreciated.

public class LinkedQueue implements PriorityQueue<Passenger>{
	private int length;
	private LinkedNode head;
	
	public LinkedQueue(){
		length = 0;
		head = null;
	}
	
	public LinkedQueue(LinkedNode headNode){
		length = 1;
		head = headNode;
	}
	
	/**
	 * Is there anything in the queue?
	 * @return true if the queue is empty; otherwise return false
	 */
	public boolean isEmpty(){
		if(length == 0){
			return true;
		}
		else if(length > 0){
			return false;
		}
		else{
			return false;
		}
	}

		/**
	 * Add passenger to the queue (at the appropriate location).
	 * @param toInsert Passenger to be added
	 */
	public void enqueue(Passenger toInsert){
		LinkedNode thisToInsert = new LinkedNode(toInsert);
		if(length == 0){
			//When it is the first Passenger entered.
			head = thisToInsert;
			head.changePrev(null);
			head.changeNext(null);
			length++;
		}
		else{
			//When it is not the first Passenger.
			LinkedNode currentNode = head;
			int compared = toInsert.compareTo(currentNode.getValue());
			while(currentNode.getNext() != null){
				if(compared == -1){
					if(currentNode.getPrev() == null){
						//When it is less than the first node.
						head = thisToInsert;
						head.changeNext(currentNode);
						head.getNext().changePrev(head);
						length++;
					}
					else{
						thisToInsert.changeNext(currentNode);
						thisToInsert.changePrev(currentNode.getPrev());
						currentNode.changePrev(thisToInsert);
						length++;
					}
				}
				else{
					currentNode = currentNode.getNext();
				}
			}
			if(currentNode.getNext() == null){
				//When it reaches the end of the list.
				if(compared == -1){
					//When it is less than the last node.
					thisToInsert.changeNext(currentNode);
					thisToInsert.changePrev(currentNode.getPrev());
					currentNode.changePrev(thisToInsert);
				}
				if(compared == 1){
					//When it is more than the last node.
					thisToInsert.changeNext(null);
					thisToInsert.changePrev(currentNode);
					currentNode.changeNext(thisToInsert);
				}
				length++;
			}
		}
	}

	/**
	 * Removes and returns the item at the front of the queue.
	 * @return the removed element
	 */
	public Passenger dequeue(){
		Passenger nextPass = head.getValue();
		if(head.getNext() != null){
			head = head.getNext();
			head.changePrev(null);
		}
		else{
			head = null;
		}
		length--;
		return nextPass;
	}
}

Edited 5 Years Ago by da10x: n/a

getValue and getNext return the Passenger object the node is holding and the next node, respectively.

This article has been dead for over six months. Start a new discussion instead.