Linked list

Insert a node at a specific position in a linked list

Aman Sharma

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a singly linked list and a position. We have to insert a node at that specific position.

Problem Statement Understanding

The problem is quite simple. We just have to insert a node at a specific position in the given linked list.

Suppose the given list is 1 → 2 → 3→ 4 → 5, position = 2, and the data to be inserted is 6.

  • According to the problem statement, we need to insert a node with value = 6 at 2nd position in the linked list.
  • So, after adding the node with value = 6 at 2nd position in the given linked list, our resultant list will be 1 → 6 → 2→ 3 → 4 → 5.

Now, I think from the above example, the problem statement is clear.

So, now the main question is how we should approach this problem? What is the first thing that comes to mind?

  • List traversal, right? Yes. We are going to use list traversal to solve this problem.

Before moving further to the approach section, try to think of the approach by yourself.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach

Our approach is going to be pretty simple.

  • We will simply traverse till (position -1)th node and add the newnode just after that node. Well, how will this work? Let us take an example.
    • Suppose the list is 1 → 2 → 3, and we have to insert 4 at the 2nd position.
    • Now, we will traverse (position -1) = (2-1) = 1 node and after traversing 1 node, we will be standing at 1.
    • Now we will make 4 → next = 1 → next as we have to insert it after 1, and finally, 1 → next = 4 to link the nodes.
    • By doing the above steps, 4 will be added at that specific position, and our resultant linked list will be: 1 → 4 → 2 → 3.

We can get a clearer look of approach by looking at the dry run.

Algorithm

  • If the position where we are asked to insert pos is smaller than 1 or greater than the size of the list, it is invalid, and we will return.
  • Else, we will make variable curr and make it point to the head of the list.
  • Now we will run a for loop using curr to reach to the node at (pos-1)th position:
    • The for loop will be: for(int i=1;inext;}
    • After the termination of the above loop, curr will be standing at the (position - 1)th node.
    • As explained above, we will simply make newnode → next = curr → next and curr → next = newnode.
  • If the pos was equal to 1, we will make the head point to newnode as newnode will become the first node of the list.

Dry Run

Code Implementation

#include 
using namespace std;

// Node structure of a singly linked list node
struct Node {
    int data;
    struct Node* next;
};

int size = 0;

// Using this function we will be creating new nodes
Node* getNode(int data)
{
    Node* newNode = new Node();

    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Using this function we will insert the newnode at the specific position
void insertAtPosition(Node* head, int pos, int data)
{
    if (pos < 1 || pos > size + 1)
        cout << "Invalid position!" << endl;
    else {
        Node *curr=head;
        for(int i=1;inext;
        }
        Node* temp=getNode(data);
        temp->next=curr->next;
        curr->next=temp;
        if(pos=1)
        head=temp;
        size++;
    }
}

// Using this function we will print the linked list
void printList(struct Node* head)
{
    while (head != NULL) {
        cout << " " << head->data;
        head = head->next;
    }
    cout << endl;
}

// Driver function
int main()
{

    Node* head = NULL;
    head = getNode(1);
    head->next = getNode(2);
    head->next->next = getNode(3);
    head->next->next->next = getNode(4);
    head->next->next->next->next = getNode(5);

    size = 5;

    cout << "Linked list before insertion: ";
    printList(head);

    int data = 6, pos = 2;
    insertAtPosition(head, pos, data);
    cout << "Linked list after insertion of 6 at position 2: ";
    printList(head);
    
    return 0;
}


public class PrepBytes {
    // Structure of a singly linked list node
    static class Node {
        public int data;
        public Node nextNode;

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

        }
    }

    // Function to create a new node and return
    static Node GetNode(int data) {
        return new Node(data);
    }

    // Function to insert an element at a specified index
    static Node InsertAtPos(Node headNode, int position, int data) {
        Node head = headNode;
        if (position < 1)
            System.out.print("Invalid position");

        if (position == 1) {
            Node newNode = new Node(data);
            newNode.nextNode = headNode;
            head = newNode;
        } else {
            for(int i=1;i

						 

#include 
#include 

struct Node {
    int data;
    struct Node* next;
};
int size = 0;
// Using this function we will be creating new nodes
struct Node* getNode(int data)
{
   struct Node* newNode
= (struct Node*)malloc(
sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
// Using this function we will insert the newnode at the specific position
void insertAtPosition(struct Node* head, int pos, int data)
{
    if (pos < 1 || pos > size + 1)
        printf( "Invalid position!\n" );
    else {
       struct Node *curr=head;
        for(int i=1;inext;
        struct Node* temp=getNode(data);
        temp->next=curr->next;
        curr->next=temp;
        if(pos=1)
        head=temp;
        size++;
    }
}
// Using this function we will print the linked list
void printList(struct Node* head)
{
    while (head != NULL) {
        printf("%d ",head->data);
        head = head->next;
    }
    printf("\n");
}
// Driver function
int main()
{
    struct Node* head = NULL;
    head = getNode(1);
    head->next = getNode(2);
    head->next->next = getNode(3);
    head->next->next->next = getNode(4);
    head->next->next->next->next = getNode(5);
    size = 5;
    printf("Linked list before insertion: ");
    printList(head);
    int data = 6, pos = 2;
    insertAtPosition(head, pos, data);
    printf("Linked list after insertion of 6 at position 2: ");
    printList(head);
    
    return 0;
}

# 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):

	newNode = Node(data)
	return newNode

# function to insert a Node at required position
def insertPos(headNode, position, data):
	head = headNode
	
	if (position < 1):	
		print("Invalid position!")
	
	if position == 1:
		newNode = Node(data)
		newNode.nextNode = headNode
		head = newNode
			
	else:
	
		while (position != 0):		
			position -= 1

			if (position == 1):

				newNode = getNode(data)
				newNode.nextNode = headNode.nextNode
				headNode.nextNode = newNode
				break
			
			headNode = headNode.nextNode
			if headNode == None:
				break		
		if position != 1:
			print("position out of range")	
	return head
	
def printList(head):
	while (head != None):	
		print(' ' + str(head.data), end = '')
		head = head.nextNode
	print()
	
if __name__=='__main__':
	
	head = getNode(1)
	head.nextNode = getNode(2)
	head.nextNode.nextNode = getNode(3)
	head.nextNode.nextNode.nextNode = getNode(4)
	head.nextNode.nextNode.nextNode.nextNode = getNode(5)
	print("Linked list before insertion: ", end='')
	printList(head)
	data = 6
	position = 2
	head = insertPos(head, position, data)
	print("Linked list after insertion of 6 at position 2: ", end = '')
	printList(head)

Output:

Linked list before insertion: 1,2,3,4,5
Linked list after insertion of 6 at position 2: 1,6,2,3,4,5

Time Complexity: O(n), as list traversal is needed.
[forminator_quiz id="5757"]

So, in this article, we have tried to explain how to insert an element at a specific position in a linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

One thought on “Insert a node at a specific position in a linked list”

  1. Good day! Do you know if they make any plugins to help with Search Engine Optimization? Im trying to get my blog to rank for some targeted keywords but Im not seeing very good results. If you know of any please share. Appreciate it!

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post