What are the ways to insert a node in linked list write an algorithm for inserting a node before a given node in a linked list?

Insert a node in Linked List before a given node

Given a node of Linked List N and a value K, the task is to insert the node with value K in the linked list before the given node N.

Nội dung chính Show

Insert a node in Linked List before a given node
When given Node is the Head Node:
When given Node is any valid node except head node:
Linked List | Set 2 (Inserting a node)
Linked List Operations: Traverse, Insert and Delete
Things to Remember about Linked List
Inserting a node at the beginning of a linked list
Video liên quan

Structure of the Node:

C++

// Structure of Node

struct Node {

int data;

Node* next;

// Constructor of Node

Node(int val, Node* link = 0)

: data(val), next(link)

{

}
};

Java

// Structure of Node

public class Node
{

public int data;

public Node next;

// Constructor of Node

public Node(int val, Node link = null)

{

this.data = val;

this.next = link;

}
}
// This code is contributed by divyesh072019

Python3

# Structure of Node

class Node:

# Constructor of Node

def __init__(self, val, link = None):

self.data = val

self.next = link

# This code is contributed by pratham76

// Structure of Node

public class Node
{

public int data;

public Node next;

// Constructor of Node

public Node(int val, Node link = null)

{

this.data = val;

this.next = link;

}
};
// This code is contributed by rutvik_56

Javascript

Output: 5 8 6

In the given problem there might be two cases:

Given node is the head node.
Given node is any valid node except the head.

When given Node is the Head Node:

The idea is to create a new node with the given value K. Then the next part of the new node will be updated with the pointer head. And finally, the head will be updated with the new node’s address. Below is the image of the same:

What are the ways to insert a node in linked list write an algorithm for inserting a node before a given node in a linked list?

When given Node is any valid node except head node:

The simplest approach is to traverse the given linked list to search the previous node of the given node. Then, create the new node with the given value K.Now, update the next part of the new node with the address of the given node and the next part of the previous node with the address of the new node. Below is an illustration of the approach with the help of image:

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include 

using namespace std;

struct Node {

int data;

Node* next;

// Constructor of Node

Node(int val, Node* link = 0)

: data(val), next(link)

{

}
};
// Create a head node

Node* head = new Node(5);
// Function prints the linked list
// starting from the given node

void printList(Node* n)
{

// Till n is not NULL

while (n != NULL) {

// Print the data

cout << n->data << " ";

n = n->next;

}
}
// Function to add a node before the
// given node other than head node

Node* addBefore(Node* given_ptr, int val)
{

// First check if the given pointer

// is the address of head

if (head == given_ptr) {

// Create a new node

Node* n = new Node(val);

// Point to next to current head

n->next = head;

// Update the head pointer

head = n;

return n;

}

// Otherwise traverse the list to

// find previous node of given node

else {

Node *p, *n = head;

// This loop will return p with

// previous pointer of given node

for (n, p; n != given_ptr;

p = n, n = n->next)

;

// Create a new node

Node* m = new Node(val);

// Update the m->next

m->next = p->next;

// Update previous node's next

p->next = m;

return m;

}
}
// Driver Code

int main()
{

// Head Node

head->next = new Node(6);

// Function Call

addBefore(head->next, 8);

// Print the linked List

printList(head);
}

Java

// Java program for the above approach

import java.util.*;

class GFG{

static class Node
{

int data;

Node next;

// Constructor of Node

Node(int val)

{

this.data = val;

this.next = null;

}
}

static Node head = new Node(5);
// Function prints the linked list
// starting from the given node

static void printList(Node n)
{

// Till n is not null

while (n != null)

{

// Print the data

System.out.print(n.data + " ");

n = n.next;

}
}
// Function to add a node before the
// given node other than head node

static Node addBefore(Node given_ptr, int val)
{

// First check if the given pointer

// is the address of head

if (head == given_ptr)

{

// Create a new node

Node n = new Node(val);

// Point to next to current head

n.next = head;

// Update the head pointer

head = n;

return n;

}

// Otherwise traverse the list to

// find previous node of given node

else

{

Node p = null;

// This loop will return p with

// previous pointer of given node

for(Node n = head; n != given_ptr;

p = n, n = n.next);

// Create a new node

Node m = new Node(val);

// Update the m.next

m.next = p.next;

// Update previous node's next

p.next = m;

return m;

}
}
// Driver Code

public static void main(String[] args)
{

// Head Node

head.next = new Node(6);

// Function Call

addBefore(head.next, 8);

// Print the linked List

printList(head);
}
}
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach

