Nachdem wir eine Knotenklasse und eine verknüpfte Listenklasse erstellt haben, schauen wir uns nun die Einfüge- und Löschoperationen an, die auf einer einfach verknüpften Liste ausgeführt werden.
Einfügeoperation auf einer einfach verknüpften Liste
Eine Einfügeoperation fügt einen Knoten in die Liste ein. Es kann drei Fälle für die Einfügeoperation geben.
- Einfügen eines neuen Knotens vor dem Kopf (am Anfang der Liste).
- Einfügen eines neuen Knotens nach dem Schwanz (d.h. am Ende der Liste).
- Einfügen eines neuen Knotens in der Mitte der Liste (an einer beliebigen Position).
Einfügen eines Knotens am Anfang der einfach verketteten Liste.
In diesem Fall wird ein neuer Knoten vor dem aktuellen Kopfknoten eingefügt. Um diese Operation auszuführen, erstellen wir zunächst einen Knoten. Der neu erstellte Knoten hat zwei Eigenschaften, die in der Konstruktorfunktion der Klasse Node definiert sind, nämlich data und next.
LinkedList.prototype.insertAtBeginning = function(data){// A newNode object is created with property data and next = null let newNode = new Node(data);// The pointer next is assigned head pointer so that both pointers now point at the same node. newNode.next = this.head;// As we are inserting at the beginning the head pointer needs to now point at the newNode.
this.head = newNode; return this.head;}
Einfügen eines Knotens am Ende der einfach verketteten Liste.
In diesem Fall wird ein neuer Knoten am Ende der Liste hinzugefügt. Um diese Operation zu implementieren, müssen wir die Liste durchlaufen, um den Endknoten zu finden, und den nächsten Zeiger des Endknotens so ändern, dass er auf den neu erstellten Knoten statt auf null zeigt.
Anfänglich ist die Liste leer und das head zeigt auf null.
LinkedList.prototype.insertAtEnd = function(data){// A newNode object is created with property data and next=null
let newNode = new Node(data);// When head = null i.e. the list is empty, then head itself will point to the newNode. if(!this.head){
this.head = newNode;
return this.head;
}// Else, traverse the list to find the tail (the tail node will initially be pointing at null), and update the tail's next pointer. let tail = this.head;
while(tail.next !== null){
tail = tail.next;
}
tail.next = newNode; return this.head;}
Einfügen eines Knotens an einer gegebenen zufälligen Position in einer einfach verketteten Liste
Um diese Operation zu implementieren, müssen wir die Liste durchlaufen, bis wir den Knoten an der gewünschten Position erreichen. Dann weisen wir dem Positionsknoten den next-Zeiger von newNode auf den nächsten Knoten zu. Der nächste Zeiger des Positionsknotens kann dann aktualisiert werden, um auf den newNode zu zeigen.
// A helper function getAt() is defined to get to the desired position. This function can also be later used for performing delete operation from a given position. LinkedList.prototype.getAt = function(index){
let counter = 0;
let node = this.head;
while (node) {
if (counter === index) {
return node;
}
counter++;
node = node.next;
}
return null;
}// The insertAt() function contains the steps to insert a node at a given index. LinkedList.prototype.insertAt = function(data, index){// if the list is empty i.e. head = null if (!this.head) {
this.head = new Node(data);
return;
}// if new node needs to be inserted at the front of the list i.e. before the head. if (index === 0) {
this.head = new Node(data, this.head);
return;
}// else, use getAt() to find the previous node. const previous = this.getAt(index - 1);
let newNode = new Node(data);
newNode.next = previous.next;
previous.next = newNode;
return this.head
}