In diesem Artikel stellen wir Ihnen vor, wie Sie eine doppelt verknüpfte Liste in JavaScript implementieren. Wir hoffen, dass er Freunden in Not hilfreich sein wird!
Was ist eine doppelt verknüpfte Liste?
In einer doppelt verknüpften Liste hat jeder Knoten einen Verweis auf den vorherigen Knoten und den nächsten Knoten. Der vorherige und nächste Start- und Endknoten sollten auf Null zeigen.
Implementierung einer doppelt verknüpften Liste
Im folgenden Code erstellen wir eine Hilfsklasse Node , das drei Attributdaten enthält: prev, next.
class Node {
constructor(data){
this.data = data; // data
this.prev = null; // 引用prev节点
this.next = null; // 引用next节点
}}Daten: Die Daten, die wir dem Knoten hinzufügen müssen.
prev: bezieht sich auf den vorherigen Knoten.
next: bezieht sich auf den nächsten Knoten.
Der Hauptalgorithmus beginnt
class DoublyLinkedList{
constructor(){
this.head = null;
this.tail = null;
this.length = null;
}}Im obigen Code erstellen wir eine DoublyLinkedList-Klasse mit drei Eigenschaften: Kopf, Schwanz und Länge.
Kopf: Es ist der erste Knoten in der Liste.
tail: Der letzte Knoten in der Liste.
Länge: Wie viele Knoten gibt es in der Liste?
Fügen wir diese Funktionen zu unserer doppelt verknüpften Liste hinzu
Push-Methode
Push-Methode hilft uns, neue Knoten am Ende der verknüpften Liste hinzuzufügen.
push(data){
const node = new Node(data);
if(!this.head){
this.head = node;
this.tail = node;
}else{
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.length++;
}1. Im obigen Code deklarieren wir zunächst eine neue Variable und rufen den Knotenkonstruktor auf.
2. Wenn es keinen this.head gibt, sind this.head und this.tail die neuen Knoten, die wir in Schritt 1 erstellt haben.
3. Wenn bereits ein Knoten vorhanden ist
sollte das neue Attribut node.prev this.tail sein
this.tail.next sollte ein neuer Knoten sein
Schwanz aktualisieren.
4. Erhöhen Sie die Länge um 1.
Pop-Methode
hilft uns, den letzten Knoten aus der Liste zu entfernen.
In einer doppelt verknüpften Liste ist es einfach, den letzten Knoten aus der Liste zu entfernen, da im Tail-Attribut ein Verweis auf den vorherigen Knoten vorhanden ist.
pop(){
if(!this.head) return null
// tail是最后一个节点，因此我们从tail中提取prev属性
const prevNode = this.tail.prev
if(prevNode){
prevNode.next = null;
this.tail = prevNode; // 更新tail
}else{
// 如果prev属性为null，则表示只有一个节点
this.head = null;
this.tail = null;
}
this.length--;
}1. Im obigen Code deklarieren wir zunächst eine neue Variable und speichern das vorherige Attribut von tail.
2. Wenn der vorherige Knoten gefunden wird.
Letzten Knoten löschen
Ende aktualisieren.
3. Wenn der vorherige Knoten leer ist, bedeutet das, dass es nur einen Knoten gibt
this.head und this.tail sollten null sein.
4. Reduzieren Sie die Länge um 1.
insertBeginning
insertBeginning-Methode hilft uns, einen neuen Knoten am Anfang der Liste einzufügen.
insertBeginning(data){
// 创建新节点
const node = new Node(data);
// 如果没有节点
if(!this.head) {
this.head = node;
this.tail = node;
}else{
this.head.prev = node
node.next = this.head;
this.head = node;
}
// 增加长度
this.length++;
}removeFirst-Methode
removeFirst-Methode hilft uns, den ersten Knoten aus der verknüpften Liste zu löschen.
removeFirst(){
if(!this.head) return null
// 存储第二个节点
const node = this.head.next;
if(node){
// 删除前一个节点
node.prev = null
// 更新head
this.head = node
}else{
// 只有一个节点，所以我们将head和tail更新为null
this.head = null
this.tail = null
}
this.length--;
}Verwandte Empfehlungen: „Javascript-Tutorial“
Das obige ist der detaillierte Inhalt vonJavaScript implementiert eine doppelt verknüpfte Liste (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
