Une liste liée est une structure de données complexe. La relation entre les données rend une liste liée divisée en trois types: liste liée unique, liste liée à la circulaire et liste liée bidirectionnelle . Ce qui suit sera introduit un par un. Les listes liées sont les points de connaissance de base et importants de la structure de données. Ici, nous parlerons de la mise en œuvre des listes liées en Java.
Opérations de liste liée à Java: liste unique et liste à double liaison
Quelques points parlent principalement:
1. Introduction à la liste liée
2. Principes et nécessités de mise en œuvre de listes liées
3. Exemple simple brin
4. Exemple à double liaison
1. Introduction à la liste liée
Les listes liées sont une structure de données relativement courante. Bien que les listes liées soient plus compliquées à stocker, elles sont plus pratiques lors de l'interrogation. Ils sont utilisés dans plusieurs langages informatiques en conséquence. Il existe de nombreuses catégories de listes liées. Les articles sont analysés pour les listes à liaison simple et les listes à double liaison. Les données de la liste liée sont comme être connectées ensemble par une chaîne, ce qui permet un accès facile aux données.
2. Principes et nécessités de mise en œuvre de listes liées
Seules les listes liées à listes et les listes à double liaison sont analysées ici. Le processus de mise en œuvre des listes liés est un peu compliqué, mais il apportera de nombreux avantages. Par exemple, avec l'arrivée des achats en ligne, les commerçants emballent généralement les marchandises dans une boîte et écrivent les informations d'adresse sur la boîte. La société express peut trouver l'acheteur via les informations sur la boîte et les marchandises arrivent intactes. Sans la protection de la boîte, le produit peut être endommagé en cours de route. La liste liée est comme la boîte avec les informations d'adresse écrites, qui non seulement protège les informations du produit, mais rédige également des informations sur la logistique. Il y a un nœud de tête dans la liste liée, similaire à la "locomotive". Tant que le nœud de tête correspondant est trouvé, vous pouvez fonctionner sur la liste liée. Dans cette analyse, le nœud de tête n'agit que comme un en-tête de données et n'enregistre pas les données valides.
Le principe de mise en œuvre de la liste liée unique est illustré sur la figure:
Principe de mise en œuvre de la liste à double liaison:
3. Exemple simple brin
Classe d'opération d'interface ICOMOMOPERATE <T>:
package linkListTest; import java.util.map; interface publique iComperate <t> {public boolean insertnode (node t); Boolean insertPosnode public (int, nœud t); Public Boolean Deletenode (int pos, map <string, objet> map); public void printLink ();}Node de liste liée unique:
package linkListTest; // Node de table unique de classe publique SNODE {Données de chaîne privées; SNODE PRIVÉ NextNode; public snode () {} public snode (String data) {this.data = data; this.nextNode = new snode (); } public String getData () {return data; } public void setData (String data) {this.data = data; } public snode getNextNode () {return nextNode; } public void setNextNode (snode nextNode) {this.nextNode = nextNode; } @Override public String toString () {return "snode [data =" + data + "]"; }}Classe d'opération de liaison unique:
package linkListtest; import java.util.hashmap; import java.util.map; public class singleLinkList implémente iComperate <node> {private snode head = new sode ("head"); // Pointeur d'en-tête public, inchangé après déclaration private int size = 0; public int getSize () {return this.Size; } / * * Insérez la liste liée, insérez-la à la fin à chaque fois * / @Override public boolean insertnode (snode node) {booléen flag = false; Courant SNODE = this.head; if (this.Size == 0) {// vide Liste lié this.head.setNextNode (node); node.setNextNode (null); } else {// nœud dans la liste liée while (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (node); node.setNextNode (null); } this.size ++; Flag = true; drapeau de retour; } / * * Insérez la position spécifiée de POS dans la liste liée, à partir de 1, et POS est supérieure à la taille, puis insérez la fin de la liste liée * * / @Override public booléen insertPosnode (int pos, snode node) {boolean flag = true; Snode current = this.head.getNextNode (); if (this.size == 0) {// la liste liée vide this.head.setNextNode (node); node.setNextNode (null); this.size ++; } else if (this.size <pos) {// La position POS est supérieure à la longueur de la liste liée, insertNode (node); } else if (pos> 0 && pos <= this.size) {// nœud dans la liste liée // 1. Recherchez le nœud et le nœud avant à insérer int fin = 0; Snode prenode = this.head; // Node avant snode currentNode = current; // Node de courant while (trouver <pos-1 && currentNode.getNextNode ()! = Null) {prenode = current; // Le nœud avant se déplace vers l'arrière currentNode = currentNode.getNextNode (); // Le nœud de courant se déplace vers l'arrière ++; } // system.out.println (prenode); // system.out.println (currentNode); // 2. INSERT NODE PENODE.SETNEXTNODE (NODE); node.setNextNode (currentNode); this.size ++; System.out.println ("Le nœud a été inséré dans la liste liée"); } else {System.out.println ("Erreur d'information de position"); Flag = false; } drapeau de retour; } / * * Spécifiez le nœud POS de la liste liée et supprimez le nœud correspondant. Méthode: Trouvez les nœuds avant et arrière pour supprimer et supprimer. À partir de 1 * * / @Override public booléen deletenode (int pos) {booléen drapeau = false; Snode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Erreur d'information de position ou aucune information dans la liste liée"); } else {// 1. Trouvez les nœuds avant et arrière pour supprimer int fin = 0; Snode prenode = this.head; // nœud avant snode nextNode = current.getNextNode (); // Node arrière while (finir <pos-1 && nextNode.getNextNode ()! = Null) {prenode = current; // Le nœud avant est déplacé en arrière nextNode = nextNode.getNextNode (); // Le nœud arrière est retiré en arrière Find ++; } // system.out.println (prenode); // system.out.println (nextNode); // 2. Supprimer le nœud prenode.setNextNode (nextNode); System.gc (); this.size--; Flag = true; } drapeau de retour; } / * * Spécifiez le nœud pos de la liste liée et modifiez le nœud correspondant. À partir de 1 * * / @Override public booléen updaTenode (int pos, map <string, objet> map) {booléen flag = false; SNODE NODE = GETNODE (POS, MAP); // Obtenez le nœud à la position correspondante if (nœud! = Null) {String data = (string) map.get ("data"); Node.setData (données); Flag = true; } drapeau de retour; }! if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Les informations de position sont incorrectes ou la liste liée n'existe pas"); retourner null; } int find = 0; while (find <pos-1 && current! = null) {current = current.getNextNode (); trouver ++; } Retour courant; } / * * Imprimer la liste liée * * / @Override public void printLink () {int length = this.size; if (longueur == 0) {System.out.println ("La liste liée est vide!"); retour ; } Snode courant = this.head.getNextNode (); int find = 0; System.out.println ("Nombre total de nœuds:" + longueur + "Ones"); while (current! = null) {System.out.println ("th" + (++ find) + "nœuds:" + courant); current = current.getNextNode (); }} public static void main (string [] args) {singleLinkList sll = new singleLinkList (); Snode node1 = new snode ("node1"); SNODE NODE2 = NOUVEAU SNODE ("NODE2"); SNODE NODE3 = NOUVEAU SNODE ("NODE3"); SNODE NODE4 = NOUVEAU SNODE ("NODE4"); SNODE NODE5 = NOUVEAU SNODE ("NODE5"); SNODE NODE6 = NOUVEAU SNODE ("INSERT Position spécifiée"); 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 ("Obtenez les données de position" + pos + "de la liste liée:" + sll.getNode (pos, null)); System.out.println ("****************************** Insert des nœuds à la position spécifiée de la liste liée **********************************"); int pos1 = 2; System.out.println ("insérer les données dans" + POS1 + "" NODES: "); Sll.InsertPosnode (POS1, Node6); SLL.printLink (); System.out.println (" ************************************ list*************************************"); int pos2 = 2; System.out.println("Delete"+pos2+" nodes: "); sll.deleteNode(pos2); sll.printLink(); System.out.println("***************************************Modify the specified location node of the linked list*************************************"); int pos3 = 2 ; System.out.println("Modify the "+pos3+" nodes: "); Map<String, Object> map = new HashMap<>() ; map.put("data", "this is a test") ; sll.updateNode(pos3, map) ; sll.printLink(); }}4. Exemple à double liaison
Classe d'opération d'interface ICOMOMOPERATE <T>:
package linkListTest; import java.util.map; interface publique iComperate <t> {public boolean insertnode (node t); Boolean insertPosnode public (int, nœud t); Public Boolean Deletenode (int pos, map <string, objet> map); public void printLink ();}Node de liste à double liaison:
package linkListTest; // Node de table à double contigu Public class DNODE {private dnode priornode; données de chaîne privées; DNODE PRIVÉ NextNode; public dnode () {} public dNode (String data) {this.priornode = new dnode (); this.data = data; this.nextNode = new DNode (); } public dnode getPriornode () {return priornode; } public void setPriorNode (dnode priornode) {this.priornode = priornode; } public String getData () {return data; } public void setData (String data) {this.data = data; } public dnode getNextNode () {return nextNode; } public void setNextNode (dnode nextNode) {this.nextNode = nextNode; } @Override public String toString () {return "dnode [data =" + data + "]"; }}Classe d'implémentation à double liaison:
package linkListtest; import java.util.hashmap; import java.util.map; public class DoubleLinkList implémente iComperate <dnode> {private dnode head = new dnode ("head"); private int size = 0; public int getSize () {return this.Size; } / * * Insérez la liste liée, insérez-la à la fin à chaque fois * * / @Override public boolean insertnode (dnode node) {booléen flag = false; Dnode courant = this.head; if (this.Size == 0) {// vide Liste lié this.head.setNextNode (node); node.setpriornode (this.head); node.setNextNode (null); } else {// nœud dans la liste liée while (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (node); node.setNextNode (null); Node.setPriorNode (courant); } this.size ++; Flag = true; drapeau de retour; } / * * Insérez la position spécifiée de POS dans la liste liée, à partir de 1, et POS est supérieur à la taille, insérez la fin de la liste liée * * / @Override public boolean insertPosnode (int pos, dnode node) {boolean flag = true; Dnode current = this.head.getNextNode (); if (this.size == 0) {// La liste liée est vide this.head.setNextNode (node); node.setNextNode (null); node.setpriornode (this.head); this.size ++; } else if (pos> this.size) {// position pos est supérieure à la longueur de la liste liée, insérez le fin insertnode (nœud); } else if (pos> 0 && pos <= this.size) {// nœud dans la liste liée // 1. Trouvez le nœud POS à insérer, insérez l'emplacement de courant de nœud POS int fin = 0; while (find <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); trouver ++; } // 2. Insérer le nœud if (current.getNextNode () == null) {// nœud tail node.setpriornode (courant); node.setNextNode (null); current.setNextNode (nœud); } else if (current.getNextNode ()! = null) {// nœud intermédiaire node.setpriornode (current.getPriornode ()); node.setNextNode (courant); current.getPriorNode (). setNextNode (node); current.setPriornode (nœud); } this.size ++; } else {System.out.println ("Erreur d'information de position"); Flag = false; } drapeau de retour; } / * * Spécifiez le nœud POS de la liste liée, supprimez le nœud correspondant, à partir de 1 * * / @Override public boolean Deletenode (int pos) {boolean drape = false; Dnode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Les informations de position sont incorrectes ou la liste liée n'existe pas"); } else {// 1. Trouvez l'emplacement à supprimer le nœud de point introuvable = 0; while (find <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); trouver ++; } // 2. Delete nœud if (current.getNextNode () == null) {// le nœud de queue courant.getPriorNode (). SetNextNode (null); } else if (current.getNextNode ()! = null) {// Le nœud intermédiaire current.getPriorNode (). setNextNode (current.getNextNode ()); current.getNextNode (). setPriorNode (current.getPriorNode ()); } System.gc (); this.size--; Flag = true; } drapeau de retour; } / * * Spécifiez le nœud pos de la liste liée et modifiez le nœud correspondant. Commencez à 1 * * / @Override public booléen updaTenode (int pos, map <string, objet> map) {booléen flag = false; Dnode node = getNode (pos, map); if (node! = null) {String data = (string) map.get ("data"); Node.setData (données); Flag = true; } drapeau de retour; }! if (pos <= 0 || pos> this.size || current == null) {System.out.println ("Les informations de position sont incorrectes ou la liste liée n'existe pas"); retourner null; } int find = 0; while (find <pos-1 && current! = null) {current = current.getNextNode (); trouver ++; } Retour courant; } / * * Imprimer la liste liée * * / @Override public void printLink () {int length = this.size; if (longueur == 0) {System.out.println ("La liste liée est vide!"); retour ; } Dnode current = this.head.getNextNode (); int find = 0; System.out.println ("Nombre total de nœuds:" + longueur + "Ones"); while (current! = null) {System.out.println ("th" + (++ find) + "nœuds:" + courant); current = current.getNextNode (); }} public static void main (String [] args) {DoubleLinkList 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 = new dnode ("insérer la position spécifiée"); 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 ("Obtenez les données de position" + pos + "de la liste liée:" + dll.getNode (pos, null)); System.out.println ("****************************** Insert des nœuds à la position spécifiée de la liste liée **********************************"); int pos1 = 2; System.out.println ("insérer des données dans les nœuds" + pos1 + ":"); dll.InsertPosnode (POS1, Node6); dll.printLink (); System.out.println ("*********************************** Supprimer les nœuds spécifiés dans la liste liée *************************************"); int pos2 = 7; System.out.println ("Delete" + POS2 + "NODES:"); dll.deletetenode (pos2); dll.printLink (); System.out.println ("************************************ Modifiez les nœuds spécifiés dans la liste liée *************************************"); int pos3 = 2; System.out.println ("Modifier les nœuds" + pos3 + ":"); Map <string, object> map = new Hashmap <> (); map.put ("data", "Ceci est un test"); dll.updatenode (pos3, map); dll.printLink (); }}Merci d'avoir lu, j'espère que cela peut vous aider. Merci pour votre soutien à ce site!