JavaScript-Programm zum Austauschen von Knoten in einer verknüpften Liste ohne Datenaustausch

JavaScript-Programm zum Austauschen von Knoten in einer verknüpften Liste ohne Datenaustausch ist ein häufiges Problem bei der Webentwicklung, bei dem die Reihenfolge der Knoten in einer verknüpften Liste neu angeordnet werden muss. Eine verknüpfte Liste ist eine Datenstruktur, die aus Knoten besteht, wobei jeder Knoten ein Datenelement und einen Verweis auf den nächsten Knoten in der Liste enthält.

In diesem Artikel lernen wir ein vollständiges Tutorial zum Austausch von Knoten in einer verknüpften Liste ohne Datenaustausch mithilfe von JavaScript. Definieren wir also zunächst den Austauschknoten und fahren dann mit dem Tutorial fort. Also, lerne weiter!

Exchange-Knoten

Das Vertauschen von Knoten in einer verknüpften Liste bedeutet, dass wir die Positionen zweier Knoten vertauschen. Es gibt viele Möglichkeiten, Knoten in einer verknüpften Liste auszutauschen. Ein Ansatz besteht darin, Daten über Knoten hinweg auszutauschen. Dies kann jedoch bei der Verarbeitung großer Datenmengen ineffizient sein. Ein anderer Ansatz besteht darin, Zeiger auf Knoten auszutauschen. Dies ist effizienter, da wir keine Daten kopieren müssen.

Lassen Sie uns den Austauschknoten anhand eines Beispiels verstehen

Beispiel

Angenommen, wir haben eine verlinkte Liste wie unten -

1 -> 2 -> 3 -> 4 -> 5

Wir möchten den zweiten und vierten Knoten tauschen, um Folgendes zu erhalten:

1 -> 4 -> 3 -> 2 -> 5

Um dies zu erreichen, ohne Daten in Knoten auszutauschen, müssen wir die Verbindungen zwischen Knoten ändern. Die resultierende verknüpfte Liste sollte dieselben Daten wie die ursprüngliche verknüpfte Liste enthalten, die Reihenfolge der Knoten hat sich jedoch geändert.

Also identifizieren wir zunächst die beiden zu tauschenden Knoten: Knoten 2 und Knoten 4. Wir müssen auch die Knoten vor und nach diesen Knoten in der Liste im Auge behalten.

In diesem Beispiel sind die Knoten vor und nach Knoten 2 1 bzw. 3. Die Knoten vor und nach Knoten 4 sind 3 bzw. 5.

Als nächstes müssen wir die Verbindungen zwischen den Knoten aktualisieren. Wir setzen zunächst den nächsten Zeiger des Knotens vor Knoten 2 auf Knoten 4. Anschließend setzen wir den nächsten Zeiger von Knoten 2 auf Knoten 5 (da Knoten 4 nun hinter Knoten 2 liegt). Schließlich setzen wir den nächsten Zeiger von Knoten 4 auf Knoten 3 (da Knoten 2 jetzt hinter Knoten 4 liegt).

Die generierte Linkliste sieht so aus -

1 -> 4 -> 3 -> 2 -> 5

Hinweis – Die Daten in jedem Knoten ändern sich nicht, nur die Reihenfolge der Knoten.

Schauen wir uns nun den Algorithmus an, den wir verwenden werden, um Knoten in einer verknüpften Liste auszutauschen, ohne Daten auszutauschen.

Algorithmus

SCHRITT1: Identifizieren Sie die beiden Knoten, die ausgetauscht werden müssen

Der erste Schritt besteht darin, die beiden Knoten zu identifizieren, die ausgetauscht werden müssen. Angenommen, wir möchten Knoten A und Knoten B vertauschen.

Schritt 2: Suchen Sie den vorherigen Knoten der beiden auszutauschenden Knoten

Wir müssen die Knoten vor den Knoten A und B in der verknüpften Liste finden. Wir nennen diese Knoten PrevA bzw. PrevB.

Schritt 3: Aktualisieren Sie den nächsten Zeiger des vorherigen Knotens, um auf einen anderen Knoten zu zeigen

Jetzt müssen wir die nächsten Zeiger von PrevA und PrevB aktualisieren, um auf die richtigen Knoten zu zeigen. Dazu gehört die Aktualisierung des nächsten Zeigers von PrevA so, dass er auf Knoten B zeigt, und die Aktualisierung des nächsten Zeigers von PrevB so, dass er auf Knoten A zeigt.

