Wap to insert an element at specific position of a linked list in python

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.

Table of Contents Show

Insert a node at a specific position in a linked list
Python Program For Inserting A Node In A Linked List
Program to insert new element into a linked list before the given position in Python
How to Insert a Node at a Specific Position in a Linked List
Linked List Operations: Traverse, Insert and Delete
Things to Remember about Linked List

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 <bits/stdc++.h>

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

<script>
// javascript program for insertion in a single linked 
// list at a specified position // A linked list Node

class Node {

// inserting the required data

constructor(val) {

this.data = val;

this.nextNode = null;

}

}

// function to create and return a Node

function GetNode(data) {

return new Node(data);

}

// function to insert a Node at required position

function InsertPos( headNode , position , data) {

head = headNode;

if (position < 1)

document.write("Invalid position");

// if position is 1 then new node is

// set infront of head node

// head node is changing.

if (position == 1) {

newNode = new Node(data);

newNode.nextNode = headNode;

head = newNode;

}

else

{

while (position-- != 0)

{

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 current with new Node

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

headNode.nextNode = newNode;

break;

}

headNode = headNode.nextNode;

}

if (position != 1)

document.write("Position out of range");

}

return head;

}

function PrintList( node) {

while (node != null) {

document.write(node.data);

node = node.nextNode;

if (node != null)

document.write(",");

}

document.write("<br/>");

}

// Driver code

head = GetNode(3);

head.nextNode = GetNode(5);

head.nextNode.nextNode = GetNode(8);

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

document.write("Linked list before insertion: ");

PrintList(head);

var data = 12, pos = 3;

head = InsertPos(head, pos, data);

