Dieser Artikel bietet Ihnen eine detaillierte Einführung in verknüpfte Listen in JavaScript. Ich hoffe, dass er für Freunde hilfreich ist.
Verknüpfte Listen und Arrays
Jeder hat Arrays in js verwendet. Arrays sind eigentlich eine sequentielle Speicherstruktur linearer Tabellen. Ihr Merkmal ist, dass sie eine Reihe von Adressen verwendet . Aufeinanderfolgende Speicherzellen speichern nacheinander Datenelemente. Seine Mängel sind auch auf seine Eigenschaften zurückzuführen. Beispielsweise muss beim Löschen oder Einfügen eines Arrays möglicherweise eine große Anzahl von Elementen verschoben werden.
Hier ist eine grobe Simulation des Einfügevorgangs des Arrays:
insert(arr, index, data){
for(let i = index + 1; i <p> Aus dem obigen Code können wir erkennen, dass das Einfügen und Löschen des Arrays ein O(n)-Vorgang sein kann . Dies führt dazu, dass die Datenstruktur der verknüpften Liste nicht erfordert, dass logisch benachbarte Elemente an physischen Orten benachbart sind, sodass sie nicht die Mängel der sequentiellen Speicherstruktur aufweist Array in einem kontinuierlichen Raum. Vorteile des Zugriffs. </p><h3>Einseitig verknüpfte Liste</h3><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png" title="1546394138978971.png" alt="Detaillierte Einführung in verknüpfte Listen in JavaScript"></span></p><h4>Funktionen der einseitig verknüpften Liste: </h4>Verwenden Sie einen beliebigen Speicherplatz zum Speichern von Datenelementen (der Speicherplatz kann hier kontinuierlich oder diskontinuierlich sein)
Jeder Knoten (Knoten) besteht aus den Daten selbst und einem Zeiger auf die nachfolgenden Knoten bestehen aus
Der Zugriff auf die gesamte verknüpfte Liste muss beim Kopfzeiger beginnen, der auf den ersten Knoten
dem letzten Knoten zeigt Der Zeiger zeigt auf null (NULL)
Knoten erstellen
Knoten einfügen
Knoten suchen/durchqueren
Knoten löschen
Zusammenführen
Zeiger zeigt auf Null
Speicherdaten
class Node {
constructor(key) {
this.next = null;
this.key = key;
}
}Jede verknüpfte Liste hat einen Kopfzeiger, der auf den ersten Knoten zeigt. Wenn kein Knoten vorhanden ist, zeigt er auf NULL
class List {
constructor() {
this.head = null;
}
} static createNode(key) {
return new createNode(key);
}Lassen Sie mich hier erklären, dass ich eine statische Methode zum Erstellen des Knotens verfügbar gemacht habe, anstatt ihn direkt in den Einfügevorgang einzukapseln, weil ich das Gefühl habe, dass eine solche Logik wird mehr sein. Seien Sie korrekter. Erstellen Sie eine verknüpfte Liste aus -> Erstellen Sie einen Knoten -> Fügen Sie den Knoten in die verknüpfte Liste ein. Möglicherweise stoßen Sie auf einige Artikel, die eine Möglichkeit vorstellen, ein Datenelement direkt als Parameter zum Aufrufen der Einfügeoperation zu verwenden und einen Knoten innerhalb der Einfügung zu erstellen.
Der Einfügevorgang muss nur den Zeiger des Knotens anpassen. Es gibt zwei Fälle:
Kopf existiert nicht. Zeigt auf einen Knoten, was darauf hinweist, dass der aktuell eingefügte Knoten der erste ist.
Kopf zeigt auf den Knoten
Der Zeiger des neuen Knotens zeigt auf den Knoten, auf den der ursprüngliche Kopf zeigt
insert(node) {
// 如果head有指向的节点
if(this.head){
node.next = this.head;
}else {
node.next = null;
}
this.head = node;
}Nach dem Knoten suchen
Suche vom Kopf aus starten
find(key) {
let node = this.head;
while(node !== null && node.key !== key){
node = node.next;
}
return node;
}Zeigen Sie mit dem Kopf auf den Knoten, den Sie löschen möchten. Löschen Sie den nächsten Knoten der Knoten (node.next)
und zeigen Sie den Zeiger in prevNode auf NULL
Löschen Sie etwas in der Mitte der Knotenliste
Zeigen Sie den Zeiger in prevNode auf den aktuellen Knoten, der gelöscht werden soll gelöscht Der nächste Knoten dieses Knotens
delete(node) {
// 第一种情况
if(node === this.head){
this.head = node.next;
return;
}
// 查找所要删除节点的上一个节点
let prevNode = this.head;
while (prevNode.next !== node) {
prevNode = prevNode.next;
}
// 第二种情况
if(node.next === null) {
prevNode.next = null;
}
// 第三种情况
if(node.next) {
prevNode.next = node.next;
}
}Der Gesamtcode der einseitig verknüpften Liste
class ListNode {
constructor(key) {
this.next = null;
this.key = key;
}
}
class List {
constructor() {
this.head = null;
this.length = 0;
}
static createNode(key) {
return new ListNode(key);
}
// 往头部插入数据
insert(node) {
// 如果head后面有指向的节点
if (this.head) {
node.next = this.head;
} else {
node.next = null;
}
this.head = node;
this.length++;
}
find(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}
delete(node) {
if (this.length === 0) {
throw 'node is undefined';
}
if (node === this.head) {
this.head = node.next;
this.length--;
return;
}
let prevNode = this.head;
while (prevNode.next !== node) {
prevNode = prevNode.next;
}
if (node.next === null) {
prevNode.next = null;
}
if (node.next) {
prevNode.next = node.next;
}
this.length--;
}
}Wenn Sie haben die obige Einführung eingegeben. Wir haben die Einwegliste bereits verstanden, daher ist die hier eingeführte Zweiwegliste tatsächlich ähnlich.
Knoten initialisieren
Zeiger auf den vorherigen Knoten
指向后一个节点的指针
节点数据
class ListNode {
this.prev = null;
this.next = null;
this.key = key;
}头指针指向NULL
class List {
constructor(){
this.head = null;
}
} static createNode(key){
return new ListNode(key);
}看上图中head后面的第一个节点可以知道，该节点的prev指向NULL
节点的next指针指向后一个节点, 也就是当前头指针所指向的那个节点
如果head后有节点，那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛)
最后将head指向新的节点
insert(node) {
node.prev = null;
node.next = this.head;
if(this.head){
this.head.prev = node;
}
this.head = node;
}这里和单向节点一样，就直接贴代码了
search(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}和之前单向链表一样，分三种情况去看：
删除的是第一个节点
head指向所要删除节点的下一个节点
下一个节点的prev指针指向所要删除节点的上一个节点
删除的是中间的某个节点
所要删除的前一个节点的next指向所要删除的下一个节点
所要删除的下一个节点的prev指向所要删除的前一个节点
删除的是最后一个节点
要删除的节点的上一个节点的next指向null（也就是指向删除节点的next所指的地址）
delete(node) {
const {prev,next} = node;
delete node.prev;
delete node.next;
if(node === this.head){
this.head = next;
}
if(next){
next.prev = prev;
}
if(prev){
prev.next = next;
}
} class ListNode {
constructor(key) {
// 指向前一个节点
this.prev = null;
// 指向后一个节点
this.next = null;
// 节点的数据(或者用于查找的键)
this.key = key;
}
}
/**
* 双向链表
*/
class List {
constructor() {
this.head = null;
}
static createNode(key) {
return new ListNode(key);
}
insert(node) {
node.prev = null;
node.next = this.head;
if (this.head) {
this.head.prev = node;
}
this.head = node;
}
search(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}
delete(node) {
const { prev, next } = node;
delete node.prev;
delete node.next;
if (node === this.head) {
this.head = next;
}
if (prev) {
prev.next = next;
}
if (next) {
next.prev = prev;
}
}
}这里做一个小总结吧，可能有一部分人读到这里还不是特别的明白，我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念，就是有一个head，然后在有好多的节点(Node)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。
Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in verknüpfte Listen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