Schritt 4: Aktualisieren Sie den nächsten Zeiger des auszutauschenden Knotens, sodass er auf den richtigen Knoten zeigt

Als nächstes müssen wir die nächsten Zeiger der Knoten A und B aktualisieren, um auf die richtigen Knoten zu zeigen. Dazu gehört die Aktualisierung des nächsten Zeigers von Knoten A, sodass er auf den Knoten neben Knoten B zeigt, und die Aktualisierung des nächsten Zeigers von Knoten B so, dass er auf den Knoten neben Knoten A zeigt.

Schritt 5: Wiederholen Sie die obigen Schritte für alle anderen Knoten, die ausgetauscht werden müssen

Wenn wir mehr als zwei Knoten austauschen müssen, können wir die obigen Schritte für jedes Knotenpaar wiederholen, das ausgetauscht werden muss.

Nach Abschluss dieser Schritte werden die Knoten in der verknüpften Liste ausgetauscht, nicht jedoch ihre Daten. Lassen Sie uns nun den obigen Algorithmus anhand eines Beispiels für seine Implementierung mit Javascript verstehen.

Beispiel

In diesem Programm definieren wir zunächst eine „Node“-Klasse, um die Knoten der verknüpften Liste zu erstellen, und definieren eine „LinkedList“-Klasse, um die verknüpfte Liste zu erstellen und zu betreiben. Die Funktion „swapNodes“ in der Klasse „LinkedList“ implementiert den zuvor beschriebenen Swap-Algorithmus.

// Define a Node class to create nodes of linked list
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
// Define a LinkedList class to create and manipulate the linked list
class LinkedList {
   constructor() {
      this.head = null;
   }
   // Function to swap two nodes in the linked list
   swapNodes(node1, node2) {
      // If both nodes are the same, no need to swap
      if (node1 === node2) {
         return;
      }
      // Find the previous nodes of both nodes to be swapped
      let prevNode1 = null;
      let currentNode1 = this.head;
      while (currentNode1 && currentNode1 !== node1) {
         prevNode1 = currentNode1;
         currentNode1 = currentNode1.next;
      }
      let prevNode2 = null;
      let currentNode2 = this.head;
      while (currentNode2 && currentNode2 !== node2) {
         prevNode2 = currentNode2;
         currentNode2 = currentNode2.next;
      }
      // If either node1 or node2 is not found, return
      if (!currentNode1 || !currentNode2) {
         return;
      }
      // Update the next pointers of the previous nodes to point to the other node
      if (prevNode1) {
         prevNode1.next = currentNode2;
      } else {
         this.head = currentNode2;
      }
      if (prevNode2) {
         prevNode2.next = currentNode1;
      } else {
         this.head = currentNode1;
      }
      // Swap the next pointers of the nodes to be swapped to point to the correct nodes
      let temp = currentNode1.next;
      currentNode1.next = currentNode2.next;
      currentNode2.next = temp;
      // Print the swapped linked list
      console.log("Swapped linked list:");
      let current = this.head;
      while (current) {
         process.stdout.write(current.data + " -> ");
         current = current.next;
      }
      console.log("null");
   }
   // Function to add a Node at the end of the linked list
   addNode(data) {
      let node = new Node(data);
      if (!this.head) {
         this.head = node;
      } else {
         let current = this.head;
         while (current.next) {
            current = current.next;
         }
         current.next = node;
      }
   }
}
// Create a linked list
let linkedList = new LinkedList();
linkedList.addNode(1);
linkedList.addNode(2);
linkedList.addNode(3);
linkedList.addNode(4);
// Print the original linked list
console.log("Original linked list:");
let current = linkedList.head;
while (current) {
   process.stdout.write(current.data + " -> ");
   current = current.next;
}
console.log("null");
// Swap node 2 and node 4
let node2 = linkedList.head.next;
let node4 = linkedList.head.next.next.next;
linkedList.swapNodes(node2, node4);

Fazit

In diesem Tutorial zeigen wir ein JavaScript-Programm, das diesen Algorithmus implementiert, der Knoten in einer verknüpften Liste erfolgreich austauscht, ohne ihre Daten auszutauschen. Ich hoffe, das hilft unseren Lesern. Viel Spaß beim Lernen!

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Austauschen von Knoten in einer verknüpften Liste ohne Datenaustausch. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!