How do you insert a node after a position temperature in singly linked list?

Insert a node at a specific position in a linked list

Given a singly linked list, a position and an element, the task is to write a program to insert that element in a linked list at a given position.

Nội dung chính Show

Insert a node at a specific position in a linked list
Linked List | Set 2 (Inserting a node)
Example in C:
inserting a node at the end of a linked list
Linked List Operations: Traverse, Insert and Delete
Things to Remember about Linked List
Video liên quan

Examples:

Input: 3->5->8->10, data = 2, position = 2 Output: 3->2->5->8->10 Input: 3->5->8->10, data = 11, position = 5 Output: 3->5->8->10->11

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: To insert a given data at a specified position, the below algorithm is to be followed:

Traverse the Linked list upto position-1 nodes.
Once all the position-1 nodes are traversed, allocate memory and the given data to the new node.
Point the next pointer of the new node to the next of current node.
Point the next pointer of current node to the new node.

Below is the implementation of the above algorithm.

C++

// C++ program for insertion in a single linked
// list at a specified position
#include 

using namespace std;
// A linked list Node

struct Node {

int data;

struct Node* next;
};
// Size of linked list

int size = 0;
// function to create and return a Node

Node* getNode(int data)
{

// allocating space

Node* newNode = new Node();

// inserting the required data

newNode->data = data;

newNode->next = NULL;

return newNode;
}
// function to insert a Node at required position

void insertPos(Node** current, int pos, int data)
{

// This condition to check whether the

// position given is valid or not.

if (pos < 1 || pos > size + 1)

cout << "Invalid position!" << endl;

else {

// Keep looping until the pos is zero

while (pos--) {

if (pos == 0) {

// adding Node at required position

Node* temp = getNode(data);

// Making the new Node to point to

// the old Node at the same position

temp->next = *current;

// Changing the pointer of the Node previous

// to the old Node to point to the new Node

*current = temp;

}

else

// Assign double pointer variable to point to the

// pointer pointing to the address of next Node

current = &(*current)->next;

}

size++;

}
}
// This function prints contents 
// of the linked list 

void printList(struct Node* head)
{

while (head != NULL) {

cout << " " << head->data;

head = head->next;

}

cout << endl;
}
// Driver Code

int main()
{

// Creating the list 3->5->8->10

Node* head = NULL;

head = getNode(3);

head->next = getNode(5);

head->next->next = getNode(8);

head->next->next->next = getNode(10);

size = 4;

cout << "Linked list before insertion: ";

printList(head);

int data = 12, pos = 3;

insertPos(&head, pos, data);

cout << "Linked list after insertion of 12 at position 3: ";

printList(head);

// front of the linked list

data = 1, pos = 1;

insertPos(&head, pos, data);

cout << "Linked list after insertion of 1 at position 1: ";

printList(head);

// insertion at end of the linked list

data = 15, pos = 7;

insertPos(&head, pos, data);

cout << "Linked list after insertion of 15 at position 7: ";

printList(head);

return 0;
}

Java

// Java program for insertion in a single linked 
// list at a specified position 

class GFG {

// A linked list Node

static class Node {

public int data;

public Node nextNode;

// inserting the required data

public Node(int data) {

this.data = data;

}

}

// function to create and return a Node

static Node GetNode(int data) {

return new Node(data);

}

// function to insert a Node at required position

static Node InsertPos(Node headNode, int position, int data) {

Node head = headNode;

if (position < 1)

System.out.print("Invalid position");

// if position is 1 then new node is

// set infornt of head node

// head node is changing.

if (position == 1) {

Node newNode = new Node(data);

newNode.nextNode = headNode;

head = newNode;

} else {

while (position-- != 0) {

if (position == 1) {

// adding Node at required position

Node newNode = GetNode(data);

// Making the new Node to point to

// the old Node at the same position

newNode.nextNode = headNode.nextNode;

// Replacing current with new Node

// to the old Node to point to the new Node

headNode.nextNode = newNode;

break;

}

headNode = headNode.nextNode;

}

if (position != 1)

System.out.print("Position out of range");

}

return head;

}

static void PrintList(Node node) {

while (node != null) {

System.out.print(node.data);

node = node.nextNode;

if (node != null)

System.out.print(",");

}

System.out.println();

}

// Driver code

public static void main(String[] args) {

Node head = GetNode(3);

head.nextNode = GetNode(5);

head.nextNode.nextNode = GetNode(8);

head.nextNode.nextNode.nextNode = GetNode(10);

System.out.print("Linked list before insertion: ");

PrintList(head);

int data = 12, pos = 3;

head = InsertPos(head, pos, data);

System.out.print("Linked list after" + " insertion of 12 at position 3: ");

PrintList(head);

// front of the linked list

data = 1;

pos = 1;

head = InsertPos(head, pos, data);

System.out.print("Linked list after" + "insertion of 1 at position 1: ");

PrintList(head);

// insertion at end of the linked list

data = 15;

pos = 7;

head = InsertPos(head, pos, data);

System.out.print("Linked list after" + " insertion of 15 at position 7: ");

PrintList(head);

}
}
// This code is contributed by Rajput-Ji

