1. Préface
Récemment, lors de l'examen des structures de données et des algorithmes, certains problèmes d'algorithmes utilisent l'idée des piles, et en ce qui concerne les piles, nous devons parler de listes liées. Les tableaux et les listes liées sont à la base des structures de stockage linéaires, et des piles et des files d'attente sont des applications de structures de stockage linéaires ~
Cet article explique principalement les points de connaissance de base des listes à liaison simple et fait une simple introduction. S'il y a une erreur, veuillez le corriger.
2. Revue et connaissances
En parlant de listes liées, mentionnons d'abord le tableau. Les comparer avec des tableaux vous fait très bien comprendre la structure de stockage des listes liées.
2.1 Examiner le tableau
Nous avons appris des tableaux en C et en Java:
Avantages des tableaux:
Inconvénients des tableaux:
2.2 Description de la liste des liens
Après avoir lu le tableau, revenez à notre liste liée:
Les n nœuds sont discrètement alloués et connectés les uns aux autres via des pointeurs. Chaque nœud n'a qu'un seul nœud prédécesseur, chaque nœud n'a qu'un seul nœud ultérieur, le premier nœud n'a pas de nœud prédécesseur et le nœud de queue n'a pas de nœud ultérieur.
Avantages de la liste liée:
Inconvénients des listes liées:
Je vais expliquer les termes liés à la liste liée via l'image ci-dessus:
Pour déterminer une liste liée, nous n'avons besoin que d'un pointeur de tête, et la liste liée entière peut être déduite via le pointeur de tête ~
Il existe plusieurs catégories de listes liées:
1. Table de liaison unidirectionnel
2. Tableau de liaison bidirectionnel
3. Liste des liens de recyclage
Ce que vous devez vous souvenir lors de l'exploitation d'une liste liée est:
Le champ de pointeur dans le nœud pointe vers un nœud!
3. Liste des liens d'implémentation Java
algorithme:
Tout d'abord, nous définissons une classe comme un nœud
Pour la commodité de l'opération, je l'ai directement définie comme publique.
Node de classe publique {// Données de données publics publics; // Domaine du pointeur, pointant vers le nœud public suivant NEUX NODE; Node public () {} public Node (int data) {this.data = data; } Node public (int, nœud NEXT) {this.data = data; this.next = suivant; }} 3.1 Créez une liste liée (ajoutez des nœuds)
Insérer des données dans la liste liée:
/ ** * Ajouter des données à la liste liée * * @param de la valeur des données à ajouter * / public static void addData (int value) {// initialiser le nœud à ajouter newNode = new nœud (valeur); // Node du nœud temporaire Temp = tête; // Trouvez le nœud de queue while (temp.Next! = Null) {temp = temp.Next; } // Le cas où la tête node.next est null a été incluse ~ temp.next = newNode; } 3.2 Traverser la liste liée
Nous avons écrit la méthode d'addition ci-dessus, et maintenant nous allons le traverser pour voir s'il est correct ~~~
Commencez à partir du premier nœud et continuez à rechercher jusqu'à ce qu'il n'y ait pas de données sur le nœud suivant:
/ ** * Traversant la liste liée * * @param tête de tête de tête * / public static void Traverse (Node Head) {// Node temporaire, démarrez à partir du premier nœud nœud temp = head.next; while (temp! = null) {System.out.println ("Suivez le compte officiel java3y:" + temp.data); // Continue avec la prochaine temp = temp.Next; }}résultat:
3.3 Insérer le nœud
/ ** * Insérer le nœud * * @param pointe pointeur du pointeur * @param index position à insérer * @param valeur de valeur à insérer * / public static void insertnode (nœud head, int index, int value) {// tout d'abord, la position de liaison (tête) + 1) illégal."); retour; } // nœud temporaire, commencez à partir du nœud de nœud de début tempor = tête; // cliquez sur la position actuelle de la traversée int currentPos = 0; // Initialisez le nœud à insérer insertnode = nouveau nœud (valeur); while (temp.next! = null) {// L'emplacement du nœud précédent a été trouvé if ((index - 1) == currentpos) {// Temp représente le nœud précédent // pointer le pointeur d'origine du nœud précédent vers le nœud inséré sur insertnode.next = temp.next; // pointer le champ de pointeur du nœud précédent vers le nœud à insérer temp.next = insertNode; retour; } currentpos ++; temp = temp.Next; }} 3.4 Obtenez la durée de la liste liée
Il est très simple d'obtenir la durée de la liste liée. Cela peut être fait en le traversant et en obtenant +1 pour chaque nœud ~
/ ** * Obtenez la longueur de la liste liée * @Param Head Head Pointer * / public static int linkListLength (Node Head) {int Linard = 0; // Node temporaire, commencez à partir du premier nœud nœud temp = head.next; // Trouvez le nœud de queue while (temp! = Null) {longueur ++; temp = temp.Next; } la longueur de retour; } 3.5 Supprimer les nœuds
La suppression d'un nœud dans un certain emplacement est en fait très similaire au nœud d'insertion, et vous devez également trouver le nœud précédent. Modifiez le champ du pointeur du nœud précédent et vous pouvez le supprimer ~
/ ** * Supprimer les nœuds en fonction de l'emplacement * * @param pointer pointeur * @param index l'emplacement à supprimer * / public static void Deletenode (nœud Head, int index) {// Tout d'abord, vous devez déterminer si l'emplacement spécifié est légal, if (index <1 || index> linkListLength (head) + 1) {System.out.println ("Delelet Emplacement est Ilgal."); "); retour; } // nœud temporaire, commencez à partir du nœud de nœud de début tempor = tête; // L'emplacement actuel de la traversée enregistrée est int currentPos = 0; while (temp.next! = null) {// L'emplacement du nœud précédent est trouvé if ((index - 1) == currentpos) {// temp représente le nœud précédent // temp.Next représente le nœud que vous souhaitez supprimer // stockage le nœud que vous souhaitez supprimer le nœud deletenode = temp.next; // Le nœud suivant que vous souhaitez supprimer le nœud est remis au nœud précédent pour contrôler temp.next = deletenode.next; // Java le recyclera, et il ne devrait pas être très logique de le définir sur NULL (je pense personnellement que si ce n'est pas correct, veuillez le souligner ~) Deletenode = null; retour; } currentpos ++; temp = temp.Next; }} 3.6 Triez la liste liée
J'ai déjà parlé de 8 algorithmes de tri [Résumé de huit algorithmes de tri]. Je choisirai un simple tri à bulles cette fois (en fait, je veux écrire un type rapide, mais c'est un peu difficile de l'essayer ...)
/ ** * Triez la liste liée * * @param Head * * / public static void sortLinkList (Node Head) {Node CurrentNode; Node nextNode; pour (currentNode = head.next; currentNode.next! = null; currentNode = currentNode.next) {for (nextNode = head.next; nextNode.Next! = null; nextNode.next.Data) {int temp = nutationnode.data>; NextNode.data = nextNode.next.data; NextNode.next.data = temp; }}}} 3.7 Trouvez le nœud K-Last dans la liste liée
Cet algorithme est assez intéressant: définissez deux pointeurs P1 et P2 pour rendre les nœuds P2 K plus rapidement que P1, et traversez en même temps. Lorsque P2 est vide, P1 est le dernier nœud K -th
/ ** * Trouvez le K -th jusqu'au dernier nœud de la liste liée (définissez deux pointeurs P1 et P2, rendez P2 K plus rapidement que P1, et traversez en arrière en même temps. Lorsque P2 est vide, P1 est le K -th jusqu'à le dernier nœud * * @param tête * @param k k -th LinkListLegment (tête)) Null; p1;}
3.8 Supprimer les données en double sur la liste liée
C'est similaire au tri des bulles, tant qu'il est égal, il peut être supprimé ~
/ ** * Supprimer les données en double sur la liste liée (similaire à la bulle, elle est équivalente à la suppression) * * @Param Head Head Head Node * / public static void DeleteDupleCate (Node Head) {// Node temporaire, (à partir du premier nœud -> Node avec des données réelles) Node Temp = head.next; // NODE NEXT du nœud de courant (premier nœud) nœud nextNode = temp.Next; while (temp.next! = null) {while (nextNode.next! = null) {if (nextNode.next.data == nextnode.data) {// supprimer le nœud suivant (le nœud actuel pointe vers le nœud suivant) nextnode.next = nextNode.next.next; } else {// Continuez avec le prochain NextNode = NextNode.Next; }} // Round suivant de comparaison Temp = temp.Next; }} 3.9 Interroger les nœuds intermédiaires de la liste liée
Cet algorithme est également assez intéressant: un pointeur qui prend 1 procédure à chaque fois, un pointeur qui prend 2 étapes à chaque fois, puis fait un pas, c'est-à-dire le nœud intermédiaire
/ ** * Interrogez le nœud intermédiaire d'une seule liste liée * / Node statique public SearchMid (tête de nœud) {nœud p1 = tête; Nœud p2 = tête; // Faites une étape et une étape deux étapes jusqu'à ce qu'elle soit nul. Le nœud central que vous atteignez (p2! = Null && p2.Next! = Null && p2.next.next! = Null) {p1 = p1.next; p2 = p2.Next.Next; } retour p1; }3.10 Sortie récursive les tables à liaison unique de la queue à la tête
/ ** * Sortir la liste liée unique de la queue à la tête par récursive * * @param nœud de tête de tête * / public static void printListRevervely (nœud head) {if (head! = Null) {printListRevervely (head.next); System.out.println (head.data); }} 3.11 Liste des liens inversés
/ ** * Implémentez l'inversion de la liste liée * * @param nœud Le nœud de tête de la liste liée * / noeud statique publique ReverseLinkList (nœud nœud) {Node Prev; if (node == null || node.next == null) {prev = node; } else {node tmp = reverselinkList (node.next); node.next.next = node; node.next = null; prev = TMP; } return prev; } Référence à la liste des liens inverses depuis: //www.vevb.com/article/136185.htm
4. Enfin
Il n'est pas difficile de comprendre la liste liée elle-même, mais elle peut provoquer des maux de tête lorsqu'ils effectuent des opérations connexes. Head.Next Suivant Suivant .... (Je suis toujours faible dans l'algorithme ... Je n'ai pas assez de cerveaux ...) J'ai écrit cette petite chose après deux jours ...
Vous pouvez tout faire en connaissant simplement son pointeur de tête lors de l'exploitation d'une liste liée.
1. Ajouter des données à la liste liée
2. Traversé la liste liée
3. Insérez les nœuds dans la liste liée à un endroit donné
4. Obtenez la durée de la liste liée
5. Supprimer le nœud à l'emplacement donné
6. Trier la liste liée
7. Trouvez le nœud K-Last dans la liste liée
8. Supprimer les données en double sur la liste liée
9. Interroger les nœuds intermédiaires de la liste liée
10. Sortir récursivement la table unique de la queue à la tête
11. Liste des liens inversés
PS: La mise en œuvre de chacun sera différente, donc certains petits détails changeront inévitablement, et il n'y a pas de moyen fixe de l'écrire, vous pouvez donc réaliser les fonctions correspondantes ~
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.
Références: