Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Implement queue using linkedlist. Looking for 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());
        }
    }
}
share|improve this question
    
I don't see any implements Queue<T> in your code, which I would expect to see from the "implement Queue" description... –  Simon André Forsberg Jun 23 at 0:36

2 Answers 2

  • 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 getCount should be called size to be conformant with other classes.

  • I prefer when people use just one signal for the system state. In your code, you use size == 0 in some places to determine if the queue is empty, and in other places you use front == null

Otherwise the code looks functional, and neat.

share|improve this answer
    
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. –  toto2 Jun 22 at 21:46
    
@toto2 - in this sense, functional as in, 'gets the job done, and no apparent bugs' –  rolfl Jun 22 at 22:02

Most coding conventions require that nested classes appear in a particular position within the enclosing scope - commonly at the bottom; see java.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 using isEmpty() 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 get O(1) insert and remove behavior.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.