Na het maken van een node klasse en een gelinkte lijst klasse, laten we nu eens kijken naar de insert en delete operaties die worden uitgevoerd op een enkelvoudig gelinkte lijst.
Insert operatie op een enkelvoudig gelinkte lijst
Een insert operatie voegt een node in de lijst in. Er kunnen drie gevallen zijn voor de insert operatie.
- Een nieuwe node invoegen vóór de head (aan het begin van de lijst).
- Een nieuwe node invoegen na de tail (d.w.z. aan het eind van de lijst).
- Een nieuw knooppunt in het midden van de lijst plaatsen (op een gegeven willekeurige positie).
en knooppunt aan het begin van de enkelvoudig gekoppelde lijst plaatsen.
In dit geval wordt een nieuw knooppunt toegevoegd vóór het huidige hoofdknooppunt. Om deze operatie uit te voeren zullen we eerst een node creëren. De nieuw aangemaakte node zal twee eigenschappen hebben zoals gedefinieerd in de constructor functie van de Node klasse, data en 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;}
Een node toevoegen aan het einde van de enkelvoudig gekoppelde lijst.
In dit geval wordt een nieuwe node toegevoegd aan het einde van de lijst. Om deze operatie uit te voeren moeten we door de lijst gaan om de staartknoop te vinden en de volgende pointer van de staart aanpassen zodat hij naar de nieuw aangemaakte knoop wijst in plaats van naar null.
In eerste instantie is de lijst leeg en wijst de head naar 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;}
Een node invoegen op een gegeven willekeurige positie in een enkelvoudig gekoppelde lijst
Om deze bewerking uit te voeren, moeten we de lijst doorlopen totdat we de node op de gewenste positie hebben bereikt. Vervolgens wijzen we de volgende pointer van de newNode toe aan de volgende node van de positie-node. De volgende pointer van de positie-node kan dan worden bijgewerkt om naar de newNode te wijzen.
// 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
}