CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Program to insert a new node at the middle of the singly linked listExplanationIn this program, we will create a singly linked list and add a new node at the middle of the list. To accomplish this task, we will calculate the size of the list and divide it by 2 to get the midpoint of the list where the new node needs to be inserted. Consider the above diagram; node 1 represents the head of the original list. Let node New is the new node which needs to be added at the middle of the list. First, we calculate size which in this case is 4. So, to get the midpoint, we divide it by 2 and store it in a variable count. Node current will point to head. First, we iterate through the list till current points to mid position. Define another node temp which point to node next to current. Insert the New node between current and temp. Algorithm
SolutionPython#Represent a node of the singly linked list class Node: def __init__(self,data): self.data = data; self.next = None; class InsertMid: #Represent the head and tail of the singly linked list def __init__(self): self.head = None; self.tail = None; self.size = 0; #addNode() will add a new node to the list def addNode(self, data): #Create a new node newNode = Node(data); #Checks if the list is empty if(self.head == None): #If list is empty, both head and tail will point to new node self.head = newNode; self.tail = newNode; else: #newNode will be added after tail such that tail's next will point to newNode self.tail.next = newNode; #newNode will become new tail of the list self.tail = newNode; #Size will count the number of nodes present in the list self.size = self.size + 1; #This function will add the new node at the middle of the list. def addInMid(self, data): #Create a new node newNode = Node(data); #Checks if the list is empty if(self.head == None): #If list is empty, both head and tail would point to new node self.head = newNode; self.tail = newNode; else: #Store the mid position of the list count = (self.size//2) if(self.size % 2 == 0) else ((self.size+1)//2); #Node temp will point to head temp = self.head; current = None; #Traverse through the list till the middle of the list is reached for i in range(0, count): #Node current will point to temp current = temp; #Node temp will point to node next to it. temp = temp.next; #current will point to new node current.next = newNode; #new node will point to temp newNode.next = temp; self.size = self.size + 1; #display() will display all the nodes present in the list def display(self): #Node current will point to head current = self.head; if(self.head == None): print("List is empty"); return; while(current != None): #Prints each node by incrementing pointer print(current.data) current = current.next; sList = InsertMid(); #Adds data to the list sList.addNode(1); sList.addNode(2); print("Original list: "); sList.display(); #Inserting node '3' in the middle sList.addInMid(3); print( "Updated List: "); sList.display(); #Inserting node '4' in the middle sList.addInMid(4); print("Updated List: "); sList.display(); Output: Original list: 1 2 Updated List: 1 3 2 Updated List: 1 3 4 2 C#include <stdio.h> //Represent a node of the singly linked list struct node{ int data; struct node *next; }; int size; //Represent the head and tail of the singly linked list struct node *head, *tail = NULL; //addNode() will add a new node to the list void addNode(int data) { //Create a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); newNode>data = data; newNode>next = NULL; //Checks if the list is empty if(head == NULL) { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail>next = newNode; //newNode will become new tail of the list tail = newNode; } //Size will count the number of nodes present in the list size++; } //This function will add the new node at the middle of the list. void addInMid(int data){ //Create a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); newNode>data = data; newNode>next = NULL; //Checks if the list is empty if(head == NULL) { //If list is empty, both head and tail would point to new node head = newNode; tail = newNode; } else { struct node *temp, *current; //Store the mid position of the list int count = (size % 2 == 0) ? (size/2) : ((size+1)/2); //Node temp will point to head temp = head; current = NULL; //Traverse through the list till the middle of the list is reached for(int i = 0; i < count; i++) { //Node current will point to temp current = temp; //Node temp will point to node next to it. temp = temp>next; } //current will point to new node current>next = newNode; //new node will point to temp newNode>next = temp; } size++; } //display() will display all the nodes present in the list void display() { //Node current will point to head struct node *current = head; if(head == NULL) { printf("List is empty\n"); return; } while(current != NULL) { //Prints each node by incrementing pointer printf("%d ", current>data); current = current>next; } printf("\n"); } int main() { //Adds data to the list addNode(1); addNode(2); printf("Original list: \n"); display(); //Inserting node '3' in the middle addInMid(3); printf( "Updated List: \n"); display(); //Inserting node '4' in the middle addInMid(4); printf("Updated List: \n"); display(); return 0; } Output: Original list: 1 2 Updated List: 1 3 2 Updated List: 1 3 4 2 JAVApublic class InsertMid { //Represent a node of the singly linked list class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } public int size; //Represent the head and tail of the singly linked list public Node head = null; public Node tail = null; //addNode() will add a new node to the list public void addNode(int data) { //Create a new node Node newNode = new Node(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail.next = newNode; //newNode will become new tail of the list tail = newNode; } //Size will count the number of nodes present in the list size++; } //This function will add the new node at the middle of the list. public void addInMid(int data){ //Create a new node Node newNode = new Node(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail would point to new node head = newNode; tail = newNode; } else { Node temp, current; //Store the mid position of the list int count = (size % 2 == 0) ? (size/2) : ((size+1)/2); //Node temp will point to head temp = head; current = null; //Traverse through the list till the middle of the list is reached for(int i = 0; i < count; i++) { //Node current will point to temp current = temp; //Node temp will point to node next to it. temp = temp.next; } //current will point to new node current.next = newNode; //new node will point to temp newNode.next = temp; } size++; } //display() will display all the nodes present in the list public void display() { //Node current will point to head Node current = head; if(head == null) { System.out.println("List is empty"); return; } while(current != null) { //Prints each node by incrementing pointer System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { InsertMid sList = new InsertMid(); //Adds data to the list sList.addNode(1); sList.addNode(2); System.out.println("Original list: "); sList.display(); //Inserting node '3' in the middle sList.addInMid(3); System.out.println( "Updated List: "); sList.display(); //Inserting node '4' in the middle sList.addInMid(4); System.out.println("Updated List: "); sList.display(); } } Output: Original list: 1 2 Updated List: 1 3 2 Updated List: 1 3 4 2 C#using System; public class CreateList { //Represent a node of the singly linked list public class Node<T>{ public T data; public Node<T> next; public Node(T value) { data = value; next = null; } } public class InsertMid<T>{ public int size; //Represent the head and tail of the singly linked list public Node<T> head = null; public Node<T> tail = null; //addNode() will add a new node to the list public void addNode(T data) { //Create a new node Node<T> newNode = new Node<T>(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail.next = newNode; //newNode will become new tail of the list tail = newNode; } //Size will count the number of nodes present in the list size++; } //This function will add the new node at the middle of the list. public void addInMid(T data){ //Create a new node Node<T> newNode = new Node<T>(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail would point to new node head = newNode; tail = newNode; } else { Node<T> temp, current; //Store the mid position of the list int count = (size % 2 == 0) ? (size/2) : ((size+1)/2); //Node temp will point to head temp = head; current = null; //Traverse through the list till the middle of the list is reached for(int i = 0; i < count; i++) { //Node current will point to temp current = temp; //Node temp will point to node next to it. temp = temp.next; } //current will point to new node current.next = newNode; //new node will point to temp newNode.next = temp; } size++; } //display() will display all the nodes present in the list public void display() { //Node current will point to head Node<T> current = head; if(head == null) { Console.WriteLine("List is empty"); return; } while(current != null) { //Prints each node by incrementing pointer Console.Write(current.data + " "); current = current.next; } Console.WriteLine(); } } public static void Main() { InsertMid<int> sList = new InsertMid<int>(); //Adds data to the list sList.addNode(1); sList.addNode(2); Console.WriteLine("Original list: "); sList.display(); //Inserting node '3' in the middle sList.addInMid(3); Console.WriteLine( "Updated List: "); sList.display(); //Inserting node '4' in the middle sList.addInMid(4); Console.WriteLine("Updated List: "); sList.display(); } } Output: Original list: 1 2 Updated List: 1 3 2 Updated List: 1 3 4 2 PHP<!DOCTYPE html> <html> <body> <?php //Represent a node of singly linked list class Node{ public $data; public $next; function __construct($data){ $this>data = $data; $this>next = NULL; } } class InsertMid{ //Represent the head and tail of the singly linked list public $head; public $tail; function __construct(){ $this>head = NULL; $this>tail = NULL; $this>size = 0; } //addNode() will add a new node to the list function addNode($data) { //Create a new node $newNode = new Node($data); //Checks if the list is empty if($this>head == null) { //If list is empty, both head and tail will point to new node $this>head = $newNode; $this>tail = $newNode; } else { //newNode will be added after tail such that tail's next will point to newNode $this>tail>next = $newNode; //newNode will become new tail of the list $this>tail = $newNode; } //Size will count the number of nodes present in the list $this>size++; } //This function will add the new node at the middle of the list. function addInMid($data){ //Create a new node $newNode = new Node($data); //Checks if the list is empty if($this>head == null) { //If list is empty, both head and tail would point to new node $this>head = $newNode; $this>tail = $newNode; } else { //Store the mid position of the list $count = ($this>size % 2 == 0) ? ($this>size/2) : (($this>size+1)/2); //Node temp will point to head $temp = $this>head; $current = null; //Traverse through the list till the middle of the list is reached for($i = 0; $i < $count; $i++) { //Node current will point to temp $current = $temp; //Node temp will point to node next to it. $temp = $temp>next; } //current will point to new node $current>next = $newNode; //new node will point to temp $newNode>next = $temp; } $this>size++; } //display() will display all the nodes present in the list function display() { //Node current will point to head $current = $this>head; if($this>head == NULL) { print("List is empty <br>"); return; } while($current != NULL) { //Prints each node by incrementing pointer print($current>data . " "); $current = $current>next; } print("<br>"); } } $sList = new InsertMid(); //Adds data to the list $sList>addNode(1); $sList>addNode(2); print("Original list: <br>"); $sList>display(); //Inserting node '3' in the middle $sList>addInMid(3); print( "Updated List: <br>"); $sList>display(); //Inserting node '4' in the middle $sList>addInMid(4); print("Updated List: <br>"); $sList>display(); ?> </body> </html> Output: Original list: 1 2 Updated List: 1 3 2 Updated List: 1 3 4 2
Next Topic#
