Apprentissage de la structure des données : utiliser JavaScript pour implémenter des opérations de liste chaînée (exemples détaillés)

Cet article vous apporte des connaissances pertinentes sur la façon d'utiliser JavaScript pour implémenter des listes chaînées dans l'apprentissage de la structure de données. J'espère qu'il vous sera utile.

La liste chaînée a les caractéristiques suivantes :

• peut étendre dynamiquement l'espace (en js, il en va de même pour les tableaux, mais dans certains langages, la longueur du tableau est fixe et ne peut pas être ajouté dynamiquement, comme le langage C )

• Besoin d'un nœud principal

• Besoin de connaître l'adresse du nœud suivant

Vous pouvez considérer chaque nœud de la liste chaînée comme un objet. Cet objet a deux attributs, l'un est la valeur du nœud et l'autre est l'adresse du nœud suivant du nœud (s'il s'agit d'une liste doublement chaînée, l'attribut de l'adresse du nœud précédent doit également être ajouté)

implémente l'opération d'ajout de nœuds :

1 au nœud de queue Ajouter un nœud

 //在尾节点处添加节点
        function append(element){
        let node = new node(element);
        let current;
        if(head == null){
            current = node
        }else{
            while(current.next){
                current = current.next;
            }
            current.next = node
        }
            length++;
        }

Analyse du code :

• Définir un nœud en fonction de l'élément entrant, qui est utilisé comme valeur de ce nœud
• Définir une variable pour représenter le nœud actuel
• Déterminez s'il contient un nœud principal, s'il n'y a pas de nœud principal, indiquant qu'il n'y a pas de valeur dans la liste chaînée, et la valeur transmise est utilisée comme nœud principal ; la liste chaînée est parcourue, le dernier nœud est trouvé et son attribut suivant est attribué au nouveau nœud
• La longueur de la liste chaînée + 1

2. Ajoutez un nœud à n'importe quelle position

Analyse  :

Attribuez l'attribut suivant du nœud précédent à cette position à ce nœud, enregistrez son nœud suivant d'origine et attribuez-le à l'attribut suivant du nœud actuel

function insert(position,element){
        let node = new Node(element);
        let current = head;
        let previous;//当前节点的前一个节点，在position处添加节点，就是在previos和current之间添加
        if(position = 0){
          node.next = head;
          head = node;
        }else{
          for(let i = 0;i< position;i++){
            pervious = current;
            current = current.next;
          }

          pervious.next = node;
          node.next = current;
        }
        length++;
        return true;
      }

Analyse du code :

• Vérifiez si la position est hors limites. Sinon, créez un nœud
• Définissez une variable pour représenter le nœud actuel et initialisez-la comme nœud principal, ce qui signifie traverser depuis le nœud principal ; une variable représente le nœud précédent du nœud actuel, sa fonction est de faciliter la recherche. le nœud précédent lors de l'insertion d'un nœud
• pour déterminer s'il faut l'ajouter avant le nœud principal. Si tel est le cas, attribuez le nœud principal à l'attribut suivant du nœud et remplacez le nœud principal par ce nœud, sinon, parcourez l'emplacement. Nœud, insérez le nœud devant le nœud à cette position
• La longueur de la liste chaînée +1

Pour mettre en œuvre l'opération de suppression du nœud

Analyse : L'opération de suppression d'un nœud consiste à supprimer le nœud devant le nœud cible Le pointeur pointe vers le nœud après le nœud cible

1 Supprimer le nœud spécifié

function removed(element){
    
      let node = new Node(element);
      let pervious;
      let nextNode;
      let current = head;

    if(head != null){
      while (current != node){
        pervious = current;
        current = current.next;
        nextNode = current.next;
      }  

      pervious.next = nextNode;
      length--;
      return true;
    }else{
      return false;
    }    
    }

2 Supprimer le nœud à la position spécifiée

function removedAt(position){
        let current = head;
        let pervious;
        let nextNode;
        let i = 0;

        while(i < position){
          pervious = current;
          current = current.next;
          nextNode = current.next;
        }

        pervious.next = nextNode;
        length--;
        return true;
      }

Implémenter l'opération d'interrogation. le nœud

Analyse : l'interrogation de nœuds est similaire à la suppression de nœuds, à la fois par traversée, recherchez le nœud correspondant ou la position correspondante, puis effectuez l'opération

1.Requérez quel nœud est une certaine position

function searchElement(element){
      //输入元素，找到该元素后返回该元素的位置
      if(head != null){
        let node = new Node(element);
        let current;
        let index = 0;
        if(head == node){
          return 0;
        }else{
          current = head;
          while(current != node){
            current = current.next;
            index++;
          }
          return index;
        }
      }else{
        return -1;
      }
    }

2. Requête sur la position d'un certain nœud

function searchPosition(position){
        let i = 0;
        let current = head;
        while(i< position){
          current = current.next;
          i++;
        }
        return current;
    }

Résumé des idées

À propos de la liste chaînée Il existe de nombreuses autres opérations. Les listes chaînées plus complexes incluent des listes doublement chaînées (ajout d'un nœud précédent lors de l'initialisation du nœud) et des listes chaînées circulaires ( le nœud suivant du nœud de queue est le nœud de tête). Ces opérations de liste chaînée peuvent également être implémentées en utilisant js , pas grand chose à dire ici. Pour résumer, le cœur de la liste chaînée est que le nœud dans la liste chaînée peut être considéré comme un objet avec deux valeurs d'attribut, l'une est la valeur du nœud et l'autre est le pointeur. L'ajout et la suppression de la liste chaînée signifient un changement. le pointeur pointant vers la liste chaînée, le point clé est current = current.next

• 【Recommandation connexe :
Tutoriel d'apprentissage javascript
• 】

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!