Partage d'exemples de structures de données JavaScript avec liste chaînée unique et liste chaînée circulaire

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. Si vous êtes intéressé, vous pourrez en savoir plus. tout le monde.

Pour en venir au fait, voici une brève introduction à la connaissance de la structure de données des listes chaînées :

Une liste chaînée est une structure de données non linéaire et non continue dans des unités de stockage physiques ( c'est dans la logique des données qu'il est linéaire), chacun de ses nœuds se compose de deux domaines : le domaine des données et le domaine du 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 pense 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 unique :

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 principal, cela forme 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évelopper les méthodes en dehors de la classe :

Recommandations associées :

Exemple de définition d'utilisation d'une liste doublement chaînée dans une structure de données JavaScript

File d'attente prioritaire et file d'attente circulaire dans la structure de données JavaScript

Explication détaillée de la méthode de définition et de représentation de l'arbre de recherche binaire dans la structure de données 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!