webentwicklung-frage-antwort-db.com.de

Java in sortierte verknüpfte Liste einfügen

Ich habe diesen Code unten, wo ich eine neue Ganzzahl in eine sortierte LinkedList von Ints einfüge, aber ich denke nicht, dass dies die "richtige" Art ist, Dinge zu tun, da ich weiß, dass es eine einzige Linkedlist mit Zeiger auf den nächsten Wert und eine doppelt Linkedlist gibt Zeiger auf den nächsten und vorherigen Wert. Ich habe versucht, mit Nodes den unten angegebenen Fall zu implementieren, aber Java importiert diesen Import org.w3c.dom.Node (Document Object Model), also stecken geblieben.

Einfügungsfälle

  1. In leeres Array einfügen
  2. Wenn der Wert kleiner als alles ist, fügen Sie den Anfang ein.
  3. Wenn der Wert größer als alles ist, fügen Sie den letzten ein.
  4. Kann dazwischen liegen, wenn der Wert in LL unter oder über bestimmten Werten liegt.

    import Java.util.*;
    
    public class MainLinkedList {
    public static void main(String[] args) {
    LinkedList<Integer> llist = new LinkedList<Integer>();
    
    llist.add(10);
    llist.add(30);
    llist.add(50);
    llist.add(60);
    llist.add(90);
    llist.add(1000);
    System.out.println("Old LinkedList " + llist);
    
    //WHat if you want to insert 70 in a sorted LinkedList
    LinkedList<Integer> newllist = insertSortedLL(llist, 70);
    System.out.println("New LinkedList " + newllist);
    }
    
    public static LinkedList<Integer> insertSortedLL(LinkedList<Integer> llist, int value){
    
        llist.add(value);
        Collections.sort(llist);
        return llist;
    
    }
    

    }

7
cloudviz

Dies könnte Ihren Zweck perfekt erfüllen:

Verwenden Sie diesen Code:

import Java.util.*;

public class MainLinkedList {
    private static LinkedList<Integer> llist;

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

        addValue(60);
        addValue(30);
        addValue(10);
        addValue(-5);
        addValue(1000);
        addValue(50);
        addValue(60);
        addValue(90);
        addValue(1000);
        addValue(0);
        addValue(100);
        addValue(-1000);
        System.out.println("Linked List is: " + llist);

    }

    private static void addValue(int val) {

        if (llist.size() == 0) {
            llist.add(val);
        } else if (llist.get(0) > val) {
            llist.add(0, val);
        } else if (llist.get(llist.size() - 1) < val) {
            llist.add(llist.size(), val);
        } else {
            int i = 0;
            while (llist.get(i) < val) {
                i++;
            }
            llist.add(i, val);
        }

    }

}

Diese eine Methode verwaltet das Einfügen in die Liste auf sortierte Weise, ohne Collections.sort(list) zu verwenden.

6
Master

Wenn wir listIterator verwenden, ist die Komplexität für das Ausführen von get O (1). 

public class OrderedList<T extends Comparable<T>> extends LinkedList<T> {

    private static final long serialVersionUID = 1L;


    public boolean orderedAdd(T element) {      
        ListIterator<T> itr = listIterator();
        while(true) {
            if (itr.hasNext() == false) {
                itr.add(element);
                return(true);
            }

            T elementInList = itr.next();
            if (elementInList.compareTo(element) > 0) {
                itr.previous();
                itr.add(element);
                System.out.println("Adding");
                return(true);
            }
        }
    }
}
16
Amruth

@Atrakeur

"Das Sortieren der Liste jedes Mal, wenn Sie ein neues Element hinzufügen, ist nicht effizient."

Das stimmt, aber wenn die Liste immer in einem sortierten Zustand sein soll, ist sie wirklich die einzige Option.

"Der beste Weg ist, das Element direkt an der richtigen Stelle einzufügen, an der es sich befinden muss. Dazu können Sie alle Positionen durchlaufen, um herauszufinden, wo diese Nummer liegt."

Genau das macht der Beispielcode.

"oder verwenden Sie Collections.binarySearch, damit dieser hochoptimierte Suchalgorithmus diese Aufgabe für Sie erledigen kann"

Die binäre Suche ist effizient, jedoch nur für Listen mit wahlfreiem Zugriff. Sie können also eine Array-Liste anstelle einer verknüpften Liste verwenden, müssen sich jedoch mit Speicherkopien beschäftigen, wenn die Liste wächst. Sie benötigen auch mehr Speicher, als Sie benötigen, wenn die Kapazität der Liste höher ist als die tatsächliche Anzahl der Elemente (was ziemlich üblich ist).

