JavaScript program to insert nodes into linked list

A linked list is a data structure with different lengths, and any node can be deleted or added to the linked list. In this tutorial, we will implement a complete program for inserting nodes in a linked list with space and time complexity. Let us first understand the problem statement.

Problem Introduction

In the given problem, we are given a linked list and since we can change the size of the linked list by adding or removing nodes in the linked list, we will add or insert nodes in the linked list.

In a linked list, we can add new nodes at three different locations: the front node, after the last node, and in the middle of the linked list. For example, the given linked list is -

1 -> 2 -> 3 -> 4 -> 5 -> null, we have to add a random node with value 9. Therefore, there are many situations where nodes need to be added, such as -

• Add node at the beginning - 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

• Add node in the middle - 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null

• Add node at the end - 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> null

Let’s look at ways to achieve the following tasks -

Add node at the beginning of the linked list

Example

To add a node at the beginning of the linked list, we must create a new node and pass the head of the linked list to the new node as the next node, then move the head to the new node and add the new node node to the beginning of the linked list.

// creating the linked list node
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data){
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}
function add(data) {
   var new_node = new Node(data);
   new_node.next = head;
   return new_node;
}

var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)

head = add(7);
var data = 0;
while(head != null) {
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding a node at starting: ")
console.log(data + "null")

The time complexity of the above code is O(1), because we only need to move a pointer, and no additional space is used, making the space complexity O(1).

Add node in the middle of the linked list

Example

To add a node in the middle of a linked list, we have to create a new node and pass that node before we can add the new node of the linked list as the next node of the new node, which will add the new node node to the linked list in the middle.

// creating the linked list node
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}
function add(data,head) {
   var new_node = new Node(data);
   var temp = head;
   while(temp.value != 3) {
      temp  = temp.next;
   }
   new_node.next = temp.next;
   temp.next = new_node;
   return head;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
head = add(7,head);
var data = 0;
while(head != null) {
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding node in middle:")
console.log(data + "null")

The time complexity of the above code is O(N) because we have to move to the node where a new node needs to be added. The space complexity of the above process is O(1) since we are not using any extra space.

Add node at the end of the linked list

Example

To add a node at the end of the linked list, we must create a new node and add the node after the tail node and move the tail node to the next node.

// creating the linked list node
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
   }

function add(data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next
   return tail;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)

tail = add(7);
var data = 0;
while(head != null){
   data = data + head.value + " -> ";
   head = head.next;
}
console.log("Linked List after adding a node at the end: ")
console.log(data + "null")

The time complexity of the above code is O(1), because we only need to move a pointer, and no additional space is used, making the space complexity O(1).

in conclusion

In the above tutorial, we learned how to add a new node to an existing linked list in three possible ways. We've seen correct code with explanations and time and space complexities. Adding a node in the middle of the linked list takes O(N) time, while for the other two cases its time complexity is O(1), and for all three possibilities the space complexity is O(1).

The above is the detailed content of JavaScript program to insert nodes into linked list. For more information, please follow other related articles on the PHP Chinese website!