Detaillierte Erläuterung des Wissens über verknüpfte Listen zur JavaScript-Datenstruktur

Vor kurzem habe ich das Buch „Javascript Data Structure and Algorithm“ gelesen, um mein Wissen über Datenstruktur und Algorithmen zu ergänzen. Ich hatte das Gefühl, dass mir in diesem Bereich etwas fehlt.

Verknüpfte Liste: speichert eine geordnete Sammlung von Elementen, aber im Gegensatz zu einem Array werden die Elemente in einer verknüpften Liste nicht kontinuierlich im Speicher abgelegt. Jedes Element besteht aus einem Knoten, der das Element selbst speichert, und einer Referenz (auch Zeiger oder Link genannt), die auf das nächste Element verweist.

Vorteile: Jedes Element kann hinzugefügt oder entfernt werden und wird nach Bedarf erweitert, ohne dass andere Elemente verschoben werden müssen. Der Unterschied zwischen

und Array:

Array: Sie können an jeder Position direkt auf jedes Element zugreifen;

Verknüpfte Liste: Sie möchten Um auf die verknüpfte Liste zuzugreifen, muss ein Element der Liste vom Startpunkt (Kopfzeile) aus iteriert werden, bis das erforderliche Element gefunden wird.

Machen Sie sich ein paar Notizen.

function LinkedList(){
var Node = function(element){
this.element = element
this.next = null
}
var length = 0
var head = null
this.append = function(element){
var node = new Node(element)
var current
if(head == null){ //链表为空
head = node
}else{ //链表不为空
current = head
//循环链表，直到最后一项
while(current.next){
current = current.next
}
current.next = node
}
length ++ //更新链表长度
}
this.insert = function(position,element){
var node = new Node(element)
var current = head
var previous
var index = 0
if(position>=1 && position<=length){ //判断是否越界
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.indexOf = function(element){
var current = head
var index = -1
while(current){
if (element === current.element) {
return index
}
index++
current = current.next
}
return -1
}
this.removeAt = function(position){
if(position>-1 && position<length){ //判断是否越界
var current = head
var previous
var 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 index = this.indexOf(element)
return this.removeAt(index)
}
this.isEmpty = function(){
return length == 0
}
this.size = function(){
return length
}
this.toString = function(){
var current = head
var string = ""
while(current){
string = "," + current.element
current = current.next
}
return string.slice(1)
}
this.getHead = function(){
return head
}
}