Wie finden Sie die min/max-element der verketteten Liste

Habe ich eine doppelt verkettete Liste in meinem Fall. Und ich will zu finden, die max-und min-element. Also ich möchte das Sammlungen zu finden. Hier ist mein code unten Knoten zuerst:

public class Node<T> {
    Node<T> prev;
    Node<T> next;
    T data;

    public Node(T _data)
    {
        data = _data;
        prev = null;
        next = null;
    }

    public Node(T _data, Node<T> _prev, Node<T> _next)
    {
        data = _data;
        prev = _prev;
        next = _next;
    }

    T getData()
    {
        return data;
    }

    public void setNext(Node<T> _next)
    {
        next = _next;
    }

    public void setPrev(Node<T> _prev)
    {
        prev = _prev;
    }

    public Node<T> getNext()
    {
        return next;
    }

    public Node<T> getPrev()
    {
        return prev;
    }
}

Und hier ist meiner Doppelt verketteten Liste-Klasse:

public class DoublyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    int listCount = 0;

    public void traverseF()
    {
        Node<T> temp = head;

        while(temp != null)
        {
            System.out.print(temp.getData() + " ");
            temp = temp.getNext();
        }
    }

    public void traverseB()
    {
        Node<T> temp = tail;

        while(temp != null)
        {
            System.out.print(temp.getData() + " ");
            temp = temp.getPrev();
        }
    }

    public void insertFirst(T data)
    {
        Node<T> temp = new Node<T>(data);
        if(head == null)
        {
            head = temp;
            tail = temp;
            temp.setNext(null);
            temp.setPrev(null);
        }
        else
        {
            temp.setNext(head);
            head.setPrev(temp);
            head = temp;
        }
    }

}

So, mein main-code:

import java.util.Collections;


public class glavna {

    public static void main(String[] args) {
        DoublyLinkedList<Integer> DLL = new DoublyLinkedList<Integer>();

        DLL.insertFirst(32);
        DLL.insertFirst(22);
        DLL.insertFirst(55);
        DLL.insertFirst(10);

        DLL.traverseF();

        Integer max = Collections.max(DLL);

    }
}

Wie genau rufe ich die Sammlungen.max oder Sammlungen.min-Methode? Ist das nicht die Liste nur notwendig, um den max/min-Elemente?

public T getMin()
{
    Node<T> temp = head;
    T min = head.getData();
    while(temp.getNext() != null)
    {
        if(temp.getData() < min) //error
        {
            //min = temp.getData();
        }
    }
}

Ihre DoublyLinkedList umsetzen sollte Collection - Schnittstelle, d.h. public class DoublyLinkedList implements Collection. Dann werden Sie in der Lage zu nennen Collections.max(DLL)
Eine weitere alternative zur Implementierung der Collection-Schnittstelle, ist zu verfolgen, aktuelle min und max in Ihrem insertFirst() Methode. Dann erstellen Sie einfach eine getMin() und getMax() Methoden für die Rückgabe der Minimum-und maximum-Werte in O(1).
Was ist die "Collection" - interface? Gibt es irgendein Beispiel, wie kann ich das umsetzen? Danke.
siehe hier. Sie müssen implementieren iterator() vor allem, der rest könnte stubs. IMHO, dies ist ein overkill für die einfach Suche nach min/max. Warum kann man nicht einfach erstellen, einfach getMin/Max-Verfahren, zum Beispiel basierend auf Jose Rui Santos Vorschlag ?
Ich glaube, dass es mehr Sinn macht zu implementieren getMin/Max-Methoden in konventionellen O(N) Weg, vorausgesetzt, er eines Tages muss remove() Methode für seine Liste
Überprüfen Sie mein main-post, und sehen, ob es möglich soetwas zu machen? Ich habe eine Fehlermeldung, die sagt ich kann nicht mit den < Methode, es ist undefiniert. Wie kann ich weitermachen?
In diesem Fall, wenn das Element entfernt werden n im remove(n) entspricht der aktuellen min oder max, dann müssen wir nur noch die neue min oder max in O(n). Auf diese Weise können wir noch Getter in constanst Zeit O(1), da Sie in der Regel häufiger aufgerufen. Offensichtlich, dies ist nicht erforderlich, wenn die Liste auch sortiert halten. In diesem Fall min ist die erste elem, max der Letzte.
Naja, in Anbetracht der Sammlungen Methode würde eine Menge Dinge zu implementieren, fügen und lernen, ich werde gehen den einfacheren Weg und stellen Sie eine separate Funktion. Allerdings, da bin ich mit generics, ich kann nicht mit den <. Wie kann ich vergleichen die Elemente mit generischen Daten? Ich verwende nur ganze zahlen in das Programm, aber ich denke, ich muss implementieren Sie die Funktion mit generischen Typ, wenn ich entscheiden, zu verwenden, etwas anderes später.
Vergleichen Generika, Ihre T implementieren muss Comparable - Schnittstelle. Vergleichen Sie dann mit der compareTo Methode.
oder Sie können Comparator statt. Siehe meine Antwort

