Comment utiliser des listes chaînées simples et des listes chaînées circulaires en JavaScript

Cet article présente principalement les structures de données JavaScript des listes chaînées simples et des listes chaînées circulaires, et présente en détail comment JavaScript implémente les listes chaînées simples et les listes chaînées circulaires. Ceux qui sont intéressés peuvent en savoir plus sur

<.> série sur la structure des données Avant-propos :

En tant que connaissance de base pour les programmeurs, la structure des données doit être fermement comprise par chacun de nous. Récemment, j'ai également commencé une deuxième étude sur les structures de données pour compenser les fosses que j'avais creusées à l'époque. . . . . . Quand j'étais en classe, je suivais simplement les cours et je n'implémentais moi-même aucune structure de données, encore moins d'utiliser des structures de données pour résoudre des problèmes. Il est maintenant temps de combler le trou et de lutter. Je voudrais rappeler aux enfants qui voient mon blog que si vous êtes encore à l'école, ne méprisez jamais l'étude d'un cours de base. Le trou creusé à ce moment-là devra être comblé. avec le double de l'effort. Soit cela affectera directement la capacité d'une personne, etc. . . . . . Ne vous creusez pas de trou

Entrons dans le vif du sujet concernant la connaissance de la structure des données des listes chaînées, voici une brève introduction :

Les listes chaînées sont non linéaires et non linéaires. données continues dans des unités de stockage physiques (qui sont linéaires dans la logique des données), chacun de ses nœuds se compose de deux champs : le champ de données et le champ de pointeur. Les données réelles sont stockées dans le champ de données et le champ de pointeur stocke les informations de pointeur, pointant vers l'élément suivant ou l'élément précédent dans la liste chaînée. C'est précisément à cause de l'existence de pointeurs que le stockage des listes chaînées est discontinu en unités physiques.

Les avantages et les inconvénients des listes chaînées sont tout aussi évidents. Par rapport aux listes linéaires, les listes chaînées sont plus efficaces pour ajouter et supprimer des nœuds car elles n'ont besoin que de modifier les informations du pointeur pour terminer l'opération, contrairement aux listes linéaires (tableaux) qui nécessitent le déplacement d'éléments. De même, la longueur d'une liste chaînée est théoriquement infinie (dans la limite de la capacité de la mémoire) et la longueur peut être modifiée dynamiquement, ce qui présente de grands avantages par rapport aux listes linéaires. En conséquence, étant donné que les tables linéaires ne peuvent pas accéder de manière aléatoire aux nœuds et ne sont accessibles que via des requêtes de parcours de pointeur le long de la liste chaînée, l'efficacité de l'accès aux éléments de données est relativement faible.

Ce qui suit est la partie JS

Les méthodes communes et les descriptions qui y sont encapsulées :

方法	描述
append(element)	向链表尾部添加结点element
insert(position,element)	向位置position处插入结点element
removeAt(position)	按照索引值position删除结点
remove(element)	搜索并删除给定结点element
remove()	删除链表中最后一个结点
indexOf(element)	查找并返回给定结点element的索引值
isEmpty()	判断链表是否为空
size()	获取链表长度
toString()	转换为字符串输出
getHead()	获取头结点
getTail()	获取尾结点

Les descriptions d'algorithme de chaque méthode commune ne seront pas écrites ici, je Je crois que tout le monde peut facilement le lire et le comprendre, après tout, ce sont des connaissances très basiques.

Liste chaînée simple :

