Implement a queue using a linked list.
I'm looking for a code review, optimizations and best practices.
public class QueueAsLinkedList<T> { private Node<T> front; private Node<T> rear; private int size; public QueueAsLinkedList() {} private static class Node<T> { T item; Node<T> next; Node (T item, Node<T> next) { this.item = item; this.next = next; } } public void add(T item) { Node<T> node = new Node<T>(item, null); if (rear == null) { rear = node; front = node; } else { rear.next = node; } rear = node; size++; } public T remove() { if (front == null) { throw new NoSuchElementException(); } T item = front.item; front = front.next; if (front == null) { rear = null; } size--; return item; } public T peek() { if (front == null) { throw new NoSuchElementException(); } return front.item; } public int getCount() { return size; } public boolean isEmpty() { return size == 0; } public static void main(String[] args) { QueueAsLinkedList<Integer> ll = new QueueAsLinkedList<Integer>(); ll.add(1); ll.add(2); ll.add(3); while (!ll.isEmpty()) { System.out.println(ll.remove()); } }}
- \$\begingroup\$I don't see any
implements Queue<T>in your code, which I would expect to see from the "implement Queue" description...\$\endgroup\$Simon Forsberg– Simon Forsberg2014-06-23 00:36:38 +00:00CommentedJun 23, 2014 at 0:36
2 Answers2
There is no point in having the constructor for Node require the 'next' node. It is never part of the constructor, in your code.
The default constructor is useless code here. You may as well remove it, it does nothing.
the method
getCountshould be calledsizeto be conformant with other classes.I prefer when people use just one signal for the system state. In your code, you use
size == 0in some places to determine if the queue is empty, and in other places you usefront == null
Otherwise the code looks functional, and neat.
- \$\begingroup\$Funny... I'm not sure if you mean "functional" as in "working", or as in "functional programming". The linked list is the basic data structure in functional programming.\$\endgroup\$toto2– toto22014-06-22 21:46:46 +00:00CommentedJun 22, 2014 at 21:46
- \$\begingroup\$@toto2 - in this sense, functional as in, 'gets the job done, and no apparent bugs'\$\endgroup\$rolfl– rolfl2014-06-22 22:02:00 +00:00CommentedJun 22, 2014 at 22:02
Most coding conventions require that nested classes appear in a particular position within the enclosing scope - commonly at the bottom; seejava.util.LinkedList. There's no one right answer to where it should be, but in the middle of the class is a bit odd.
You should probably be usingisEmpty() as your state signal. That will cut down on the inconsistency issue raised by rolfl. Of course, to use isEmpty everywhere, you need to choose the correct implementation, and ensure that the modifications to the list are performed in a consistent order.
public boolean isEmpty() { return getCount() == 0;}public T remove() { if (isEmpty()) { throw new NoSuchElementException(); } T item = front.item; front = front.next; size--; if (isEmpty()) { rear = null; } return item;}add is really doing two different things; creating a new node, and inserting it into the list. These two chores should be made explicit
Node<T> createNode(T item) { return new Node<T>(item, null);}public void add(T item) { Node<T> node = createNode(item); add(node);}void add(Node<T> node) { if (isEmpty()) { front = node; } else { rear.next = node; } rear = node; size++;}If you are willing to jump through some extra hoops, you don't actually need the queue to contain two nodes -- one will suffice. The trick is implement a circular linked list. You still getO(1) insert and remove behavior.
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.