Einführung in die Implementierungsmethode der verknüpften Liste der JavaScript-Datenstruktur (Bild und Text)

Verknüpfte Liste ist eine allgemeine Datenstruktur. Es handelt sich um eine Struktur, die Speicher dynamisch zuweist. In diesem Artikel wird hauptsächlich die Implementierung verknüpfter Listen in der JavaScript-Datenstruktur vorgestellt, die einen guten Referenzwert hat. Werfen wir einen Blick darauf mit dem Editor unten

Das vorherige Poster besprach die Implementierung von Datenstrukturstapeln bzw. -warteschlangen. Die damals verwendeten Datenstrukturen wurden alle mithilfe von Arrays implementiert, aber manchmal sind Arrays nicht die meisten Optimal. Optimale Datenstruktur, zum Beispiel beim Hinzufügen und Löschen von Elementen in einem Array, andere Elemente müssen verschoben werden und die Verwendung der spit()-Methode in JavaScript erfordert keinen Zugriff auf andere Elemente. Wenn Ihnen die Verwendung von Arrays langsam vorkommt, sollten Sie die Verwendung verknüpfter Listen in Betracht ziehen.

Das Konzept der verknüpften Liste

Verknüpfte Liste ist eine gängige Datenstruktur. Es handelt sich um eine Struktur, die Speicher dynamisch zuweist. Die verknüpfte Liste verfügt über eine „Kopfzeiger“-Variable, dargestellt durch Kopf, die eine Adresse speichert, die auf ein Element zeigt. Jeder Knoten verwendet die Referenz eines Objekts, um auf seinen Nachfolger zu verweisen. Eine Referenz, die auf einen anderen Knoten zeigt, wird als Kette bezeichnet.

Array-Elemente werden durch Indizes (Positionen) referenziert, während verknüpfte Listenelemente durch ihre Beziehungen referenziert werden. Daher ist die Einfügeeffizienz der verknüpften Liste sehr hoch. Die folgende Abbildung zeigt den Einfügevorgang des verknüpften Listenknotens d:

　

Löschvorgang:

Objektbasierte verknüpfte Liste

Wir definieren zwei Klassen, die Node-Klasse und die LinkedList-Klasse. Node ist die Knotendaten, und LinkedList speichert die Methoden dafür Betreiben der verknüpften Liste.

Erster Blick auf die Node-Klasse:

function Node(element){
  this.element = element;
   this.next = null;
 }

Element wird verwendet, um die Daten auf dem Knoten zu speichern, und als nächstes wird es verwendet, um den Link zu speichern, der auf den Knoten zeigt.

LinkedList-Klasse:

function LinkedList(){
     this.head = new Node('head');
     this.find = find;
     this.insert = insert;
     this.remove = remove;
     this.show = show;
}

find()-Methode, ausgehend vom Kopfknoten, Suche entlang der verknüpften Listenknoten, bis ein Element gefunden wird, das dem Elementinhalt entspricht, dann der Knoten zurückgegeben. Wenn nicht gefunden, leer zurückgeben.

function find(item){
     var currentNode = this.head;//从头结点开始
     while(currentNode.element!=item){
         currentNode = currentNode.next;
     }
     return currentNode;//找到返回结点数据，没找到返回null
}

Methode einfügen. Wie aus der vorherigen Demonstration des Einfügens von Elementen hervorgeht, gibt es vier einfache Schritte zum Implementieren des Einfügens:

1. Erstellen Sie einen Knoten

2. Suchen Sie den Zielknoten

3. Ändern Sie den Zielknoten. Der nächste Punkt des Punktes zeigt auf den Link

4. Weisen Sie den nächsten Wert des Zielknotens der Methode next

function insert(newElement,item){
     var newNode = new Node(newElement);
     var currentNode = this.find(item);
     newNode.next = currentNode.next;
     currentNode.next = newNode;
 }

Remove() des zu Knoten, der eingefügt werden soll. Um einen Knoten zu löschen, müssen Sie zunächst den vorherigen Knoten des gelöschten Knotens finden. Aus diesem Grund definieren wir die Methode frontNode():

function frontNode(item){
     var currentNode = this.head;
     while(currentNode.next.element!=item&&currentNode.next!=null){
         currentNode = currentNode.next;
     }   
     return currentNode;
}

Einfache Antwort in drei Schritten:

1. Erstellen Sie einen Knoten

2. Finden Sie den vorherigen Knoten des Zielknotens

3. Ändern Sie den nächsten Knoten des vorherigen Knotens so, dass er auf den Knoten n nach dem gelöschten Knoten zeigt >