InformationsquelleAutor user12831231 | 2014-11-08

Umzusetzen getMin mit Generika, die Sie brauchen werden, um Sie vergleichen zu können. Sie können beispielsweise eine benutzerdefinierte Komparator zur Methode:

public T getMin(Comparator<? super T> comparator) {
    Node<T> temp = head.getNext();
    T min = head.getData();
    while(temp != null) {
        T candidateValue = temp.getData();
        if (comparator.compare(candidateValue, min) < 0) { //equivalent to candidate < min
            min = candidateValue;
        }
        temp = temp.getNext();
    }
    return min;
}

Dann, indem Sie mit Ihrer Methode für Integer :

getMin(new Comparator<Integer>() {
    @Override
    public int compare(Integer arg0, Integer arg1) {
        return arg0.compareTo(arg1);
    }
 });

Ein weiterer Ansatz ist, um Ihre Liste nur halten Vergleichbar Elemente :

public class DoublyLinkedList<T extends Comparable<? super T>> {

und dann haben Sie Ihre getMin() Methode verwenden compareTo Methode :

public T getMin() {
    Node<T> temp = head.getNext();
    T min = head.getData();
    while(temp != null) {
        T candidateValue = temp.getData();
        if (candidateValue.compareTo(min) < 0) { //equivalent to candidate < min
            min = candidateValue;
        }
        temp = temp.getNext();
    }
    return min;
}

Zweite Ansatz ist weniger ausführlich als Integer ist Comparable (d.h. implementiert, die Vergleichbar für Sie bereits), so brauchen Sie nicht, um jeden anderen code ändern.

In dieser Zeile: if (comparator.compareTo(min) < 0) was genau ist der comparator? Wo ist es definiert?
Es war ein Tippfehler, tut mir Leid, ich bearbeitete es. Es ist die candidateValue Vergleich mit min
Danke. Das scheint eine gute Lösung!

InformationsquelleAutor kiruwka

1

Liste ist keine Auflistung, so kann man nicht mit Sammlungen mit es.
- Gibt es eine kurzes Beispiel, wie kann ich auf meiner Liste eine Sammlung?
- Es muss implementieren interface der Sammlung zu einer Sammlung.
- Also, ich habe zu tun interface Collection{} und fügen Sie implements Collection in der Klasse, oder muss ich Sie deklarieren die Methoden innerhalb der Kollektion auch?
- Sie implementieren müssen, um die vorhandenen Sammlungen Schnittstelle. Es klingt wie Sie nicht vertraut sind mit Schnittstellen, so würde ich empfehlen, Lesen Sie auf Sie. Kurz gesagt, Sie definieren einen "Vertrag", aber du wirst auf jeden Fall brauchen, um Sie zu verstehen, ein wenig tiefer, bevor Sie werde in der Lage sein, dies zu beenden. Hier ist das erste tutorial das ich gefunden habe. tutorialspoint.com/java/java_interfaces.htm (ganz ehrlich, ich habe es nicht gelesen). Wenn Sie gelesen haben, und Sie haben implementiert das interface der Sammlung, werden Sie in der Lage, das zu tun, was Sie wollen.
InformationsquelleAutor kraskevich

Den Sammlungen.max Methode erwartet ein argument, das die Collection. Der einfachste Weg wäre wahrscheinlich zu erweitern AbstractCollection und fügen Sie diese Methoden:

@Override
public Iterator<T> iterator() {
    return new Iterator<T>() {
        private Node<T> node = head;
        @Override
        public boolean hasNext() {
            return node != null;
        }

        @Override
        public T next() {
            T next = node.data;
            node = node.getNext();
            return next;
        }
    };
}

@Override
public int size() {
    int size = 0;
    Node<T> node = head;
    while (node != null) {
        size++;
        node = node.getNext();
    }
    return size;
}

Das ist eine schöne Lösung, vielen Dank. Ich denke, es ist aus meinem Verständnis obwohl. Ich werde mein bestes tun, um es zu studieren.

InformationsquelleAutor August

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.