Gemeinsame Nutzung von Beispielen für die JavaScript-Datenstruktur für einfach verknüpfte Listen und zirkuläre verknüpfte Listen

Dieser Artikel stellt hauptsächlich die JavaScript-Datenstrukturen von einfach verknüpften Listen und zirkulär verknüpften Listen vor und stellt detailliert vor, wie JavaScript einfach verknüpfte Listen und zirkulär verknüpfte Listen implementiert. Wenn Sie interessiert sind, kann er Ihnen hoffentlich weiterhelfen alle.

Um auf den Punkt zu kommen, hier eine kurze Einführung in die Datenstrukturkenntnisse verknüpfter Listen:

Eine verknüpfte Liste ist eine nichtlineare und nicht kontinuierliche Datenstruktur in physischen Speichereinheiten ( Es handelt sich um eine lineare Datenlogik. Jeder seiner Knoten besteht aus zwei Domänen: der Datendomäne und der Zeigerdomäne. 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 verlinkter 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 nur die Zeigerinformationen ändern müssen, um den Vorgang abzuschließen, im Gegensatz zu linearen Listen (Arrays), die das Verschieben von Elementen erfordern. 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 hier 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 der einzelnen allgemeinen Methoden werden hier nicht geschrieben Ich glaube, jeder kann es leicht lesen und verstehen, 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 Der Hauptknoten bildet eine kreisförmige verknüpfte Liste. 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:

Methoden außerhalb der Klasse erweitern:

Verwandte Empfehlungen:

Beispiel für die Verwendungsdefinition einer doppelt verknüpften Liste in einer JavaScript-Datenstruktur

Prioritätswarteschlange und zirkuläre Warteschlange in der JavaScript-Datenstruktur

Detaillierte Erläuterung der Definition und Darstellungsmethode des binären Suchbaums in der JavaScript-Datenstruktur

Das obige ist der detaillierte Inhalt vonGemeinsame Nutzung von Beispielen für die JavaScript-Datenstruktur für einfach verknüpfte Listen und zirkuläre verknüpfte Listen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!