In this article, I will explore the topic of adding a node to a linked list, building upon the concepts discussed in my previous article on the subject. The focus will be on a Javascript implementation. We will delve deeper into the different operations of adding a node, providing a more detailed and comprehensive understanding of this fundamental operation in linked list data structures.
Adding Operations
When it comes to adding nodes to a linked list, there are several types of operations that one can perform.
The most basic of these is known as appending, which involves adding a new node to the end of the linked list. This is typically done by iterating through the list until the last node is reached, and then adding the new node to the end.
Another common operation is known as prepending, which involves adding a new node to the beginning of the list. This is done by simply setting the new node as the head of the linked list, and updating its next pointer to point to the previous head node.
Other types of adding operations can include inserting a node at a specific position in the list, or concatenating two separate linked lists together.
Visualising Adding Operations
From my experience, having the ability to visualize addition operations is crucial to fully understand how they function. This stands true for any other linked list operations as well. By learning how to visualize operations, you can do any linked list manipulations confidently.
In the interest of brevity and clarity, I will focus solely on the visualization of inserting a node at the nth position in a doubly linked list. Once you grasp this concept, you will find it easy to execute operations such as appending, prepending, and concatenating on any type of linked list without encountering much difficulty.
Addition Illustration
Consider the following doubly linked list:
We are going to be inserting (adding) a new node at index 1.
To add a new node (represented by a purple node with value 9) at index 1 in the linked list, we would have to traverse the linked list to reach index 1 and then break the existing link between index 0 and index 1.
Then we would have to create a new link that accommodates the new node. I think of it like rewiring components in an electrical circuit.
After relinking, our new node will be inserted in the linked list at index 1, while the node previously at index 1 will now be at index 2. This concludes the addition operation.
Code
Now that we are able to visualize what happens during the addition operation, creating the code for it is going to be relatively simpler.
//implementing nth index addition function in doubly linked lists
class LinkedList {
constructor(){
this.head = this.tail = null
}
nthInsertion(value,index){
let currentIndex = 0;
let currentNode = this.head;
while(currentNode){
if(currentIndex === index){
let oldNode = currentNode //node with value 3
let oldNodePrev = currentNode.prev //node with value 1
currentNode = new Node(value) //purple node with value 9
oldNodePrev.next = currentNode
oldNode.prev = currentNode
currentNode.next = oldNode
currentNode.prev = oldNodePrev
return currentNode
}
else{
currentIndex++
currentNode = currentNode.next
}
return null //if index invalid
}
}
}
class Node {
constructor(value, prev, next){
this.value = value
this.prev = prev || null //default value of null
this.next = next || null //default value of null
}
}
Conclusion
Whether you're appending a node to the end of a linked list, inserting a node at a specific position, or prepending a node to the beginning of a linked list, understanding the mechanics of adding nodes is vital. With a solid understanding of adding nodes to a linked list, you can easily manipulate the list to suit your needs and build more complex data structures as well. In the upcoming articles, I will be diving into other types of operations, like delete and search operations, that can be performed on linked lists.