How to Insert a Node at a Specific Position in a Linked List in JavaScript
“Linked lists” are linear data structures that contain the data in individual objects referred to as nodes and store data in a different way. These linked lists can be singly, doubly, or circular. Inserting a node at a specific position is a common approach that enables the developer to modify the list dynamically. This functionality is made convenient with the help of the Linked list built-in operations/methods.
Contents Overview
- What is a Linked List in JavaScript?
- What is the Need for Linked List in JavaScript?
- Operations on Linked List
- Algorithm For Inserting a Node at Specific Position in Linked List
- How to Insert a Node at a Specific Position in a Linked List in JavaScript?
- Approach 1: Inserting a Node at a Specific Position in a Linked List Using User-defined Functions in JavaScript
- Approach 2: Inserting a Node at a Specific Position in a Linked List Using List Operations
- Conclusion
What is a Linked List in JavaScript?
A “Linked List” corresponds to a data structure that stores a collection of data(ordered) that can be invoked sequentially. The data in the linked list i.e., node comprises information and a pointer. Also, the data in the linked list is not contained at contagious memory locations, unlike the array.
What is the Need for Linked List in JavaScript?
The following factors contribute to making the linked list a favorable option for the developers to store the data:
- Dynamic: The linked lists are dynamic in nature as these can grow or shrink during code execution.
- Memory Optimization: These lists efficiently utilize memory and don’t need to allocate the memory in advance.
- Efficient Insertion and Deletion: The linked lists insert and delete the elements efficiently at any position in the list.
Operations on Linked List
Following are the operations/methods that are commonly applied on the LinkedList:
insertAt(index): This method inserts the node at the target index.
removeFrom(index): This method removes the node from the target index.
appendNode(node): This method appends the target node in the linked list.
getNode(index): It retrieves the node from the given index.
reverse(): It reverses the entire list.
clear(): This method nullifies the linked list by making the head point null.
Algorithm For Inserting a Node at Specific Position in Linked List
data = 15
position = 2
In the above demonstration, “data” is the node to be inserted, and “position” indicates the index in the list at which the node is to be added.
Output
How to Insert a Node at a Specific Position in a Linked List in JavaScript?
A node can be inserted at a specific index position in the linked list via the following approaches:
- Using “User-defined Functions”.
- Using “List Operations”.
Approach 1: Inserting a Node at a Specific Position in a Linked List Using User-defined Functions in JavaScript
This example inserts multiple nodes at a target index position utilizing a single class and multiple user-defined functions for fetching the data, inserting and displaying the nodes:
class NodeSpecific {
constructor(value) {
this.data = value;
this.nextNode = null;
}}
function fetchNode(data) {
return new NodeSpecific(data);
}
function InsertPos(hdNode , pos , data) {
head = hdNode;
if (pos < 1)
console.log("Inappropriate Index");
if (pos == 1) {
newNode = new NodeSpecific(data);
newNode.nextNode = hdNode;
head = newNode;
}
else {
while (pos-- != 0) {
if (pos == 1) {
newNode = fetchNode(data);
newNode.nextNode = hdNode.nextNode;
hdNode.nextNode = newNode;
break;
}
hdNode = hdNode.nextNode;
}
if (pos != 1)
console.log("Position out of range");
}
return head;
}
function displayList( node) {
while (node != null) {
console.log(node.data);
node = node.nextNode;
}
console.log("\n");
}
head = fetchNode(10);
head.nextNode = fetchNode(20);
head.nextNode.nextNode = fetchNode(30);
head.nextNode.nextNode.nextNode = fetchNode(40);
console.log("Default Linked List Before Insertion -> ");
displayList(head);
var data = 2, pos = 1;
head = InsertPos(head, pos, data);
console.log("Linked list after" + " insertion of 2 at index position 0: ");
displayList(head);
data = 4;
pos = 3;
head = InsertPos(head, pos, data);
console.log("Linked list after" + " insertion of 4 at index position 2: ");
displayList(head);
data = 8;
pos = 7;
head = InsertPos(head, pos, data);
console.log("Linked list after" + " insertion of 8 at index position 6: ");
displayList(head);
</script>
According to the above block of code, follow the following steps:
- Declare the class “NodeSpecific” to insert the required data.
- After that, define the function “fetchNode()” to create and retrieve the node.
- Now, the defined “InsertPos()” function inserts the node at the target index based on the specified parameters.
- Deal with the invalid index condition in the first “if” statement.
- Now, if the index position is “1”, a new node is allocated infront of the head node by creating a class instance.
- In the “else” condition, invoke the “fetchNode()” function to include the node at the desired index.
- Also, make the new node point to the old node at the same index position.
- Now, declare the “displayList()” function to print the nodes provided that they are not null.
- Access the “fetchNode()” function to include the nodes one after another with the stated values.
- Lastly, invoke the “InsertPos()” and “displayList()” functions to insert and display the nodes at the specific index positions and defined data represented by “pos” and “data”, respectively.
Output(Default Linked List)
First Insertion
Second Insertion
Third Insertion
From these outcomes, it can be verified that the insertion at the target indexes is done appropriately.
Approach 2: Inserting a Node at a Specific Position in a Linked List Using List Operations
In this demonstration, the nodes can be inserted at specific positions by using multiple classes and built-in operations on the linked lists:
class NodeSpecific {
constructor(dt) {
this.dt = dt
this.next = null
}}
class linkedList {
constructor(Head = null) {
this.Head = Head
}
add(newNode){
let nd = this.Head;
if(nd==null){
this.Head = newNode;
return;
}
while (nd.next) {
nd = nd.next;
}
nd.next = newNode;
}
insertAt(ind, newNode){
let nd = this.Head;
if(ind==0) {
newNode.next = nd;
this.head = newNode;
return;
}
while(--ind){
if(nd.next!==null)
nd = nd.next;
else
throw Error("Index Out of Bound");
}
let tempVal = nd.next;
nd.next = newNode;
newNode.next = tempVal;
}
showList(){
let nd = this.Head;
var str = ""
while (nd) {
str += nd.dt + "->";
nd = nd.next;
}
str += "NULL"
console.log(str);
}
}
let list = new linkedList();
list.add(new NodeSpecific(10));
list.add(new NodeSpecific(20));
list.add(new NodeSpecific(30));
list.add(new NodeSpecific(40));
list.add(new NodeSpecific(50));
console.log("Default Linked List Values -> ");
list.showList();
console.log("Inserting Values ->");
console.log("Insert 2 at index position 1:")
list.insertAt(1, new NodeSpecific(2));
list.showList();
console.log("Insert 4 at index position 2:")
list.insertAt(2, new NodeSpecific(4));
list.showList();
console.log("Insert 8 at index position 5:")
list.insertAt(5, new NodeSpecific(8));
list.showList();
</script>
The code explanation is as follows:
- Declare the class “NodeSpecific” comprising the constructor to insert the nodes.
- Now, apply the Linked list operation “insertAt()” to insert the new node at the passed index.
- Also, handle the “index out of bound” exception if the limit is exceeded by the index.
- Define the “showList()” function to display the list.
- Now, create an instance of the latter defined class i.e., “linkedList” to contain the nodes.
- Create multiple class instances to insert the default nodes comprising the given values and display the list.
- Finally, invoke the “insertAt()” method to insert the values passed as the class constructor parameter at the target indexes in the list.
Output
From this outcome, it can be analyzed that the nodes are inserted at the specific positions accordingly.
Conclusion
The node can be inserted at a specific index position in a Linked List using the “nextNode” property, user-defined functions, or applying the Linked List operational methods. This can be done by using single or multiple classes and user-defined functions. This approach assists in chaining and updating the linked list appropriately.
Source: linuxhint.com