Préface
Une liste liée est une structure de données de base commune. Il s'agit d'une table linéaire, mais elle n'est pas stockée séquentiellement en mémoire. Il est stocké sous forme de chaîne. Chaque nœud stocke le "pointeur" du nœud suivant. Les données de Java sont divisées en types de données de référence et types de données de base. Il n'y a pas de concept de pointeurs en Java, mais pour les listes liées, les pointeurs se réfèrent à l'adresse des types de données de référence.
Les listes et les tableaux liés sont deux structures de données linéaires, et leur longueur est fixée pour les tableaux. Puisqu'ils sont continuels en mémoire, ils conviennent plus à la recherche et à la traversée. Les listes liées ne sont pas stockées séquentiellement en mémoire, mais comme elles sont composées de "pointeurs", il est plus pratique de comparer les tableaux lors de l'insertion et de la suppression.
Le code suivant implémente une structure de données simple d'une liste liée décrite dans le langage Java via des classes internes et des méthodes récursives. Jetons un coup d'œil à l'introduction détaillée.
Définition de la structure des données de liste liée
Tout d'abord, jetons un coup d'œil à la définition de la structure de données de la liste liée, le code est le suivant:
classe NodeManager {Root de nœud privé; // Root Node private int currentIndex = 0; // Numéro de série du nœud, chaque opération démarre à partir de 0 public void add (int data) {} public void delnode (int data) {} public void print () {} public boolean findnode (int data) {} public boolean updatenode (int olddata, int newdata) {} // insert insert void insert (int le nœud de classe de méthode {private int data; Node privé Suivant; // Prenez le type actuel en tant que nœud public de propriété (données int) {this.data = data; } public void setData (int data) {this.data = data; } public int getData () {return data; } // Ajouter le nœud public void addNode (int data) {} // supprimer le nœud public void delnode (int data) {} // sorpation de tous les nœuds publics void printnode () {} // finir si le nœud existe public boolean findNode (int data) {} // modify node booolean uptenode (int olddata, intwata)} node public void insertnode (int index, int data) {}}}Pour la définition des listes liées, la classe NodeManager est utilisée pour gérer les opérations de liste liée, tandis que le nœud de classe interne membre est utilisé pour fournir des données de liste liée et une structure de chaîne. Pour les utilisateurs de la classe, les données ne sont pas directement accessibles, donc la classe NodeManager fonctionne et le nœud de classe interne fournit une véritable gestion des données. Par conséquent, la classe de nœuds doit fournir des méthodes de fonctionnement de données réelles, et la classe NodeManager doit également fournir un ensemble de méthodes pour faire fonctionner les listes liées par externe. Par conséquent, la classe NodeManager et la classe de nœuds fournissent apparemment les mêmes méthodes, mais la signification réelle n'est pas la même.
Vérifions la méthode ADD () dans la classe NodeManager et la classe Node. Le code est le suivant:
public void add (int data) {if (root == null) {root = new node (data); } else {root.addnode (data); }} // Ajouter le nœud public void addNode (int data) {if (this.next == null) {this.next = new node (data); } else {this.next.addnode (data); }}La méthode ci-dessus dans le code est la méthode de la classe NodeManager, tandis que la méthode suivante est la méthode de la classe de nœud.
Une variable de membre racine est fournie dans la classe Manager, qui est utilisée pour gérer le nœud de tête de la liste liée. Par conséquent, lors de l'ajout d'un nœud, il déterminera d'abord si la racine est vide. S'il est vide, le nœud sera enregistré directement par la racine. Si la racine n'est pas vide, elle sera ajoutée via la méthode AddNode () dans la classe de nœud. L'idée d'ajouter au point est de trouver le dernier nœud de la liste liée actuelle et d'attribuer le nouvel ajout à la variable membre suivante que le nœud est attribué au dernier nœud.
Ajouter, supprimer, modifier et vérifier la liste liée
La même idée est également donnée à d'autres opérations sur les listes liées. Le code complet pour l'ajout, la suppression, la récupération et la sortie des listes liées sont les suivantes:
classe NodeManager {Root de nœud privé; // Root Node private int currentIndex = 0; // Numéro de série du nœud, chaque opération démarre à partir de 0 public void add (int data) {if (root == null) {root = new node (data); } else {root.addnode (data); }} public void delnode (int data) {if (root == null) return; if (root.getData () == data) {node tmp = root; root = root.next; tmp = null; } else {root.delnode (data); }} public void print () {if (root! = null) {System.out.print (root.getData () + ""); root.printNode (); System.out.println (); }} public boolean findNode (int data) {if (root == null) return false; if (root.getData () == data) {return true; } else {return root.findNode (data); }} public booléen updatenode (int ol oldedata, int newdata) {if (root == null) return false; if (root.getData () == olddata) {root.setData (newData); Retour Vrai; } else {return root.updatenode (olddata, newData); }} // insert public void insert (int index, int data) {if (index <0) return; currentIndex = 0; if (index == currentIndex) {node newNode = new node (data); newnode.next = root; root = newNode; } else {root.insertNode (index, data); }} // Quiconque possède les données, qui fournit le nœud de classe de méthode {private int data; Node privé Suivant; // Prenez le type actuel en tant que nœud public de propriété (données int) {this.data = data; } public void setData (int data) {this.data = data; } public int getData () {return data; } // Ajouter le nœud public void addNode (int data) {if (this.next == null) {this.next = new node (data); } else {this.next.addnode (data); }} // Supprimer le nœud public void delnode (int data) {if (this.next! = Null) {if (this.next.getData () == data) {node tmp = this.next; this.next = this.next.next; tmp = null; } else {this.next.delnode (data); }}} // Sortie de tous les nœuds public void printNode () {if (this.next! = Null) {System.out.print (this.next.getData () + ""); this.next.printNode (); }} // Recherchez si le nœud existe public Boolean FindNode (int data) {if (this.next! = Null) {if (this.next.getData () == data) {return true; } else {return this.next.findNode (data); }} return false; } // Modifiez le nœud public booléen updatenode (int olddata, int newdata) {if (this.next! = Null) {if (this.next.getData () == olddata) {this.next.setData (newdata); Retour Vrai; } else {return this.next.updatenode (olddata, newdata); }} return false; } // insérer le nœud public void insertnode (int index, int data) {currentIndex ++; if (index == currentIndex) {node newNode = new node (data); newnode.next = this.next; this.next = newNode; } else {this.next.insertNode (index, data); }}}}}Ce qui précède est le code complet pour le fonctionnement de base de la liste liée. Ce qui suit est un code d'appel pour les tests, le code est le suivant:
classe publique LinkList {public static void main (String [] args) {nodeManager nm = new NodeManager (); System.out.println ("Adresse de la liste liée (Ajouter 5, 4, 3, 2, 1)"); NM.Add (5); NM.Add (4); NM.Add (3); nm.add (2); nm.add (1); nm.print (); System.out.println ("Supprimer de la liste liée (supprimer 3)"); nm.delnode (3); nm.print (); System.out.println ("Recherche de la liste liée (Recherche 1)"); System.out.println (nm.FindNode (1)); System.out.println ("Liste de liaison (Find 10)"); System.out.println (nm.FindNode (10)); System.out.println ("Liste de mise à jour (mise à jour 1 à 10)"); NM.Updatenode (1, 10); nm.print (); System.out.println ("Insérer la liste (insérer 20 en première position)"); NM.Insert (1, 20); nm.print (); System.out.println ("INSERT LISTE (INSERT 30 À la première position)"); NM.Insert (1, 20); nm.print (); System.out.println ("INSERT LISTE (INSERT 30 À LA POSITION ZERO)"); NM.Insert (0, 30); nm.print (); }}Compiler et exécuter le code, le résultat est le suivant:
J'ai utilisé beaucoup de connaissances sur les structures de données dans la classe de collecte en Java. Lorsque je serai en bon état, j'apprendrai le code source de la classe de collection Java. Je travaillerai dur pour être un programmeur junior!
Résumer
Ce qui précède est l'intégralité du contenu de cet article. J'espère que le contenu de cet article a une certaine valeur de référence pour l'étude ou le travail de chacun. Si vous avez des questions, vous pouvez laisser un message pour communiquer. Merci pour votre soutien à wulin.com.