JavaScript-Programm zum Einfügen von Knoten in eine verknüpfte Liste

Eine verknüpfte Liste ist eine Datenstruktur mit unterschiedlichen Längen. Jeder Knoten kann gelöscht oder zur verknüpften Liste hinzugefügt werden. In diesem Tutorial implementieren wir ein vollständiges Programm zum Einfügen von Knoten in eine verknüpfte Liste mit räumlicher und zeitlicher Komplexität. Lassen Sie uns zunächst die Problemstellung verstehen.

Einführung in das Problem

In der gegebenen Frage erhalten wir eine verknüpfte Liste und da wir die Größe der verknüpften Liste ändern können, indem wir Knoten in der verknüpften Liste hinzufügen oder entfernen, werden wir Knoten in der verknüpften Liste hinzufügen oder einfügen.

In einer verknüpften Liste können wir neue Knoten an drei verschiedenen Stellen hinzufügen: vorne, nach dem letzten Knoten und in der Mitte der Liste. Die angegebene verknüpfte Liste lautet beispielsweise -

1 -> 2 -> 3 -> 4 -> 5 -> null, wir müssen einen zufälligen Knoten mit dem Wert 9 hinzufügen. Daher gibt es viele Fälle, in denen Knoten hinzugefügt werden müssen, z. B. -

• Knoten am Anfang hinzufügen - 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

• Knoten in der Mitte hinzufügen – 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null

• Knoten am Ende hinzufügen - 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> null

Sehen wir uns Möglichkeiten an, die folgenden Aufgaben zu lösen -

Knoten am Anfang der verknüpften Liste hinzufügen

Beispiel

Um einen Knoten am Anfang der verknüpften Liste hinzuzufügen, müssen wir einen neuen Knoten erstellen und den Kopf der verknüpften Liste als nächsten Knoten an den neuen Knoten übergeben, dann den Kopf an den neuen Knoten verschieben und den neuen Knoten hinzufügen Knoten an den Anfang der verknüpften Liste.

// creating the linked list node
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data){
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}
function add(data) {
   var new_node = new Node(data);
   new_node.next = head;
   return new_node;
}

var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)

head = add(7);
var data = 0;
while(head != null) {
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding a node at starting: ")
console.log(data + "null")

Die Zeitkomplexität des obigen Codes beträgt O(1), da wir nur einen Zeiger bewegen müssen und kein zusätzlicher Raum verwendet wird, wodurch die Raumkomplexität O(1) wird.

Knoten in der Mitte der verknüpften Liste hinzufügen

Beispiel

Um einen Knoten in der Mitte einer verknüpften Liste hinzuzufügen, müssen wir einen neuen Knoten erstellen und diesen Knoten übergeben, bevor wir den neuen Knoten der verknüpften Liste als nächsten Knoten des neuen Knotens hinzufügen können. Dadurch wird der neue Knoten hinzugefügt Knoten zur verknüpften Liste in der Mitte.

// creating the linked list node
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}
function add(data,head) {
   var new_node = new Node(data);
   var temp = head;
   while(temp.value != 3) {
      temp  = temp.next;
   }
   new_node.next = temp.next;
   temp.next = new_node;
   return head;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
head = add(7,head);
var data = 0;
while(head != null) {
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding node in middle:")
console.log(data + "null")

Die zeitliche Komplexität des obigen Codes beträgt O(N), da wir zu dem Knoten wechseln müssen, an dem ein neuer Knoten hinzugefügt werden muss. Die Raumkomplexität des obigen Prozesses beträgt O(1), da wir keinen zusätzlichen Raum verbrauchen.

Knoten am Ende der verknüpften Liste hinzufügen

Beispiel

Um einen Knoten am Ende der verknüpften Liste hinzuzufügen, müssen wir einen neuen Knoten erstellen und diesen Knoten nach dem Endknoten hinzufügen und den Endknoten zum nächsten Knoten verschieben.

// creating the linked list node
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
   }

function add(data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next
   return tail;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)

tail = add(7);
var data = 0;
while(head != null){
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding a node at the end: ")
console.log(data + "null")

Die Zeitkomplexität des obigen Codes beträgt O(1), da wir nur einen Zeiger bewegen müssen und kein zusätzlicher Raum verwendet wird, wodurch die Raumkomplexität O(1) wird.

Fazit

Im obigen Tutorial haben wir gelernt, wie man auf drei Arten einen neuen Knoten zu einer vorhandenen verknüpften Liste hinzufügt. Wir haben korrekten Code mit Erklärungen und zeitlichen und räumlichen Komplexitäten gesehen. Das Hinzufügen eines Knotens in der Mitte der verknüpften Liste benötigt O(N) Zeit, während in den anderen beiden Fällen seine Zeitkomplexität O(1) beträgt und für alle drei Möglichkeiten die Raumkomplexität O(1) beträgt.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Einfügen von Knoten in eine verknüpfte Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!