function remove(item){
     var frontNode = this.frontNode(item);
     //console.log(frontNode.element);
     frontNode.next = frontNode.next.next;
 }

Show()-Methode:

function show(){
     var currentNode = this.head,result;
     while(currentNode.next!=null){
         result += currentNode.next.element;//为了不显示head结点
         currentNode = currentNode.next;
     }
}

Testprogramm:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

Ausgabe:

Doppelt verknüpfte Liste

Der Übergang vom Kopfknoten zum Endknoten der verknüpften Liste ist sehr einfach, aber manchmal müssen wir von hinten nach vorne durchlaufen. An dieser Stelle können wir dem Node-Objekt ein

-Attribut hinzufügen, das den Link zum Vorgängerknoten speichert. Das Poster verwendet das folgende Diagramm, um das Funktionsprinzip einer doppelt verketteten Liste zu veranschaulichen.

Zuerst fügen wir der Node-Klasse das Front-Attribut hinzu:

function Node(element){
  this.element = element;
  this.next = null;
   this.front = null;
 }

Natürlich benötigen wir auch die entsprechende insert()-Methode und entfernen( ) Methode Nehmen Sie entsprechende Änderungen vor:

function insert(newElement,item){
  var newNode = new Node(newElement);
  var currentNode = this.find(item);
  newNode.next = currentNode.next;
  newNode.front = currentNode;//增加front指向前驱结点
  currentNode.next = newNode;
}
function remove(item){  
  var currentNode = this.find(item);//找到需要删除的节点
  if (currentNode.next != null) {
    currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
    currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
    currentNode.next = null;//并设置前驱与后继的指向为空
    currentNode.front = null;    
  }  
}

Zeigen Sie die verknüpfte Liste in umgekehrter Reihenfolge an:

Sie müssen der doppelt verknüpften Liste eine Methode hinzufügen, um den letzten Knoten zu finden. Die Methode findLast() findet den letzten Knoten in der verknüpften Liste, sodass die Kette nicht von vorne nach hinten durchlaufen werden muss.

function findLast() {//查找链表的最后一个节点
  var currentNode = this.head;
  while (currentNode.next != null) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

Ausgabe in umgekehrter Reihenfolge realisieren:

function showReverse() {
  var currentNode = this.head, result = "";
  currentNode = this.findLast(); 
  while(currentNode.front!=null){
    result += currentNode.element + " ";
    currentNode = currentNode.front;
  }
  return result;
}

Testprogramm:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list);
list.remove("b");
console.log(list.show());
console.log(list.showReverse());

Ausgabe:

Zirkular verknüpfte Liste

Zirkulär verknüpfte Liste ist eine andere Form der verknüpften Speicherstruktur. Sein Merkmal besteht darin, dass das Zeigerfeld des letzten Knotens in der Liste auf den Kopfknoten zeigt und die gesamte verknüpfte Liste einen Ring bildet. Zirkulär verknüpfte Listen ähneln einfach verknüpften Listen und die Knotentypen sind dieselben. Der einzige Unterschied besteht darin, dass beim Erstellen einer zirkulär verknüpften Liste das nächste Attribut des Kopfknotens auf sich selbst zeigen soll, das heißt:

head.next = head

Dieses Verhalten wird auf jedes Element übertragen in den Knoten der verknüpften Liste, sodass das nächste Attribut jedes Knotens auf den Kopfknoten der verknüpften Liste zeigt. Das Poster verwendet das folgende Bild, um eine kreisförmige verknüpfte Liste darzustellen:

Ändern Sie die

Konstruktionsmethode :

function LinkedList(){
  this.head = new Node('head');//初始化
  this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
  this.find = find;
  this.frontNode = frontNode;
  this.insert = insert;
  this.remove = remove;
  this.show = show; 
}

这时需要注意链表的输出方法show()与find()方法，原来的方式在循环链表里会陷入死循环，while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
  var currentNode = this.head;//从头结点开始
  while(currentNode.element!=item&&currentNode.next.element!='head'){
    currentNode = currentNode.next;
  }
  return currentNode;//找到返回结点数据，没找到返回null
}
function show(){
  var currentNode = this.head,result = "";
  while (currentNode.next != null && currentNode.next.element != "head") {   
    result += currentNode.next.element + " ";
    currentNode = currentNode.next;
  }
  return result;
}

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

测试结果：

Das obige ist der detaillierte Inhalt vonEinführung in die Implementierungsmethode der verknüpften Liste der JavaScript-Datenstruktur (Bild und Text). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!