function LinkedList(){ 
 /*节点定义*/ 
 var Node = function(element){ 
  this.element = element; //存放节点内容 
  this.next = null; //指针 
 } 
 
 var length = 0, //存放链表长度 
  head = null; //头指针 
 
 this.append = function(element){ 
  var node = new Node(element), 
   current; //操作所用指针 
 
  if (!head){ 
   head = node; 
  }else { 
   current = head; 
 
   while(current.next){ 
    current = current.next; 
   } 
 
   current.next = node; 
  } 
 
  length++; 
  return true; 
 }; 
 
 this.insert = function(position, element){ 
  if (position >= 0 && position <= length) { 
   var node = new Node(element), 
    current = head, 
    previous, 
    index = 0; 
 
   if(position === 0){ 
    node.next = current; 
    head = node; 
   }else{ 
    while(index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
    node.next = current; 
    previous.next = node; 
   } 
 
   length++; 
   return true; 
  }else{ 
   return false; 
  } 
  }; 
 
 this.removeAt = function(position){ 
  if(position > -1 && position < length){ 
   var current = head, 
    previous, 
    index = 0; 
 
   if (position === 0) { 
 
    head = current.next; 
 
   }else{ 
 
    while (index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
 
    previous.next = current.next; 
   }; 
 
   length--; 
   return current.element; 
  }else{ 
   return null; 
  } 
 }; 
 
 this.remove = function(element){ 
  var current = head, 
   previous; 
 
  if(element === current.element){ 
   head = current.next; 
   length--; 
   return true; 
  } 
  previous = current; 
  current = current.next; 
 
  while(current){ 
   if(element === current.element){ 
    previous.next = current.next; 
    length--; 
    return true; 
   }else{ 
    previous = current; 
    current = current.next; 
   } 
  } 
  return false; 
 }; 
 
 this.remove = function(){ 
  if(length < 1){ 
   return false; 
  } 
 
  var current = head, 
  previous; 
 
  if(length == 1){ 
   head = null; 
   length--; 
   return current.element; 
  } 
 
  
  while(current.next !== null){ 
   previous = current; 
   current = current.next; 
  } 
 
  previous.next = null; 
  length--; 
  return current.element; 
 }; 
 
 this.indexOf = function(element){ 
  var current = head, 
   index = 0; 
 
  while(current){ 
   if(element === current.element){ 
    return index; 
   } 
   index++; 
   current = current.next; 
  } 
 
  return false; 
 }; 
 
 this.isEmpty = function(){ 
  return length === 0; 
 }; 
 
 this.size = function(){ 
  return length; 
 }; 
 
 this.toString = function(){ 
  var current = head, 
   string = &#39;&#39;; 
 
  while(current){ 
   string += current.element; 
   current = current.next; 
  } 
  return string; 
 };  
 
 this.getHead = function(){ 
  return head; 
 } 
  
}

Liste chaînée circulaire : sur la base de la liste chaînée unique, pointez le pointeur du nœud de queue vers le nœud de tête pour former une liste chaînée circulaire. À partir de n’importe quel nœud d’une liste chaînée circulaire, la liste chaînée entière peut être parcourue.

function CircularLinkedList(){ 
 var Node = function(element){ 
  this.element = element; 
  this.next = null; 
 } 
 
 var length = 0, 
  head = null; 
 
 this.append = function(element){ 
  var node = new Node(element), 
   current; 
 
  if (!head) { 
   head = node; 
   node.next = head; 
  }else{ 
   current = head; 
 
   while(current.next !== head){ 
    current = current.next; 
   } 
 
   current.next = node; 
   node.next = head; 
  }; 
 
  length++; 
  return true; 
 }; 
 
 this.insert = function(position, element){ 
  if(position > -1 && position < length){ 
   var node = new Node(element), 
    index = 0, 
    current = head, 
    previous; 
 
 
   if (position === 0) { 
 
    node.next = head; 
    head = node; 
 
   }else{ 
 
    while(index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
 
    previous.next = node; 
    node.next = current; 
 
   }; 
 
   length++; 
   return true; 
  }else{ 
   return false; 
  } 
 }; 
 
 this.removeAt = function(position){ 
  if(position > -1 && position < length){ 
   var current = head, 
    previous, 
    index = 0; 
 
   if (position === 0) { 
 
    head = current.next; 
 
   }else{ 
 
    while (index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
 
    previous.next = current.next; 
   }; 
 
   length--; 
   return current.element; 
  }else{ 
   return null; 
  } 
 }; 
 
 this.remove = function (element){ 
  var current = head, 
   previous, 
   indexCheck = 0; 
 
  while(current && indexCheck < length){ 
   if(current.element === element){ 
    if(indexCheck == 0){ 
     head = current.next; 
     length--; 
     return true; 
    }else{ 
     previous.next = current.next; 
     length--; 
     return true; 
    } 
   }else{ 
    previous = current; 
    current = current.next; 
    indexCheck++; 
   } 
  } 
  return false; 
 }; 
 
 this.remove = function(){ 
  if(length === 0){ 
   return false; 
  } 
 
  var current = head, 
   previous, 
   indexCheck = 0; 
 
  if(length === 1){ 
   head = null; 
   length--; 
   return current.element; 
  } 
 
  while(indexCheck++ < length){ 
   previous = current; 
   current = current.next; 
  } 
  previous.next = head; 
  length--; 
  return current.element; 
 }; 
 
 this.indexOf = function(element){ 
  var current = head, 
   index = 0; 
 
  while(current && index < length){ 
   if(current.element === element){ 
    return index; 
   }else{ 
    index++; 
    current = current.next; 
   } 
  } 
  return false; 
 }; 
 
 
 this.isEmpty = function(){ 
  return length === 0; 
 }; 
 
 this.size = function(){ 
  return length; 
 }; 
 
 this.toString = function(){ 
  var current = head, 
   string = &#39;&#39;, 
   indexCheck = 0; 
 
  while(current && indexCheck < length){ 
   string += current.element; 
   current = current.next; 
   indexCheck++; 
  } 
 
  return string; 
 };  
 
}

Utilisation :

Développez la méthode en dehors de la classe :

Ce qui précède c'est que je l'ai compilé pour tout le monde, j'espère qu'il sera utile à tout le monde à l'avenir.

Articles associés :

Comment implémenter des références circulaires entre les composants dans Vue.js

Il existe des exemples de composants asynchrones dans Vue

Comment résoudre l'erreur maximale de pile d'appels dans nodejs

Comment implémenter une plateforme de gestion de blog dans Vue+SpringBoot

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!