So verwenden Sie einfach verknüpfte Listen und zirkulär verknüpfte Listen in JavaScript

In diesem Artikel werden hauptsächlich die JavaScript-Datenstrukturen von einfach verknüpften Listen und zirkulär verknüpften Listen vorgestellt und detailliert beschrieben, wie JavaScript einfach verknüpfte Listen und zirkulär verknüpfte Listen implementiert. Interessierte können mehr über

Datenstruktur-Reihe Vorwort:

Als Grundwissen für Programmierer muss die Datenstruktur von jedem von uns fest im Griff sein. Kürzlich habe ich auch mit einer zweiten Untersuchung von Datenstrukturen begonnen, um die Gruben auszugleichen, die ich damals gegraben habe. . . . . . Als ich im Unterricht war, habe ich nur die Vorlesungen verfolgt und selbst keine Datenstruktur implementiert, geschweige denn Datenstrukturen zur Lösung von Problemen verwendet. Jetzt ist es an der Zeit, die Lücke zu füllen und zu kämpfen. Ich möchte die Kinder, die meinen Blog lesen, daran erinnern, dass das Studium eines Grundkurses niemals unterschätzt werden muss mit doppeltem Aufwand wirkt es sich entweder direkt auf die Fähigkeiten einer Person aus usw. . . . . . Graben Sie sich kein Loch

Kommen wir zum Punkt des Wissens über die Datenstruktur verknüpfter Listen. Hier ist eine kurze Einführung:

Verknüpfte Listen sind nichtlinear und nicht-. Kontinuierliche Daten in physischen Speichereinheiten (die in der Datenlogik linear sind), jeder ihrer Knoten besteht aus zwei Feldern: dem Datenfeld und dem Zeigerfeld. Die tatsächlichen Daten werden im Datenfeld gespeichert, und das Zeigerfeld speichert Zeigerinformationen, die auf das nächste oder vorherige Element in der verknüpften Liste zeigen. Gerade aufgrund der Existenz von Zeigern ist die Speicherung verknüpfter Listen in physikalischen Einheiten diskontinuierlich.

Die Vor- und Nachteile verknüpfter Listen liegen gleichermaßen auf der Hand. Verglichen mit linearen Listen sind verknüpfte Listen beim Hinzufügen und Löschen von Knoten effizienter, da sie im Gegensatz zu linearen Listen (Arrays), die das Verschieben von Elementen erfordern, nur Zeigerinformationen ändern müssen, um den Vorgang abzuschließen. Ebenso ist die Länge einer verknüpften Liste theoretisch unendlich (innerhalb der Speicherkapazität) und die Länge kann dynamisch geändert werden, was große Vorteile gegenüber linearen Listen hat. Da lineare Tabellen nicht zufällig auf Knoten zugreifen können und nur über Zeigerdurchlaufabfragen entlang der verknüpften Liste aufgerufen werden können, ist die Effizienz des Zugriffs auf Datenelemente entsprechend relativ gering.

Das Folgende ist der JS-Teil

Die darin gekapselten allgemeinen Methoden und Beschreibungen:

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

Die Algorithmusbeschreibungen jeder gemeinsamen Methode werden hier nicht geschrieben, I glaube, dass jeder es leicht lesen und verstehen kann, schließlich handelt es sich um sehr grundlegendes Wissen.

Einfach verknüpfte Liste:

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; 
 } 
  
}

Zirkular verknüpfte Liste: Zeigen Sie basierend auf der einfach verknüpften Liste mit dem Zeiger des Endknotens auf den Kopfknoten, um eine kreisförmig verknüpfte Liste zu bilden. Ausgehend von jedem Knoten in einer zirkulär verknüpften Liste kann die gesamte verknüpfte Liste durchlaufen werden.

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; 
 };  
 
}

Verwendung:

Erweitern Sie die Methode außerhalb der Klasse:

Das Obige ist was Ich habe es für alle zusammengestellt und hoffe, dass es in Zukunft für alle hilfreich sein wird.

Verwandte Artikel:

So implementieren Sie Zirkelverweise zwischen Komponenten in Vue.js

Es gibt Beispiele für asynchrone Komponenten in Vue

So beheben Sie den maximalen Aufrufstapelfehler in nodejs

So implementieren Sie eine Blog-Verwaltungsplattform in Vue+SpringBoot

Das obige ist der detaillierte Inhalt vonSo verwenden Sie einfach verknüpfte Listen und zirkulär verknüpfte Listen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!