document.write("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);

document.write("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);

document.write("Linked list after" + " insertion of 15 at position 7: ");

PrintList(head);
// This code is contributed by gauravrajput1.
</script>

Time Complexity: O(N)

Article Tags :

Data Structures

Linked List

cpp-double-pointer

Practice Tags :

Data Structures

Linked List

Read Full Article

Python Program For Inserting A Node In A Linked List

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.

Python

# Node class 

class Node:

# Function to initialize the

# node object

def __init__(self, data):

# Assign data

self.data = data

# Initialize next as null

self.next = None

# Linked List class 

class LinkedList:

# Function to initialize the

# Linked List object

def __init__(self):

self.head = None

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.

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Add a node at the front: (4 steps process)
The new node is always added before the head of the given Linked List. And newly added node becomes the new head of the Linked List. For example, if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25. Let us call the function that adds at the front of the list is push(). The push() must receive a pointer to the head pointer, because push must change the head pointer to point to the new node (See this)

Following are the 4 steps to add a node at the front.

Python

# This function is in LinkedList class 
# Function to insert a new node at 
# the beginning 

def push(self, new_data):

# 1 & 2: Allocate the Node &

# Put in the data

new_node = Node(new_data)

# 3. Make next of new Node as head

new_node.next = self.head

# 4. Move the head to point to new Node

self.head = new_node

Time complexity of push() is O(1) as it does a constant amount of work.
Add a node after a given node: (5 steps process)
We are given a pointer to a node, and the new node is inserted after the given node.

Python

# This function is in LinkedList class. 
# Inserts a new node after the given 
# prev_node. This method is defined 
# inside LinkedList class shown above 

def insertAfter(self, prev_node, new_data):

# 1. Check if the given prev_node exists

if prev_node is None:

print "The given previous node must in LinkedList."

return

# 2. Create new node &

# 3. Put in the data

new_node = Node(new_data)

# 4. Make next of new Node as next of prev_node

new_node.next = prev_node.next

# 5. make next of prev_node as new_node

prev_node.next = new_node

Time complexity of insertAfter() is O(1) as it does a constant amount of work.

Add a node at the end: (6 steps process)
The new node is always added after the last node of the given Linked List. For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.
Since a Linked List is typically represented by the head of it, we have to traverse the list till the end and then change the next to last node to a new node.

Following are the 6 steps to add node at the end.

Python

# This function is defined in Linked List 
# class appends a new node at the end. 
# This method is defined inside LinkedList 
# class shown above 

def append(self, new_data):

# 1. Create a new node

# 2. Put in the data

# 3. Set next as None

new_node = Node(new_data)

# 4. If the Linked List is empty, then

# make the new node as head

if self.head is None:

self.head = new_node

return

# 5. Else traverse till the last node

last = self.head

while (last.next):

last = last.next

# 6. Change the next of last node

last.next = new_node

Time complexity of append is O(n) where n is the number of nodes in the linked list. Since there is a loop from head to end, the function does O(n) work.
This method can also be optimized to work in O(1) by keeping an extra pointer to the tail of the linked list/

Following is a complete program that uses all of the above methods to create a linked list.

Python

# A complete working Python program to demonstrate all 
# insertion methods of linked list 

# Node class 

class Node:

# Function to initialize the

# node object

def __init__(self, data):

# Assign data

self.data = data

# Initialize next as null

self.next = None

# Linked List class contains a 
# Node object 

class LinkedList:

# Function to initialize head

def __init__(self):

self.head = None

# Functio to insert a new node at

# the beginning

def push(self, new_data):

# 1 & 2: Allocate the Node &

# Put in the data

new_node = Node(new_data)

# 3. Make next of new Node as head

new_node.next = self.head

# 4. Move the head to point to new Node

self.head = new_node

# This function is in LinkedList class.

# Inserts a new node after the given

# prev_node. This method is defined

# inside LinkedList class shown above

def insertAfter(self, prev_node, new_data):

# 1. Check if the given prev_node exists

if prev_node is None:

print "The given previous node must inLinkedList."

return

# 2. Create new node &

# Put in the data

new_node = Node(new_data)

# 4. Make next of new Node as next

# of prev_node

new_node.next = prev_node.next

# 5. make next of prev_node as new_node

prev_node.next = new_node

# This function is defined in Linked List class

# Appends a new node at the end. This method is

# defined inside LinkedList class shown above */

def append(self, new_data):

# 1. Create a new node

# 2. Put in the data

# 3. Set next as None

new_node = Node(new_data)

# 4. If the Linked List is empty, then make the

# new node as head

if self.head is None:

self.head = new_node

return

# 5. Else traverse till the last node

last = self.head

while (last.next):

last = last.next

# 6. Change the next of last node

last.next = new_node

# Utility function to print the

# linked list

def printList(self):

temp = self.head

while (temp):

print temp.data,

temp = temp.next

# Code execution starts here 

if __name__=='__main__':

# Start with the empty list

llist = LinkedList()

# Insert 6. So linked list

becomes 6->None

llist.append(6)

# Insert 7 at the beginning. So

# linked list becomes 7->6->None

llist.push(7);

# Insert 1 at the beginning. So

# linked list becomes 1->7->6->None

llist.push(1);

# Insert 4 at the end. So linked list

# becomes 1->7->6->4->None

llist.append(4)

# Insert 8, after 7. So linked list

# becomes 1 -> 7-> 8-> 6-> 4-> None

llist.insertAfter(llist.head.next, 8)

print 'Created linked list is:',

llist.printList()
# This code is contributed by Manikantan Narasimhan

Output:

Created Linked list is: 1 7 8 6 4

Please refer complete article on Linked List | Set 2 (Inserting a node) for more details!

Article Tags :

Linked List

Python

Python Programs

Linked Lists

TCS

Wipro

Practice Tags :

Wipro

TCS

Linked List

Read Full Article

Program to insert new element into a linked list before the given position in Python

PythonServer Side ProgrammingProgramming

Suppose we have a list of elements; these elements are stored in a singly linked list. We also have a value pos and value val. We have to insert val before index pos of the linked list.

So, if the input is like nums = [1,5,3,6,8] pos = 3 val = 7, then the output will be [1,5,3,7,6,8]

To solve this, we will follow these steps −

new := create a linked list node with value same as val
if pos is same as 0, then
- next of new := list_head
- return new
temp := list_head
while temp is not null and pos is not same as 1, do
- temp := next of temp
- pos := pos - 1
next of new := next of temp
next of temp := new
return list_head

How to Insert a Node at a Specific Position in a Linked List

Kelly M.

Aug 16, 2020 · 5 min read

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; };