Eine verknüpfte Liste ist eine komplexe Datenstruktur. Die Beziehung zwischen den Daten ermöglicht eine verknüpfte Liste, die in drei Typen unterteilt ist: einzelne verknüpfte Liste, kreisförmige verknüpfte Liste und bidirektionale verknüpfte Liste . Das Folgende wird nacheinander eingeführt. Verbindete Listen sind die grundlegenden und wichtigen Wissenspunkte in der Datenstruktur. Hier sprechen wir über die Implementierung verknüpfter Listen in Java.
Java-verknüpfte Listenvorgänge: Einzelverbundene Liste und doppelte Listliste
Ein paar Punkte sprechen hauptsächlich über:
1. Einführung in die verknüpfte Liste
2. Prinzipien und Notwendigkeiten für die Umsetzung verknüpfter Listen
1. Ein-Strang-Beispiel
4. Doppelklotze Beispiel
1. Einführung in die verknüpfte Liste
Verbindete Listen sind eine relativ häufige Datenstruktur. Obwohl verknüpfte Listen komplizierter für den Speicher sind, sind sie bei Abfragen bequemer. Sie werden in mehreren Computersprachen entsprechend verwendet. Es gibt viele Kategorien verknüpfter Listen. Artikel werden auf einzelne Listen und doppelte Listen analysiert. Die Daten in der verknüpften Liste sind wie durch eine Kette miteinander verbunden, sodass ein einfacher Zugriff auf Daten.
2. Prinzipien und Notwendigkeiten für die Umsetzung verknüpfter Listen
Hier werden nur einzelne Listen und doppelt verknüpfte Listen analysiert. Der Implementierungsprozess von verknüpften Listen ist etwas kompliziert, bringt jedoch viele Vorteile. Mit der Ankunft von Online -Einkaufsmöglichkeiten packen Händler die Ware in der Regel in eine Box und schreiben die Adressinformationen auf die Box. Die Express Company kann den Käufer durch die Informationen über die Schachtel finden und die Waren intakt ankommen. Ohne den Schutz der Box kann das Produkt auf dem Weg beschädigt werden. Die verknüpfte Liste entspricht dem Feld mit geschriebenen Adresse, die nicht nur Produktinformationen schützt, sondern auch Logistikinformationen schreibt. In der verknüpften Liste befindet sich ein Kopfknoten, ähnlich der "Lokomotive". Solange der entsprechende Kopfknoten gefunden wird, können Sie auf der verknüpften Liste arbeiten. In dieser Analyse fungiert der Kopfknoten nur als Datenheader und speichert keine gültigen Daten.
Das Implementierungsprinzip der einzelnen verknüpften Liste ist in der Abbildung dargestellt:
Doppelverbundenes Listen-Implementierungsprinzip:
1. Ein-Strang-Beispiel
ICommoperate <T> Schnittstellenbetriebsklasse:
Paket linkListTest; importieren java.util.map; öffentliche Schnittstelle iCommoperate <T> {public boolean InsertNode (t Knoten); public boolean InsertPosnode (int pos, tknoten); Public Boolean DeleteNode (int pos, map <String, Objekt> Karte); public void printlink ();}Single Linked List Node:
Paket linkListTest; // Einzelverbindungstabelle Knoten öffentliche Klasse Snode {private String-Daten; private Snode NextNode; public snode () {} public snode (String -Daten) {this.data = data; this.NextNode = new Snode (); } public String getData () {returndaten; } public void setData (String -Daten) {this.data = data; } public snode getNextNode () {return NextNode; } public void setNextNode (Snode NextNode) {this.NextNode = NextNode; } @Override public String toString () {return "snode [data =" + data + "]"; }}Einzelverbindungs -Betriebsklasse:
Paket linkListTest; importieren java.util.hashMap; import Java.util.map; öffentliche Klasse SinglelinkList implementiert iCommoperate <Snode> {private snode head = new Snode ("head"); // Public Header Zeiger, unverändert nach Deklaration private int size = 0; public int getSize () {return this.size; } / * * Fügen Sie die verknüpfte Liste ein, fügen Sie sie jedes Mal zum Ende ein * / @Override public boolean InsertNode (Snode -Knoten) {boolean flag = false; Snode current = this.head; if (this.size == 0) {// leere verlinkte Liste this.head.setNextNode (Knoten); node.setNextNode (null); } else {// Knoten in der verknüpften Liste while (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (Knoten); node.setNextNode (null); } this.size ++; Flag = wahr; Rückflagge; } / * * Fügen Sie die angegebene Position von POS in der verlinkten Liste ab 1 ein und POS ist größer als die Größe und fügen Sie das Ende der verknüpften Liste ein * * / @Override public boolean InsertPosNode (int pos, snode node) {boolean flag = true; Snode current = this.head.getNextNode (); if (this.size == 0) {// Die leere verlinkte Liste This.head.SetNextNode (Knoten); node.setNextNode (null); this.size ++; } else if (this.size <pos) {// Die POS -Position ist größer als die Länge der verknüpften Liste, InsertNode (Knoten); } else if (pos> 0 && pos <= this.size) {// Knoten in der verknüpften Liste // 1. Suchen Sie den Knoten und den vorderen Knoten, der int int fand = 0 eingefügt werden soll. Snode prenode = this.head; // Frontknoten Snode currentNode = Strom; // aktueller Knoten while (find <pos-1 && currentNode.getNextNode ()! = Null) {prenode = current; // Frontknoten bewegt rückwärts currentNode = currentNode.getNextNode (); // Der aktuelle Knoten bewegt rückwärts ++; } // system.out.println (prenode); // system.out.println (currentNode); // 2.. node.setNextNode (currentNode); this.size ++; System.out.println ("Knoten wurde in die verlinkte Liste eingefügt"); } else {System.out.println ("Positionsinformationsfehler"); Flag = Falsch; } Rückkehrflag; } / * * Geben Sie den Knoten -POS der verknüpften Liste an und löschen Sie den entsprechenden Knoten. Methode: Finden Sie die vorderen und hinteren Knoten zum Löschen und Löschen. Ausgehend von 1 * */ @Override public boolean deleteNode (int pos) {boolean flag = false; Snode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Positionsinformationsfehler oder keine Informationen in der verlinkten Liste"); } else {// 1. Finden Sie die vorderen und hinteren Knoten, um int find = 0 zu löschen; Snode prenode = this.head; // Frontknoten snode snode neutnode = cururrow.getNextNode (); // Back-Knoten while (finde <pos-1 && nextNode.getNextNode ()! = Null) {prenode = current; // Der vordere Knoten wird zurückgezogen von nächstenNode = NextNode.getNextNode (); // Der Backknoten wird zurückgezogen Find ++; } // system.out.println (prenode); // system.out.println (NextNode); // 2. Löschen Sie den Knoten prenode.setNextNode (NextNode); System.gc (); this.size--; Flag = wahr; } Rückkehrflag; } / * * Geben Sie den Knoten POS der verknüpften Liste an und ändern Sie den entsprechenden Knoten. Ab 1 * */ @Override public boolean updateNode (int pos, map <string, Objekt> map) {boolean flag = false; Snode node = getNode (pos, map); // den Knoten an der entsprechenden Position abrufen if (Knoten! = Null) {String data = (String) map.get ("data"); node.setData (Daten); Flag = wahr; } Rückkehrflag; } / * * Den Knoten POS der angegebenen verknüpften Liste ab 1 * * / @Override public snode getNode (int pos, map <String, Objekt> Karte) {Snode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Positionsinformationen sind falsch oder die verlinkte Liste existiert nicht"); null zurückkehren; } int find = 0; while (finde <pos-1 && current! = null) {current = current.getNextNode (); Finden Sie ++; } Return Current; } / * * Verlinkte Liste drucken * * * / @Override public void printlink () {int länge = this.size; if (Länge == 0) {System.out.println ("Die verlinkte Liste ist leer!"); zurückkehren ; } Snode current = this.head.getNextNode (); int find = 0; System.out.println ("Gesamtzahl der Knoten:" + Länge + ""); while (current! current = current.getNextNode (); }} public static void main (String [] args) {SinglelinkList Sll = new SinglelinkList (); Snode node1 = new snode ("node1"); Snode node2 = new snode ("node2"); Snode node3 = new snode ("node3"); Snode node4 = new snode ("node4"); Snode node5 = new snode ("node5"); Snode node6 = new Snode ("angegebene Position einfügen"); Sll.InsertPosNode (Sll.getSize ()+1, Node1); Sll.InsertPosNode (Sll.getSize ()+1, Node2); sll.insertposnode (sll.getSize ()+1, node3); sll.insertposnode (sll.getSize ()+1, node4); Sll.InsertPosNode (Sll.getSize ()+1, Node5); // sll.insertnode (node1); // sll.insertnode (node2); // sll.insertnode (node3); // sll.insertnode (node4); // sll.insertnode (node5); System.out.println("******************************"); sll.printlink (); System.out.println("*********************************"); int pos = 2; System.out.println ("Get die Position" Position+"der verknüpften Liste der verknüpften Liste:"+sll.getNode (pos, null)); System.out.println("****************************** Insert nodes to the specified position of the linked list**********************************"); int pos1 = 2; System.out.println ("Daten in"+pos1+"Knoten:"); Sll.insertposnode (pos1, node6); sll.printlink (); System.out.println("************************************Delete the specified location node of the linked list*************************************"); int pos2 = 2; System.out.println ("löschen"+pos2+"Knoten:"); Sll.DeletEnode (POS2); sll.printlink (); System.out.println("***************************************Modify the specified location node of the linked list*************************************"); int pos3 = 2; System.out.println ("Ändern Sie"+pos3+"Knoten:"); Karte <String, Objekt> map = new HashMap <> (); map.put ("Daten", "Dies ist ein Test"); Sll.UpDatenode (POS3, MAP); sll.printlink (); }}4. Doppelklotze Beispiel
ICommoperate <T> Schnittstellenbetriebsklasse:
Paket linkListTest; importieren java.util.map; öffentliche Schnittstelle iCommoperate <T> {public boolean InsertNode (t Knoten); public boolean InsertPosnode (int pos, tknoten); Public Boolean DeleteNode (int pos, map <String, Objekt> Karte); public void printlink ();}Doppelverbundener Listenknoten:
Paket linkListTest; // Dual-ContiGuous-Tabellenknoten öffentliche Klasse Dnode {private dnode priornode; private String -Daten; private dnode amtNode; public dnode () {} public dnode (String -Daten) {this.Priornode = new Dnode (); this.data = Daten; this.NextNode = new Dnode (); } public dnode getPriornode () {return priornode; } public void setPriornode (dnode priornode) {this.priornode = priornode; } public String getData () {returndaten; } public void setData (String -Daten) {this.data = data; } public dnode getNextNode () {return NextNode; } public void setNextNode (dnode NextNode) {this.NextNode = NextNode; } @Override public String toString () {return "dnode [data =" + data + "]"; }}Doppelverbundene Listen-Implementierungsklasse:
Paket linkListTest; importieren java.util.hashMap; import Java.util.map; Public Class DoubelinkList implementiert iCommoperate <Dnode> {private dnode head = new Dnode ("head"); private int size = 0; public int getSize () {return this.size; } / * * Fügen Sie die verknüpfte Liste ein, fügen Sie sie jedes Mal am Ende ein * * / @Override public boolean InsertNode (DNODE -Knoten) {boolean flag = false; Dnode current = this.head; if (this.size == 0) {// leere verlinkte Liste this.head.setNextNode (Knoten); node.setPriornode (this.head); node.setNextNode (null); } else {// Knoten in der verknüpften Liste while (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (Knoten); node.setNextNode (null); node.setPriornode (Strom); } this.size ++; Flag = wahr; Rückflagge; } / * * Fügen Sie die angegebene Position von POS in der verlinkten Liste ab 1 ein und POS ist größer als die Größe. Fügen Sie das Ende der verknüpften Liste ein. Dnode current = this.head.getNextNode (); if (this.size == 0) {// Die verknüpfte Liste ist leer this.head.setNextNode (Knoten); node.setNextNode (null); node.setPriornode (this.head); this.size ++; } else if (pos> this.size) {// pos Position ist größer als die Länge der verknüpften Liste, fügen Sie den Endnode (Knoten) ein; } else if (pos> 0 && pos <= this.size) {// Knoten in der verknüpften Liste // 1. Suchen Sie den zu eingefügten POS -Knoten, fügen Sie den POS -Knoten aktuellen Standort in int find = 0 ein; while (find <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); Finden Sie ++; } // 2. Node if (current.getNextNode () == null) {// Tail Node node.setPriornode (current); node.setNextNode (null); Current.SetNextNode (Knoten); } else if (current.getNextNode ()! node.setNextNode (aktuell); current.getPriornode (). setNextNode (Knoten); current.setPriornode (Knoten); } this.size ++; } else {System.out.println ("Positionsinformationsfehler"); Flag = Falsch; } Rückkehrflag; } / * * Geben Sie den Knoten POS der verknüpften Liste an und löschen Sie den entsprechenden Knoten ab 1 * * / @Override public boolean deleteNode (int pos) {boolean flag = false; Dnode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Positionsinformationen sind falsch oder die verlinkte Liste existiert nicht"); } else {// 1. Finden Sie den Ort, an dem der POS -Knoten gelöscht werden soll. Int find = 0; while (find <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); Finden Sie ++; } // 2. Knoten löschen if (current.getNextNode () == null) {// Der Tail -Knoten current.getPriornode (). SetNextNode (null); } else if (current.getNextNode ()! current.getNextNode (). setPriornode (current.getPriornode ()); } System.gc (); this.size--; Flag = wahr; } Rückkehrflag; } / * * Geben Sie den Knoten POS der verknüpften Liste an und ändern Sie den entsprechenden Knoten. Starten Sie bei 1 * */ @Override public boolean updateNode (int pos, map <String, Objekt> Karte) {boolean flag = false; Dnode node = getNode (pos, map); if (node! = null) {string data = (string) map.get ("data"); node.setData (Daten); Flag = wahr; } Rückkehrflag; } / * * Den Knoten POS der angegebenen verknüpften Liste finden, starten Sie bei 1 * * / @Override public dnode getNode (int pos, map <String, Objekt> map) {dnode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Positionsinformationen sind falsch oder die verlinkte Liste existiert nicht"); null zurückkehren; } int find = 0; while (finde <pos-1 && current! = null) {current = current.getNextNode (); Finden Sie ++; } Return Current; } / * * Verlinkte Liste drucken * * * / @Override public void printlink () {int länge = this.size; if (Länge == 0) {System.out.println ("Die verlinkte Liste ist leer!"); zurückkehren ; } Dnode current = this.head.getNextNode (); int find = 0; System.out.println ("Gesamtzahl der Knoten:" + Länge + ""); while (current! current = current.getNextNode (); }} public static void main (String [] args) {DoubelInKList dll = new DoublelinkList (); Dnode node1 = new Dnode ("node1"); Dnode node2 = new Dnode ("node2"); Dnode node3 = new Dnode ("node3"); Dnode node4 = new Dnode ("node4"); Dnode node5 = new Dnode ("node5"); Dnode node6 = neuer dnode ("angegebene Position einfügen"); dll.insertposnode (10, node1); dll.insertposnode (10, node2); dll.insertposnode (10, node3); dll.insertposnode (10, node4); dll.insertposnode (10, node5); // dll.insertNode (node1); // dll.insertNode (node2); // dll.insertNode (node3); // dll.insertNode (node4); // dll.insertNode (node5); System.out.println("******************************"); dll.printlink (); System.out.println("************************************"); int pos = 2; System.out.println ("Get die"+pos+"Positionsdaten der verknüpften Liste:"+dll.getNode (pos, null)); System.out.println("****************************** Insert nodes to the specified position of the linked list**********************************"); int pos1 = 2; System.out.println ("Daten in die"+pos1+"-Knoten einfügen:"); dll.insertposnode (pos1, node6); dll.printlink (); System.out.println ("****************************************************************************************************** int pos2 = 7; System.out.println ("löschen"+pos2+"Knoten:"); Dll.DeletEnode (POS2); dll.printlink (); System.out.println("************************************Modify the nodes specified in the linked list*************************************"); int pos3 = 2; System.out.println ("Ändern Sie"+pos3+"Knoten:"); Karte <String, Objekt> map = new HashMap <> (); map.put ("Daten", "Dies ist ein Test"); dll.updatenode (pos3, map); dll.printlink (); }}Danke fürs Lesen, ich hoffe, es kann Ihnen helfen. Vielen Dank für Ihre Unterstützung für diese Seite!