Sort-Methode für die Doppelt verkettete Liste
Versuchen, herauszufinden, wie man meine doppelt verkettete Liste.
Ich bekomme eine null-Zeiger-Ausnahme hier:
while (temp.getNext()!=null){
Gibt es einen besseren Ansatz oder eine Beratung zu bekommen, diese gehen in die richtige Richtung?
public void sort() {
//bubble sort!
boolean swapped = (head != null);
while (swapped) {
swapped = false;
EntryNode temp = head;
//can't swap something with nothing
while (temp.getNext()!=null){
if (temp.getLastName().compareTo(temp.getNext().getLastName()) > 0) {
swapped = true;
//special case for two nodes
if (size == 2) {
//reassign head and tail
tail = temp;
head = temp.getNext();
tail.setPrev(head);
head.setNext(tail);
tail.setNext(null);
head.setNext(null);
}
//if swapping is at head
else {
if (temp == head) {
head = temp.getNext();
temp.setNext(head.getNext());
head.getNext().setPrev(temp);
head.setPrev(null);
head.setNext(temp);
temp.setPrev(head);
}
else {
temp.setNext(temp.getNext().getNext());
temp.setPrev(temp.getNext());
temp.getNext().setNext(temp);
temp.getNext().setPrev(temp.getPrev());
}
}
}
//loop through list
temp = temp.getNext();
}
}
}
- Dies hat zu den Hausaufgaben. Sie Sortieren nicht verlinkten Listen, die in der realen Welt.
- In der LISP-basierten Sprachen, die Sie Sortieren von verketteten Listen die ganze Zeit
Du musst angemeldet sein, um einen Kommentar abzugeben.
Verwenden Sie die merge-sort Algorithmus, ist oft die beste Wahl zum Sortieren einer (einfach oder doppelt) verkettete Liste. Es gibt bereits eine post der Diskussion der relevanten Fragen der Umsetzung.
Ich denke, Sie sollten prüfen:
weil Sie bereits die Zuordnung
am Ende der
while
Schleife.Dem einfachen Ansatz ist, um die Inhalte der Liste in ein array verwenden
Arrays.sort
im array sortiert, und schließlich den Wiederaufbau der Liste der sortierten array.O(NlogN)
Vergleiche ... das entspricht in etwaO(logN)
traversalen. Noch einmal, das hinzufügen einer Konstante 2 mehr traversalen ändert nichts an der Komplexität. (Die Sorten, die sind besser alsO(NlogN)
beziehen sich auf spezielle Eigenschaften der Domäne von Werten, die sortiert wird.)