Welche Datenstruktur/-methode zu verwenden ist, hängt also stark von Ihren Speicher- und Zugriffsanforderungen ab.

[edit] Tatsächlich gibt es ein Problem mit dem Beispielcode: Er führt beim Durchlaufen der Schleife zu mehreren Scans der Liste. 

int i = 0;
while (llist.get(i) < val) {
    i++;
}
llist.add(i, val);

Der Aufruf von get (i) wird die Liste einmal durchlaufen, um zur i-ten Position zu gelangen. Dann wird der Aufruf zum Hinzufügen (i, val) erneut durchlaufen. Das wird also sehr langsam sein.

Ein besserer Ansatz wäre, einen ListIterator zu verwenden, um die Liste zu durchlaufen und das Einfügen durchzuführen. Diese Schnittstelle definiert eine add () - Methode, mit der das Element an der aktuellen Position eingefügt werden kann.

1
Greg Brown

Schauen Sie unter com.google.common.collect.TreeMultiset nach.

Dies ist effektiv eine sortierte Menge, die mehrere Instanzen desselben Werts zulässt.

Es ist ein schöner Kompromiss für das, was Sie zu tun versuchen. Das Einfügen ist billiger als ArrayList, aber Sie erhalten immer noch die Vorteile der binären Suche/Baumstruktur.

1
DanJ

Sie können dies in log (N) time Komplexität einfach tun. Keine Notwendigkeit, alle Werte zu durchlaufen. Sie können die binäre Suche verwenden, um der sortierten verknüpften Liste einen Wert hinzuzufügen. Fügen Sie einfach den Wert an der Position der oberen Grenze dieser Funktion hinzu. Code überprüfen ... Sie können es besser verstehen.

    public static int ubound(LinkedList<Integer> ln, int x) {
        int l = 0;
        int h = ln.size();
        while (l < h) {
            int mid = (l + h) / 2;
            if (ln.get(mid) <= x) l = mid + 1;
            else h = mid;
        }
        return l;
    }

    public void solve() 
    {
        LinkedList<Integer> ln = new LinkedList<>();
        ln.add(4);
        ln.add(6);
        ln.add(ubound(ln, 5), 5);
        out.println(ln);

    }

Ausgabe: [4, 5, 6]

weitere Informationen zur binären Suche finden Sie unter: https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/

0
NIKUNJ KHOKHAR

Sie müssen herausfinden, wo die Daten eingefügt werden sollen, indem Sie die Bestellkriterien kennen.

Die einfache Methode besteht darin, die Einfügeposition brutal zu durchsuchen (Liste durchgehen, binäre Suche ...).

Wenn Sie die Art Ihrer Daten kennen, können Sie die Einfügeposition schätzen, um die Anzahl der Prüfungen zu reduzieren. Wenn Sie beispielsweise 'Zorro' einfügen und die Liste alphabetisch geordnet ist, sollten Sie am Ende der Liste beginnen ... oder die Position Ihres Buchstabens einschätzen (wahrscheinlich gegen Ende). Dies kann auch funktionieren Zahlen, wenn Sie wissen, woher sie kommen und wie sie verteilt werden. Dies wird Interpolationssuche genannt: http://en.wikipedia.org/wiki/Interpolation_search

Denken Sie auch an die Batch-Einfügung: Wenn Sie viele Daten schnell einfügen, können Sie in Erwägung ziehen, viele Einfügungen in einem Durchgang durchzuführen und nur einmal danach zu sortieren.

0

Verknüpfte Liste ist nicht die bessere Implementierung für eine SortedList

Das Sortieren der gesamten Liste jedes Mal, wenn Sie ein neues Element hinzufügen, ist nicht effizient. Am besten fügen Sie das Element direkt dort ein, wo es sich befinden muss (an seiner korrekten Position). Für So können Sie alle Positionen in einer Schleife durchlaufen, um herauszufinden, wo diese Nummer ist, und dann diese einfügen oder Collections.binarySearch verwenden, damit dieser hochoptimierte Suchalgorithmus diese Aufgabe für Sie erledigt.

BinarySearch gibt den Index des Objekts zurück, wenn das Objekt in der Liste gefunden wird (Sie können hier ggf. nach Duplikaten suchen) oder (- (Einfügepunkt) - 1), wenn das Objekt nicht bereits in der Liste vorhanden ist (und Einfügepunkt ist.) der Index, an dem das Objekt platziert werden muss, um die Reihenfolge zu erhalten)

0
Atrakeur