Python3

# Python3 program for insertion in a single linked
# list at a specified position

# A linked list Node

class Node:

def __init__(self, data):

self.data = data

self.nextNode = None

# function to create and return a Node

def getNode(data):

# allocating space

newNode = Node(data)

return newNode;
# function to insert a Node at required position

def insertPos(headNode, position, data):

head = headNode

# This condition to check whether the

# position given is valid or not.

if (position < 1):

print("Invalid position!")

if position == 1:

newNode = Node(data)

newNode.nextNode = headNode

head = newNode

else:

# Keep looping until the position is zero

while (position != 0):

position -= 1

if (position == 1):

# adding Node at required position

newNode = getNode(data)

# Making the new Node to point to

# the old Node at the same position

newNode.nextNode = headNode.nextNode

# Replacing headNode with new Node

# to the old Node to point to the new Node

headNode.nextNode = newNode

break

headNode = headNode.nextNode

if headNode == None:

break

if position != 1:

print("position out of range")

return head

# This function prints contents 
# of the linked list 

def printList(head):

while (head != None):

print(' ' + str(head.data), end = '')

head = head.nextNode;

print()

# Driver Code

if __name__=='__main__':

# Creating the list 3.5.8.10

head = getNode(3);

head.nextNode = getNode(5);

head.nextNode.nextNode = getNode(8);

head.nextNode.nextNode.nextNode = getNode(10);

print("Linked list before insertion: ", end='')

printList(head);

data = 12

position = 3;

head = insertPos(head, position, data);

print("Linked list after insertion of 12 at position 3: ", end = '')

printList(head);

# front of the linked list

data = 1

position = 1;

head = insertPos(head, position, data);

print("Linked list after insertion of 1 at position 1: ", end = '')

printList(head);

# insertion at end of the linked list

data = 15

position = 7;

head = insertPos(head, position, data);

print("Linked list after insertion of 15 at position 7: ", end='')

printList(head);
# This code iscontributed by rutvik_56

// C# program for insertion in a single linked 
// list at a specified position 

using System;

namespace InsertIntoLinkedList
{

class Program

{

// A linked list Node

private class Node

{

public int data;

public Node nextNode;

// inserting the required data

public Node(int data) => this.data = data;

}

// function to create and return a Node

static Node GetNode(int data) => new Node(data);

// function to insert a Node at required position

static Node InsertPos(Node headNode,

int position, int data)

{

var head = headNode;

if (position < 1)

Console.WriteLine("Invalid position");

//if position is 1 then new node is

// set infornt of head node

//head node is changing.

if (position == 1)

{

var newNode = new Node(data);

newNode.nextNode = headNode;

head = newNode;

}

else

{

while (position-- != 0)

{

if (position == 1)

{

// adding Node at required position

Node newNode = GetNode(data);

// Making the new Node to point to

// the old Node at the same position

newNode.nextNode = headNode.nextNode;

// Replacing current with new Node

// to the old Node to point to the new Node

headNode.nextNode = newNode;

break;

}

headNode = headNode.nextNode;

}

if (position != 1)

Console.WriteLine("Position out of range");

}

return head;

}

static void PrintList(Node node)

{

while (node != null)

{

Console.Write(node.data);

node = node.nextNode;

if(node != null)

Console.Write(",");

}

Console.WriteLine();

}

// Driver code

static void Main(string[] args)

{

var head = GetNode(3);

head.nextNode = GetNode(5);

head.nextNode.nextNode = GetNode(8);

head.nextNode.nextNode.nextNode = GetNode(10);

Console.WriteLine("Linked list before insertion: ");

PrintList(head);

int data = 12, pos = 3;

head = InsertPos(head, pos, data);

Console.WriteLine("Linked list after" +

" insertion of 12 at position 3: ");

PrintList(head);

// front of the linked list

data = 1; pos = 1;

head = InsertPos(head, pos, data);

Console.WriteLine("Linked list after" +

"insertion of 1 at position 1: ");

PrintList(head);

// insertion at end of the linked list

data = 15; pos = 7;

head = InsertPos(head, pos, data);

Console.WriteLine("Linked list after" +

" insertion of 15 at position 7: ");

PrintList(head);

}

}
}
// This code is contributed by dhirucoool

Javascript

Time Complexity: O(N)

How do you insert a node after a position temperature in singly linked list?

Article Tags :

Data Structures

Linked List

cpp-double-pointer

Practice Tags :

Data Structures

Linked List

Read Full Article

Linked List | Set 2 (Inserting a node)

