9
\$\begingroup\$

For understanding the concepts, I've implemented the Queue data structures using a linked list. Is there anything to improve?

LinkList.java

public class LinkList {

    private static class Node<T> {

        private final T data;
        private Node next;

        public Node(T data){
            this.data=data;
        }


        public void displayNode(){
            System.out.print(data+ " ");
        }

    }

    private Node first = null;
    private Node last = null;

    public boolean isEmpty() {
        return (first == null);
    }

    public <T> void addLast(T data) {
        Node n = new Node(data);
        if (isEmpty()) {
            n.next = first;
            first = n;
            last = n;
        } else {
            last.next = n;
            last = n;
            last.next = null;
        }

    }

    public void removeFirst() {

            Node temp = first;
            if (first.next == null)
                last = null;
            first = first.next;

        }


    public void displayList() {
        Node current = first;
        while (current != null) {
            current.displayNode();
            current = current.next;
        }
    }

}

LinkListQueue.java

public class LinkListQueue {

    LinkList newLinkList = new LinkList();

    public <T> void enqueue(T data) {
        newLinkList.addLast(data);
    }

    public void dequeue() {
        if(!newLinkList.isEmpty())
            newLinkList.removeFirst();

    }

    public void displayQueue() {
        newLinkList.displayList();
        System.out.println();
    }

    public boolean isEmpty(){
        return newLinkList.isEmpty();
    }

}

LinkListQueueDemo.java

public class LinkListqueueDemo {

    public static void main(String[] args) {

        LinkListQueue queueImpl = new LinkListQueue();

        queueImpl.enqueue("A");
        queueImpl.enqueue("B");
        queueImpl.enqueue("C");
        queueImpl.enqueue("D");
        queueImpl.displayQueue();
        queueImpl.dequeue();
        queueImpl.displayQueue();

    }

}
\$\endgroup\$
2

1 Answer 1

16
\$\begingroup\$

BUG:

public void removeFirst() {

        Node temp = first;
        if (first.next == null)
            last = null;
        first = first.next;

    }

This crashes if you have an empty list. Add a check for first == null. Additionally... what's that temp variable for?


Don't define the Node as T, define the List to contain T.

public class LinkList<T>

This because you use the T outside the Node class and you ended up having to add it to the addLast method.


    if (isEmpty()) {
        n.next = first;
        first = n;
        last = n;
    } else {
        last.next = n;
        last = n;
        last.next = null;
    }

You already know that n.next is null. You also know that first is null, because that's what defines isEmpty().

So instead, try this:

    if (isEmpty()) {
        first = n;
    } else {
        last.next = n;
    }
    last = n;
    last.next = null;

It does the same thing.


Design:

You have an insert (enqueue) method... but there's no way to retrieve an object that went into the Queue. removeFirst could return the object. This drastically cuts down on the uses of such an object (it's useless now).

\$\endgroup\$
0

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