Bestellte Linkliste:
Sortieren Sie nach Schlüsselwerten. Beim Löschen des Kettenkopfs wird der minimale (/maximale) Wert gelöscht. Suchen Sie beim Einfügen nach der Insertionsposition.
Beim Einfügen müssen Sie O (N), Durchschnitt O (N/2) vergleichen, und beim Löschen der minimalen (/maximalen) Daten am Kettenkopf ist die Effizienz O (1).
Wenn für eine Anwendung häufig Zugriff auf die kleinsten (/maximalen) Datenelemente einfügen/suchen/löschen), sind bestellte verknüpfte Listen eine gute Wahl. Vorrangige Warteschlangen können bestellte verknüpfte Listen verwenden, um die Sortierung der in der Insertion geordneten verknüpften Listen zu implementieren:
Sortieren Sie für ein ungeordnetes Array es mit einer geordneten verlinkten Liste, und das zeitliche Vergleichsniveau ist o (n^2)
Die Kopienzeitstufe ist o (2*n). Da die Anzahl der Kopien gering ist, werden die Daten in der verknüpften Liste zum ersten Mal n -mal verschoben und dann aus der verlinkten Liste in das Array kopiert. In nzeitigen Zeit müssen jedes Mal, wenn ein neuer Link eingefügt wird, nicht die sich bewegenden Daten kopieren. Nur ein oder zwei Links müssen die Linkdomäne ändern.
Import Java.util.Arrays; import Java.util.random; / *** Einfügen von Arrays in eine bestellte verlinkte Liste* @Author Stone*/ Public Class LinkedListInsertSort <T erweitert vergleichbar <T >> {private Link <T> zuerst; // First Node public linkedListInsertSort () {} public boolean isempty () {return first == null; } public void sortList (t [] ary) {if (ary == null) {return; } // Array -Elemente in die verknüpfte Liste einfügen und in einer geordneten verlinkten Liste für (t data: ary) {insert (data) sortieren; } //} public void Insert (t data) {// In den Kettenheader einfügen, sortieren Sie von klein nach großes nach groß <t> newlink = new Link <T> (Daten); Link <T> current = zuerst, vorher, vorab = null; while (current! current = current.Next; } if (vorher == null) {first = newLink; } else {vorher.Next = newLink; } newlink.next = aktuell; } public link <T> deleteFirst () {// Den Kettenheader -Link <T> temp = First; First = First.Next; // Ändern Sie den ersten Knoten, um die Temperatur zurückzugeben. } public link <T> find (t t) {link <T> find = First; while (find! = null) {if (! find.data.equals (t)) {find = find.Next; } else {break; }} return find; } public link <T> delete (t t) {if (isEmpty ()) {return null; } else {if (first.data.equals (t)) {link <T> temp = First; First = First.Next; // Ändern Sie den ersten Knoten in den nächsten Knoten zurück. }} Link <t> p = zuerst; Link <T> q = zuerst; while (! P.Data.equals (t)) {if (p.Next == null) {// Geben Sie an, dass die Rückkehr NULL am Ende der Kette nicht gefunden wurde; } else {q = p; p = P.Next; }} Q.Next = P.Next; Rückkehr p; } public void displayList () {// Travel System.out.println ("List (First-> Last):"); Link <T> current = First; while (current! = null) {current.displaylink (); current = current.Next; }} public void displayListeverse () {// Inverse Traversal Link <T> p = zuerst, q = first.Next, t; Während (q! = null) {// Zeiger umgekehrt ist, ist die durchquerte Datenreihenfolge rückwärts t = q.Next; // no3 if (p == zuerst) {// Wenn es der ursprüngliche Header ist, sollte der .Next des Headers leer sein. P.Next = null; } Q.Next = p; // no3 -> no1 Zeiger reverse p = q; // Start ist umgekehrt q = t; // No3 starten} // In der obigen Schleife oben, zuerst.Next ist leer, und wenn Q null ist und die Schleife nicht ausführt, ist P das ursprüngliche Datenelement. Nach dem Invertieren wird P an erster zugeordnet = P; DisplayList (); } Klasse Link <T> {// Link Point t Data; // Datenfeldverbindung <T> Weiter; // nachfolgende Zeiger, Knotenketten -Domänenverbindung (t data) {this.data = data; } void displayLink () {System.out.println ("Die Daten ist" + data.toString ()); }} public static void main (String [] args) {linkedListinsertSort <GanzEger> list = new LinkedListInserTSort <Grapier> (); Random random = new random (); int len = 5; Integer [] ary = New Integer [Len]; für (int i = 0; i <len; i ++) {ary [i] = random.nextint (1000); } System.out.println ("--------------"); System.out.println (Arrays.toString (Ary)); System.out.println ("---------------------------------------------------); LIST.SORTLIST (ARY); LIST.DisplayList ();}}
Drucken
--- Vor dem Sortieren ---- [595, 725, 310, 702, 444] --- Nach der Sortierung der verknüpften Liste ---- Liste (zuerst-> zuletzt): Die Daten sind 310 Die Daten sind 444 Die Daten sind 595 Die Daten sind 702 Die Daten sind 725
Single Linked List Inversion:
öffentliche Klasse Singlelinkedlistreverse {public static void main (String [] args) {node head = neuer Knoten (0); Knoten temp = null; Node cur = null; für (int i = 1; i <= 10; i ++) {temp = neuer Knoten (i); if (i == 1) {head.setNext (temp); } else {cur.setNext (temp); } cur = temp; } // 10.Next = null; Knoten H = Kopf; while (h! = null) {System.out.print (h.getData () + "/t"); H = H.GetNext (); } System.out.println (); // invert 1 // H = node.reverse1 (Kopf); // while (h! = null) {// system.out.print (h.getData () + "/t"); // h = h.getNext (); //} // invert 2 h = node.reverse1 (Kopf); while (h! = null) {System.out.print (h.getData () + "/t"); H = H.GetNext (); }}}/** Jeder Knoten einer einzelnen verknüpften Liste enthält Attribute, die auf den nächsten Knoten*/Klasse -Knoten {Objektdaten; // Data -Objektknoten als nächstes zeigen; // Nächster Knotenknoten (Objekt d) {this.data = d; } Node (Objekt D, Knoten n) {this.data = d; this.Next = n; } öffentliches Objekt getData () {returndaten; } public void setData (Objektdaten) {this.data = data; } public node getNext () {return als nächstes; } public void setNext (Knoten als nächstes) {this.Next = next; } // Methode 1 Kopf wird statischer Knoten reverse1 zurückgesetzt (Knotenkopf) {Knoten p = null; // der neue Kopf nach Inversionknoten q = Kopf; // Rotationsergebnis: 012,123,234, ...... 10 null null while (head.next! = Null) {p = head.Next; // der erste wird durch den zweiten ersetzt, und dann repräsentiert P den nächsten Kopf.Next = P.Next; // der zweite wird durch den dritten ersetzt, und der nächste, der bereits die erste Position erreicht hat, wird der erste, und der erste wird der erste. // der neue wird durch den ersten ersetzt} return p; } // Methode 2 Kopf wird statischer Knoten Reverse2 (Knotenkopf) nicht zurückgesetzt. {// Zeigen Sie den Zeiger des Zwischenknotens auf den vorherigen Knoten, Sie können weiterhin die verknüpfte Liste Backwards Node p1 = head, p2 = head.next, p3; // Ergebnis vorne, mittlerer und hinten/Rotation: 012, 123, 234, 345, 456 .... 9 10 NULL while (p2! = Null) {p3 = p2.Next; p2.Next = p1; // rückwärts zeigen und nach vorne p1 = p2; // 2, 3 bewegt sich vorwärts p2 = p3; } head.next = null; // Kopf hat sich nicht geändert. Wenn die Ausgabe 0 erreicht, fordern Sie 0 an. }}