Introduction à la méthode d'implémentation de liste chaînée dans la structure de données JavaScript (image et texte)

La liste chaînée est une structure de données commune. C'est une structure qui alloue dynamiquement le stockage. Cet article présente principalement l'implémentation de listes chaînées dans la structure de données JavaScript, qui a une bonne valeur de référence. Jetons-y un coup d'œil avec l'éditeur ci-dessous

L'affiche précédente traitait respectivement de l'implémentation des piles et des files d'attente de structures de données. Les structures de données utilisées à cette époque étaient toutes implémentées à l'aide de tableaux, mais parfois les tableaux ne sont pas les meilleurs. optimale. Structure de données optimale, par exemple, lors de l'ajout et de la suppression d'éléments dans un tableau, d'autres éléments doivent être déplacés et l'utilisation de la méthode spit() en JavaScript ne nécessite pas d'accès à d'autres éléments. Si vous trouvez que l'utilisation de tableaux est lente, envisagez d'utiliser des listes chaînées.

Le concept de liste chaînée

La liste chaînée est une structure de données courante. C'est une structure qui alloue dynamiquement le stockage. La liste chaînée possède une variable « pointeur de tête », représentée par head, qui stocke une adresse pointant vers un élément. Chaque nœud utilise la référence d'un objet pour pointer vers son successeur. Une référence pointant vers un autre nœud est appelée une chaîne.

Les éléments du tableau sont référencés par des indices (positions), tandis que les éléments de la liste chaînée sont référencés par leurs relations. Par conséquent, l'efficacité d'insertion de la liste chaînée est très élevée. La figure suivante montre le processus d'insertion du nœud de liste chaînée d :

　

Processus de suppression :

<.>

Liste chaînée basée sur des objets

Nous définissons deux classes, la classe Node et la classe LinkedList sont les données du nœud, et LinkedList enregistre les méthodes pour. exploiter la liste chaînée.

Premier coup d'oeil à la classe Node :

function Node(element){
  this.element = element;
   this.next = null;
 }

l'élément est utilisé pour enregistrer les données sur le nœud, et ensuite est utilisé pour enregistrer le lien pointant vers le nœud.

Classe LinkedList :

function LinkedList(){
     this.head = new Node('head');
     this.find = find;
     this.insert = insert;
     this.remove = remove;
     this.show = show;
}

méthode find(), en commençant par le nœud principal, en recherchant le long des nœuds de la liste chaînée jusqu'à ce qu'un élément égal au contenu de l'élément soit trouvé, puis le nœud est retourné. S'il n'est pas trouvé, retournez vide.

function find(item){
     var currentNode = this.head;//从头结点开始
     while(currentNode.element!=item){
         currentNode = currentNode.next;
     }
     return currentNode;//找到返回结点数据，没找到返回null
}

Méthode d'insertion. Comme le montre la démonstration précédente de l'insertion d'éléments, il existe quatre étapes simples pour mettre en œuvre l'insertion :

1 Créer un nœud

2. Trouver le nœud cible

. 3. Modifier le nœud cible Le point suivant du point pointe vers le lien

4. Attribuer la valeur suivante du nœud cible à la méthode next

function insert(newElement,item){
     var newNode = new Node(newElement);
     var currentNode = this.find(item);
     newNode.next = currentNode.next;
     currentNode.next = newNode;
 }

Remove() du nœud à insérer. Pour supprimer un nœud, vous devez d'abord retrouver le nœud précédent du nœud supprimé. Pour cette raison, nous définissons la méthode frontNode() :

function frontNode(item){
     var currentNode = this.head;
     while(currentNode.next.element!=item&&currentNode.next!=null){
         currentNode = currentNode.next;
     }   
     return currentNode;
}

Réponse simple en trois étapes :

1. Créez un nœud

2. Recherchez le nœud précédent du nœud cible

3 Modifiez le nœud suivant du nœud précédent pour pointer vers le nœud n après le nœud supprimé

Méthode Show() :