class Node:

# Constructor of Node

def __init__(self, val, link = None):

self.data = val

self.next = link
# Create a head node

head = Node(5);

# Function prints the linked list
# starting from the given node

def printList(n):

# Till n is not NULL

while (n != None):

# Print the data

print(n.data, end = ' ')

n = n.next;

# Function to add a node before the
# given node other than head node

def addBefore(given_ptr, val):

global head

# First check if the given pointer

# is the address of head

if (head == given_ptr):

# Create a node

n = Node(val);

# Point to next to current head

n.next = head;

# Update the head pointer

head = n;

return n;

# Otherwise traverse the list to

# find previous node of given node

else:

p = None

n = head;

# This loop will return p with

# previous pointer of given node

while(n != given_ptr):

p = n

n = n.next

# Create a node

m = Node(val);

# Update the m.next

m.next = p.next;

# Update previous node's next

p.next = m;

return m;

# Driver Code

if __name__=='__main__':

# Head Node

head.next = Node(6);

# Function Call

addBefore(head.next, 8);

# Print the linked List

printList(head);

# This code is contributed by rutvik_56

// C# program for the 
// above approach

using System;

class GFG{

class Node
{

public int data;

public Node next;

// Constructor of Node

public Node(int val)

{

this.data = val;

this.next = null;

}
}

static Node head = new Node(5);
// Function prints the linked list
// starting from the given node

static void printList(Node n)
{ 

// Till n is not null

while (n != null)

{

// Print the data

Console.Write(n.data + " ");

n = n.next;

}
}
// Function to add a node before the
// given node other than head node

static Node addBefore(Node given_ptr,

int val)
{ 

// First check if the given

// pointer is the address of

// head

if (head == given_ptr)

{

// Create a new node

Node n = new Node(val);

// Point to next to current

// head

n.next = head;

// Update the head pointer

head = n;

return n;

}

// Otherwise traverse the list

// to find previous node of

// given node

else

{

Node p = null;

// This loop will return p with

// previous pointer of given node

for(Node n = head; n != given_ptr;

p = n, n = n.next);

// Create a new node

Node m = new Node(val);

// Update the m.next

m.next = p.next;

// Update previous node's next

p.next = m;

return m;

}
}
// Driver Code

public static void Main(String[] args)
{ 

// Head Node

head.next = new Node(6);

// Function Call

addBefore(head.next, 8);

// Print the linked List

printList(head);
}
}
// This code is contributed by shikhasingrajput

Javascript

Output: 5 8 6

Time Complexity: O(N)
Auxiliary Space: O(1)

Article Tags :

Data Structures

Linked List

Linked Lists

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.

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

Inserting a node at the beginning of a linked list

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

Example

Assume that the linked list has elements: 20 30 40 NULL

If we insert 100, it will be added at the beginning of a linked list.

After insertion, the new linked list will be

100 20 30 40 NULL

What are the ways to insert a node in linked list write an algorithm for inserting a node before a given node in a linked list?

Insert a node in Linked List before a given node

When given Node is the Head Node:

When given Node is any valid node except head node:

Linked List | Set 2 (Inserting a node)

Linked List Operations: Traverse, Insert and Delete

Things to Remember about Linked List

Inserting a node at the beginning of a linked list

Example

Bài Viết Liên Quan

Có thể bạn quan tâm

Xem Nhiều

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội