Implementation of Queue using Linkedlist in Java

Question

Can someone please review my code? Is it the correct implementation of a queue? If not, please give suggestions on how to implement it using a linked list.

class Queue { Node front,rear; class Node { int data; Node next; public Node(int d) { data=d; next=null; } } void enqueue(int new_data) { Node new_node=new Node(new_data); if(front==null) { new_node.next=front; front=new_node; rear=front; } else if(rear.next==null) { rear.next=new_node; rear=rear.next; } System.out.println(rear.data+"\t Enqueued"); } Node dequeue() { if(front==null && rear==null) { System.out.println("\t Queue is Empty"); return null; } else { Node temp=front; front=temp.next; temp.next=null; System.out.println(temp.data+"\t Dequeued"); if(front==null) { rear=front; } System.out.println(front +" "+ rear); return temp; } } public static void main(String[] args) { Queue q=new Queue(); q.enqueue(1); q.enqueue(2); q.enqueue(3); q.enqueue(4); q.dequeue(); q.dequeue(); } } 

Answer 1

Formatting

Your indentation is all over the place. Using a consistent form of indenting that reflects the scoping of statements makes your code much easier to read and makes bugs easier to spot.

Consistency

Be consistent with your interface. You define enqueue in terms of the data item that is to be stored in the queue. This is good, because it hides the implementation. However, you define dequeue as returning a Node. This is bad, Node is an implementation detail, there's no reason for the caller to need to know it exists. dequeue should instead be returning an int (as this is the type stored in the queue).

Print statements

Your print statements don't belong in your queue. Part of the reason that you originally submitted code that didn't allow access to the values stored in the queue is because you put the print statements within it. Separate the concerns of your classes and test the boundaries. If you had originally tried to write your print statements in your main is would have become clear that you needed dequeue to return something in order for you to be able to print it.

Mains don't belong in collections

Your main method doesn't belong in the Queue. It's not part of the Queue, it's part of your test harness. You should put it in a different class. This will help to enforce the boundaries between what is the Queue's responsibilities and what is not the Queue's responsibilities.

Returns & Elses

Where possible you want to avoid nesting statements too far. In your dequeue, you're doing this:

if(front==null && rear==null) { System.out.println("\t Queue is Empty"); return null; } else { 

This creates a layer of nesting for the else statement. You don't need the else. When the if condition is matched, you return from the function. The only way you get past the statement is if the condition didn't match, so the else is redundant.

Redundant checks

In enqueue you perform:

else if(rear.next==null) 

You don't have an else condition for this check, and if this condition is triggered, it means that rear isn't pointing at the end of the queue and you've got something very wrong with your collection. Either remove the if check, since it can't happen, or throw an exception when it does, don't just pretend everything is all right.