We have introduced Linked Lists in the previous post. We also created a simple linked list with 3 nodes and discussed linked list traversal.
All programs discussed in this post consider the following representations of linked list.

C++

// A linked list node 

class Node
{ 

public:

int data;

Node *next;
}; 
// This code is contributed by rathbhupendra

// A linked list node

struct Node
{

int data;

struct Node *next;
};

Java

// Linked List Class

class LinkedList
{

Node head; // head of list

/* Node Class */

class Node

{

int data;

Node next;

// Constructor to create a new node

Node(int d) {data = d; next = null; }

}
}

Python

# Node class

class Node:

# Function to initialize the node object

def __init__(self, data):

self.data = data # Assign data

self.next = None # Initialize next as null
# Linked List class

class LinkedList:

# Function to initialize the Linked List object

def __init__(self):

self.head = None

/* Linked list Node*/

public class Node
{

public int data;

public Node next;

public Node(int d) {data = d; next = null; }
}

Javascript

In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1) At the front of the linked list
2) After a given node.
3) At the end of the linked list.

Algorithm:

STEP 1:
IF PTR = NULL
WRITE OVERFLOW
GOTO STEP 12
END OF IF
STEP 2: SET NEW_NODE = PTR
STEP 3: NEW_NODE → DATA = VAL
STEP 4: SET TEMP = HEAD
STEP 5: SET I = 0
STEP 6: REPEAT STEP 5 AND 6 UNTIL I
STEP 7: TEMP = TEMP → NEXT
STEP 8:IF TEMP = NULL
WRITE “DESIRED NODE NOT PRESENT”
GOTO STEP 12
END OF IF
END OF LOOP
STEP 9: PTR → NEXT = TEMP → NEXT
STEP 10: TEMP → NEXT = PTR
STEP 11: SET PTR = NEW_NODE
STEP 12: EXIT

Example in C:

#include<stdio.h> #include<stdlib.h> void insertNode(int); void createNode(int); struct node { int data; struct node *next; }; struct node *head; void main () { int choice,item,loc; do { printf("\nEnter the element to insert:\n"); scanf("%d",&item); if(head == NULL) { createNode(item); } else { insertNode(item); } printf("\nPress 0 to insert more.\n"); scanf("%d",&choice); }while(choice == 0); } void createNode(int item) { struct node *ptr = (struct node *)malloc(sizeof(struct node *)); if(ptr == NULL) { printf("\nOVERFLOW\n"); } else { ptr->data = item; ptr->next = head; head = ptr; printf("\nNode inserted successfully!!\n"); } } void insertNode(int item) { struct node *ptr = (struct node *) malloc (sizeof(struct node)); struct node *temp; int i,loc; if(ptr == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter the location:\n"); scanf("%d",&loc); ptr->data = item; temp=head; for(i=0;i<loc;i++) { temp = temp->next; if(temp == NULL) { printf("\nElement can't be inserted.\n"); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf("\nNode inserted successfully!!"); } }

#include #include void insertNode(int); void createNode(int); struct node { int data; struct node *next; }; struct node *head; void main () { int choice,item,loc; do { printf("\nEnter the element to insert:\n"); scanf("%d",&item); if(head == NULL) { createNode(item); } else { insertNode(item); } printf("\nPress 0 to insert more.\n"); scanf("%d",&choice); }while(choice == 0); } void createNode(int item) { struct node *ptr = (struct node *)malloc(sizeof(struct node *)); if(ptr == NULL) { printf("\nOVERFLOW\n"); } else { ptr->data = item; ptr->next = head; head = ptr; printf("\nNode inserted successfully!!\n"); } } void insertNode(int item) { struct node *ptr = (struct node *) malloc (sizeof(struct node)); struct node *temp; int i,loc; if(ptr == NULL) { printf("\nOVERFLOW"); } else { printf("\nEnter the location:\n"); scanf("%d",&loc); ptr->data = item; temp=head; for(i=0;inext; if(temp == NULL) { printf("\nElement can't be inserted.\n"); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf("\nNode inserted successfully!!"); } }

Output

Please Share

inserting a node at the end of a linked list

The new node will be added at the end of the linked list.

Linked List Operations: Traverse, Insert and Delete

In this tutorial, you will learn different operations on a linked list. Also, you will find implementation of linked list operations in C/C++, Python and Java.

There are various linked list operations that allow us to perform different actions on linked lists. For example, the insertion operation adds a new element to the linked list.

Here's a list of basic linked list operations that we will cover in this article.

Traversal - access each element of the linked list
Insertion - adds a new element to the linked list
Deletion - removes the existing elements
Search - find a node in the linked list
Sort - sort the nodes of the linked list

Before you learn about linked list operations in detail, make sure to know about Linked List first.

Things to Remember about Linked List

head points to the first node of the linked list
next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.

In all of the examples, we will assume that the linked list has three nodes 1 --->2 --->3 with node structure as below:

struct node { int data; struct node *next; };