LinkedList Queue implementation

Question

I'm working on a project which simulates (very simple/watered down) a network. The basis of this is to learn how to implement a Queue. I understand there are many ways to go about this, but I ultimately went with a LinkedList mainly because of it's nature (FIFO) which makes it easy to utilize in a Queue. I would appreciate any feedback on my implementation, and would also greatly appreciate with any critiques on my Queue's toString(), I know it is an unconventional way of doing it but I thought it would by a nice chance to work on recursion.

The data class in the this project is the Packet. It represents a packet and code is as follows. I've omitted the getters and setters for brevity:

private static int packetCount; // Determined at the time of the objects creation [incremental] private int id; // Assigned by packetCount private int packetSize; // Size of the packet being sent private int timeArrive; // Creation "time stamp" private int timeToDest; // Number of simulation units it took for the packet to arrive to destination /** * Default constructor */ public Packet() { id = 0; packetSize = 0; timeArrive = 0; timeToDest = 0; } public Packet(int id, int packetSize, int timeArrive, int timeToDest) { this.id = id; this.packetSize = packetSize; this.timeArrive = timeArrive; this.timeToDest = timeToDest; } @Override public String toString() { return "Packet #" + id + " => arrive at simulation unit: " + timeArrive + " => packet size: " + packetSize; } } 

Here is my Node class:

public class Node { private Packet data; private Node next; private Node prev; public Node() { next = null; data = null; prev = null; } public Node(Packet data) { this.data = data; next = null; prev = null; } public Packet getData() { return data; } public Node getNext() { return next; } public Node getPrev() { return prev; } public void setData(Packet data) { this.data = data; } public void setNext(Node next) { this.next = next; } public void setPrev(Node prev) { this.prev = prev; } } 

And my Queue class which is actually a router within this simulation:

/** * Represents a router on the network [queue] */ public class Router{ private Node head; private Node tail; int size; public Router() { head = null; tail = null; size = 0; } public boolean isEmpty() { return head == null; } public int size() { return size; } public void enqueue(Packet packet) { Node node = new Node(packet); if(head == null) { head = node; tail = node; } tail.setNext(node); node.setPrev(tail); tail = node; size++; } public Packet dequeue(){ if(isEmpty()) { try { throw new Exception("Underflow"); } catch (Exception e) { e.printStackTrace(); } } Node ptr = head; head = ptr.getNext(); if(head == null) { tail = null; } size--; return ptr.getData(); } public Packet peek() { if(isEmpty()) { try { throw new Exception("Underflow"); } catch (Exception e) { e.printStackTrace(); } } return head.getData(); } public String recToString(StringBuilder strBlder, Node cursor) { if(cursor !=head) { strBlder.append(cursor.getData().toString() + "\n"); recToString(strBlder, cursor.getPrev()); } strBlder.append(cursor.getData().toString()); return strBlder.toString(); } @Override public String toString() { StringBuilder s = new StringBuilder(); return recToString(s, tail); } } 

Answer 1

Packet

private static int packetCount; // Determined at the time of the objects creation [incremental] 

I would remove this field. Personally I feel it's odd for a Packet to need to know the number of packets. Apart from that you would need to synchronize access to this field, should your class ever be used in a multi-threading environment.

Node

• make data final. A node should never change it's data once created. Remove the setter as well.
• Remove the default constructor public Node(). It is unused and does not initialize the (now final) field data.
• rename the field data to packet. A clear naming will help other developers and your future self remember what is stored here.

Router

size should be private too

public void enqueue(Packet packet) { Node node = new Node(packet); if (head == null) { head = node; tail = node; } tail.setNext(node); node.setPrev(tail); tail = node; size++; } 

if head == nullyou set head = tail = node. You now have three references to the same Packet object. After that you set next and prev on this object to itself.

public Packet dequeue() { Node ptr = head; head = ptr.getNext(); if (head == null) { tail = null; } size--; return ptr.getData(); } 

If now dequeue is called, head is assigned to ptr (which is the Packet pointing forward and backward to itself. head is assigned ptr.next which means, it is still the same object. head == null will never be true. For every subsequent call to dequeue you will get that Packet.

If another Packet ist enqueued the next call to dequeue will return the first Packet once more and then return the new Packet, removing it from your list.

To fix that, change enqueue to

public void enqueue(Packet packet) { Node node = new Node(packet); if (head == null) { head = node; tail = node; } else { tail.setNext(node); node.setPrev(tail); tail = node; } size++; } 

Are you sure, that the output created by recToString is what you want/need?

Calling

router.enqueue(new Packet(11, 11, 11, 11)); router.enqueue(new Packet(22, 22, 22, 22)); router.enqueue(new Packet(33, 33, 33, 33)); System.out.println(router.toString()); 

yields the output:

Packet #33 => arrive at simulation unit: 33 => packet size: 33 Packet #22 => arrive at simulation unit: 22 => packet size: 22 Packet #11 => arrive at simulation unit: 11 => packet size: 11Packet #22 => arrive at simulation unit: 22 => packet size: 22Packet #33 => arrive at simulation unit: 33 => packet size: 33 

Since you implement FIFO I think, the first (head) element should be printed first.

Remove recToString and replace toString:

@Override public String toString() { StringBuilder result = new StringBuilder(); Node current = head; while (current != null) { result.append(current.getData().toString()).append("\n"); current = current.getNext(); } return result.toString(); } 

It now starts at head and walks forward through the list till it hits the end.

With recToString removed the only call to Node#getPrev() got removed, too. A FIFO-structure does not need to be double linked. Let's remove it.

Node:

public class Node { private Packet data; private Node next; public Node(Packet data) { this.data = data; next = null; } public Packet getData() { return data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } 

Router#enqueue()

public void enqueue(Packet packet) { Node node = new Node(packet); if (head == null) { head = node; tail = node; } else { tail.setNext(node); tail = node; } size++; } 

Edit:Forgot my own comment.

Exception handling

Create your own Exception:

public class QueueEmptyException extends RuntimeException { public QueueEmptyException() { } public QueueEmptyException(final String message) { super(message); } public QueueEmptyException(final String message, final Throwable cause) { super(message, cause); } public QueueEmptyException(final Throwable cause) { super(cause); } public QueueEmptyException(final String message, final Throwable cause, final boolean enableSuppression, final boolean writableStackTrace) { super(message, cause, enableSuppression, writableStackTrace); } } 

Create a method that throws the Exception, if the queue is empty:

private void assertNotEmpty() { if (isEmpty()) { throw new QueueEmptyException("Queue is emtpy"); } } 

Change peek

public Packet peek() { assertNotEmpty(); return head.getData(); } 

and dequeue

public Packet dequeue() { assertNotEmpty(); [...] } 

Answer 2

• Since you handle data in FIFO order, I don't see the need for the prev. In any case if you use it, make sure that dequeue clears head.prev after node removal.

• As pointed by @Mpirious, catching your own exceptions doesn't make sense. What's worse, after detecting an empty queue the code keeps going.

• Getters and setters in Node do not serve any purpose: private members with unrestricted access are as good as public.