Warteschlangenimplementierung mithilfe einer verknüpften Liste

71940
Arun Prakash

Um die Konzepte zu verstehen, habe ich die QueueDatenstrukturen mithilfe einer verknüpften Liste implementiert . Gibt es etwas zu verbessern?

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();

    }

}
Antworten
8
Wenn Sie Java 8 verwenden, ziehen Sie [optional] (http://docs.oracle.com/javase/8/docs/api/java/util/Optional.html) über `null` in Betracht. Toby vor 6 Jahren 0
Wenn Sie eine Warteschlange implementieren, sollten Sie die Implementierung der Warteschlange in Betracht ziehen: http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html raptortech97 vor 6 Jahren 0

1 Antwort auf die Frage

15
Pimgd

FEHLER:

public void removeFirst() {

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

    }

Dies stürzt ab, wenn Sie eine leere Liste haben. Fügen Sie einen Check für hinzu first == null. Zusätzlich ... wozu dient diese tempVariable?


Definieren Sie den Knoten nicht als T, sondern definieren Sie die zu enthaltende Liste T.

public class LinkList<T>

Dies liegt daran, dass Sie das T außerhalb der Node-Klasse verwenden und Sie es schließlich der addLast-Methode hinzufügen mussten.


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

Sie wissen bereits, dass n.nextdas null ist. Sie wissen auch, dass dies firstnull ist, weil es das ist, was definiert isEmpty().

Versuchen Sie es stattdessen so:

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

Es tut dasselbe.


Design:

Sie haben eine Insert-Methode (Enqueue-Methode), aber es ist nicht möglich, ein Objekt abzurufen, das in die Warteschlange eingereiht wurde. removeFirstkönnte das Objekt zurückgeben. Dies reduziert drastisch die Verwendung eines solchen Objekts (es ist jetzt nutzlos).