function remove(item){
     var frontNode = this.frontNode(item);
     //console.log(frontNode.element);
     frontNode.next = frontNode.next.next;
 }

Programme de test :

function show(){
     var currentNode = this.head,result;
     while(currentNode.next!=null){
         result += currentNode.next.element;//为了不显示head结点
         currentNode = currentNode.next;
     }
}

Sortie :

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

Liste doublement chaînée

Le passage du nœud de tête au nœud de queue de la liste chaînée est très simple, mais parfois, nous devons parcourir de l'arrière vers l'avant. À ce stade, nous pouvons ajouter un

attribut

à l'objet Node, qui stocke le lien vers le nœud prédécesseur. L'affiche utilise le diagramme suivant pour illustrer le principe de fonctionnement d'une liste doublement chaînée.

Nous ajoutons d'abord l'attribut front à la classe Node :

Bien sûr, nous avons également besoin de la méthode insert() correspondante et de delete( ) méthode Effectuer les modifications correspondantes :

function Node(element){
  this.element = element;
  this.next = null;
   this.front = null;
 }

Afficher la liste chaînée dans l'ordre inverse :

function insert(newElement,item){
  var newNode = new Node(newElement);
  var currentNode = this.find(item);
  newNode.next = currentNode.next;
  newNode.front = currentNode;//增加front指向前驱结点
  currentNode.next = newNode;
}
function remove(item){  
  var currentNode = this.find(item);//找到需要删除的节点
  if (currentNode.next != null) {
    currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
    currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
    currentNode.next = null;//并设置前驱与后继的指向为空
    currentNode.front = null;    
  }  
}

Vous devez ajouter une méthode à la liste doublement chaînée pour trouver le dernier nœud. La méthode findLast() trouve le dernier nœud de la liste chaînée, éliminant ainsi le besoin de parcourir la chaîne d'avant en arrière.

Réaliser une sortie dans l'ordre inverse :

function findLast() {//查找链表的最后一个节点
  var currentNode = this.head;
  while (currentNode.next != null) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

Programme de test :

function showReverse() {
  var currentNode = this.head, result = "";
  currentNode = this.findLast(); 
  while(currentNode.front!=null){
    result += currentNode.element + " ";
    currentNode = currentNode.front;
  }
  return result;
}

Sortie :

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list);
list.remove("b");
console.log(list.show());
console.log(list.showReverse());

Liste chaînée circulaire

La liste chaînée circulaire est une autre forme de structure de stockage liée. Sa caractéristique est que le champ de pointeur du dernier nœud de la liste pointe vers le nœud principal et que l'ensemble de la liste chaînée forme un anneau. Les listes chaînées circulaires sont similaires aux listes chaînées unidirectionnelles et les types de nœuds sont les mêmes. La seule différence est que lors de la création d'une liste chaînée circulaire, laissez l'attribut suivant de son nœud principal pointer vers lui-même, c'est-à-dire :

head.next = headCe comportement sera transmis à chaque élément dans les nœuds de la liste chaînée, de sorte que l'attribut suivant de chaque nœud pointe vers le nœud principal de la liste chaînée. L'affiche utilise l'image suivante pour représenter une liste chaînée circulaire :

Modifier la

méthode de construction

 :

function LinkedList(){
  this.head = new Node('head');//初始化
  this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
  this.find = find;
  this.frontNode = frontNode;
  this.insert = insert;
  this.remove = remove;
  this.show = show; 
}

这时需要注意链表的输出方法show()与find()方法，原来的方式在循环链表里会陷入死循环，while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
  var currentNode = this.head;//从头结点开始
  while(currentNode.element!=item&&currentNode.next.element!='head'){
    currentNode = currentNode.next;
  }
  return currentNode;//找到返回结点数据，没找到返回null
}
function show(){
  var currentNode = this.head,result = "";
  while (currentNode.next != null && currentNode.next.element != "head") {   
    result += currentNode.next.element + " ";
    currentNode = currentNode.next;
  }
  return result;
}

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

测试结果：

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!