Liste des liens commandés:
Trier par des valeurs clés. Lors de la suppression de l'en-tête de chaîne, la valeur minimale (/ maximale) est supprimée. Lors de l'insertion, recherchez la position d'insertion.
Lors de l'insertion, vous devez comparer O (n), O (n / 2) moyen, et lorsque vous supprimez les données minimales (/ maximales) à la tête de la chaîne, l'efficacité est O (1),
Si une application nécessite un accès fréquent (insérer / finir / supprimer) aux plus petits éléments de données (/ maximum), les listes liées commandées sont un bon choix. Les files d'attente prioritaires peuvent utiliser des listes liées ordonnées pour implémenter le tri d'insertion des listes liées commandées:
Pour un tableau non ordonné, triez-le avec une liste liée ordonnée, et le niveau de comparaison est O (n ^ 2)
Le niveau de temps de copie est O (2 * n). Étant donné que le nombre de copies est faible, les données de la liste liée sont déplacées n fois pour la première fois, puis copiées à partir de la liste liée au tableau. N fois, chaque fois qu'un nouveau lien est inséré, il n'est pas nécessaire de copier les données mobiles, un ou deux liens doivent modifier le domaine de liaison.
import java.util.arrays; import java.util.random; / ** * Les tableaux d'insertion de tri dans une liste liée ordonnée * @Author Stone * / classe publique LinkedListInsertsort <T étend comparable <T>> {Link privé <T> First; // premier nœud public LinkedListInsertsort () {} public boolean isEmpty () {return first == null; } public void sortlist (t [] ary) {if (ary == null) {return; } // insérer des éléments de tableau dans la liste liée et les trier dans une liste liée ordonnée pour (t data: ary) {insert (data); } //} public void insert (t data) {// insérer à l'en-tête de chaîne, tri de petit à grand lien <T> newLink = new link <t> (data); Link <T> current = premier, précédent = null; while (current! = null && data.compareto (current.data)> 0) {PREBL = Current; courant = current.next; } if (précédent == null) {first = newLink; } else {précédente.next = newLink; } newlink.next = current; } lien public <T> DeleteFirst () {// Supprimer le lien d'en-tête de chaîne <T> temp = premier; premier = first.next; // modifie le premier nœud à la température de retour; } lien public <T> find (t t) {link <t> find = premier; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} return trouver; } lien public <T> delete (t t) {if (isEmpty ()) {return null; } else {if (first.data.equals (t)) {link <t> temp = premier; premier = first.next; // modifie le premier nœud en la température de retour du nœud suivant; }} Lien <T> p = premier; Lien <T> q = premier; tandis que (! } else {q = p; p = p.Next; }} q.next = p.next; Retour p; } public void displayList () {// Travel System.out.println ("List (First -> Last):"); Link <T> current = premier; while (current! = null) {current.displayLink (); courant = current.next; }} public void DisplayListreverSe () {// lien de traversée inverse <T> p = premier, q = first.next, t; tandis que (q! = null) {// pointeur est inversé, l'ordre de données traversé est en arrière t = q.next; // no3 if (p == premier) {// Quand c'est l'en-tête d'origine, le .Next de l'en-tête doit être vide p.Next = null; } q.next = p; // no3 -> no1 pointeur inverse p = q; // Démarrer est inversé Q = T; // no3 start} // Dans la boucle si dans la boucle ci-dessus, d'abord.next est vide, et lorsque q est nul et ne exécute pas la boucle, p est l'élément de données la plupart d'origine. Après l'inversion, P est affecté à First First = P; displayList (); } class link <T> {// lien point t data; // lien de champ de données <T> Suivant; // Pointer ultérieur, lien de domaine de chaîne de nœud (TATA T) {this.data = data; } void displayLink () {System.out.println ("Les données sont" + data.toString ()); }} public static void main (String [] args) {LinkedListInsertSort <Integer> list = new LinkedListInsertSort <Integer> (); Aléatoire aléatoire = nouveau aléatoire (); int len = 5; Entier [] ary = nouveau entier [len]; for (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 ();}}
Imprimer
--- Avant le tri ---- [595, 725, 310, 702, 444] --- Après le tri de la liste liée ---- Liste (premier -> dernier): les données sont 310 Les données sont 444 Les données sont 595, les données sont 702 Les données sont 725.
Inversion de liste liée unique:
classe publique SingleLinkEdListreverSe {public static void main (String [] args) {node head = new node (0); Node temp = null; Nœud cur = null; for (int i = 1; i <= 10; i ++) {temp = new nœud (i); if (i == 1) {head.setNext (temp); } else {cur.setNext (temp); } cur = temp; } // 10.Next = null; Nœud h = tête; while (h! = null) {System.out.print (h.getData () + "/ t"); h = h.getNext (); } System.out.println (); // inverser 1 // h = node.reverse1 (tête); // while (h! = null) {// System.out.print (h.getData () + "/ t"); // h = h.getNext (); //} // invert 2 h = node.reverse1 (tête); while (h! = null) {System.out.print (h.getData () + "/ t"); h = h.getNext (); }}} / * * Chaque nœud d'une seule liste liée contient des attributs pointant vers le nœud suivant * / class nœud {objet data; // nœud d'objet de données suivant; // NODE NODE NEXT (Object D) {this.data = d; } Nœud (objet d, nœud n) {this.data = d; this.next = n; } Objet public getData () {return data; } public void setData (objet Data) {this.data = data; } Node public getNext () {return net; } public void setNext (node suivant) {this.next = next; } // Méthode 1 La tête est réinitialisé le nœud statique Reverse1 (tête de nœud) {nœud p = null; // la nouvelle tête après le nœud d'inversion Q = tête; // Résultat de rotation: 012,123,234, ...... 10 null null while (head.next! = Null) {p = head.next; // Le premier est remplacé par le second, puis P représente la tête suivante.Next = P.Next; // Le second est remplacé par le troisième, et le suivant qui a déjà atteint la première position deviendra le premier, et le premier deviendra le premier; // le nouveau est remplacé par le premier} return p; } // La tête de méthode 2 ne réinitialise pas le nœud statique reverse2 (tête de nœud) {// pointer le pointeur du nœud intermédiaire vers le nœud précédent, vous pouvez toujours continuer à traverser la liste liée au nœud P1 = tête, p2 = head.next, p3; // Résultat de rotation avant, moyen et arrière //: 012, 123, 234, 345, 456 .... 9 10 null while (p2! = Null) {p3 = p2.Next; p2.Next = p1; // pointe vers l'arrière et les avantages p1 = p2; // 2, 3 avance P2 = P3; } head.next = null; // la tête n'a pas changé. Lorsque la sortie atteint 0, demandez 0.Next à 1 retour p1; }}