C Program to insert 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.

Table of Contents 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:
Inserting a node at the beginning of a linked list
Linked List Operations: Traverse, Insert and Delete
Things to Remember about Linked List
Putting everything together
Author: Srikanta

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

<script>
// Structure of Node
class Node {

// Constructor of Node

constructor(val, link = null) {

this.data = val;

this.next = link;

}
}
// This code is contributed by gauravrajput1
</script>

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:

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

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

<script>
// Javascript program for the above approach

class Node {

// Constructor of Node

constructor(val) {

this.data = val;

this.next = null;

}
}

var head = new Node(5);

// Function prints the linked list

// starting from the given node

function printList(n) {

// Till n is not null

while (n != null) {

// Print the data

document.write(n.data + " ");

n = n.next;

}

}

// Function to add a node before the

// given node other than head node

function addBefore(given_ptr , val) {

// First check if the given pointer

// is the address of head

if (head == given_ptr) {

// Create a new node

var 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 {

var p = null;

// This loop will return p with

// previous pointer of given node

for (n = head; n != given_ptr; p = n, n = n.next)

;

// Create a new node

var m = new Node(val);

// Update the m.next

m.next = p.next;

// Update previous node's next

p.next = m;

return m;

}

}

// Driver Code

// Head Node

head.next = new Node(6);

// Function Call

addBefore(head.next, 8);

// Print the linked List

printList(head);
// This code is contributed by todaysgaurav
</script>

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

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

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

Putting everything together

Here is the complete program that inserts elements in a linked list in all 4 positions mentioned above. You can compile this program and run.

/* File name: test.c Compile: cc test.c */ #include <stdio.h> #include <stdlib.h> struct node{ int val; struct node *next; }; void print_list(struct node *head) { printf("H->"); while(head) { printf("%d->", head->val); head = head->next; } printf("|||\n\n"); } void insert_front(struct node **head, int value) { struct node * new_node = NULL; new_node = (struct node *)malloc(sizeof(struct node)); if (new_node == NULL) { printf("Failed to insert element. Out of memory"); } new_node->val = value; new_node->next = *head; *head = new_node; } void insert_end(struct node **head, int value) { struct node * new_node = NULL; struct node * last = NULL; new_node = (struct node *)malloc(sizeof(struct node)); if (new_node == NULL) { printf("Failed to insert element. Out of memory"); } new_node->val = value; new_node->next = NULL; if( *head == NULL) { *head = new_node; return; } last = *head; while(last->next) last = last->next; last->next = new_node; } void insert_after(struct node *head, int value, int after) { struct node * new_node = NULL; struct node *tmp = head; while(tmp) { if(tmp->val == after) { /*found the node*/ new_node = (struct node *)malloc(sizeof(struct node)); if (new_node == NULL) { printf("Failed to insert element. Out of memory"); } new_node->val = value; new_node->next = tmp->next; tmp->next = new_node; return; } tmp = tmp->next; } } void insert_before(struct node **head, int value, int before) { struct node * new_node = NULL; struct node * tmp = *head; new_node = (struct node *)malloc(sizeof(struct node)); if (new_node == NULL) { printf("Failed to insert element. Out of memory"); return; } new_node->val = value; if((*head)->val == before) { new_node->next = *head; *head = new_node; return; } while(tmp && tmp->next) { if(tmp->next->val == before) { new_node->next = tmp->next; tmp->next = new_node; return; } tmp = tmp->next; } /*Before node not found*/ free(new_node); } void main() { int count = 0, i, val, after, before; struct node * head = NULL; printf("Enter number of elements: "); scanf("%d", &count); for (i = 0; i < count; i++) { printf("Enter %dth element: ", i); scanf("%d", &val); insert_front(&head, val); } printf("Initial List: "); print_list(head); printf("Enter a value to enter at the front of the list: "); scanf("%d", &val); insert_front(&head, val); printf("List after insertion: "); print_list(head); printf("Enter a value to enter at the end of the list: "); scanf("%d", &val); insert_end(&head, val); printf("List after insertion: "); print_list(head); printf("Enter a value to insert in the list: "); scanf("%d", &val); printf("Insert after: "); scanf("%d", &after); insert_after(head, val, after); printf("List after insertion: "); print_list(head); printf("Enter a value to insert in the list: "); scanf("%d", &val); printf("Insert before: "); scanf("%d", &before); insert_before(&head, val, before); printf("List after insertion: "); print_list(head); }

And the output of the program:

Enter number of elements: 3 Enter 0th element: 55 Enter 1th element: 77 Enter 2th element: 66 Initial List: H->66->77->55->||| Enter a value to enter at the front of the list: 10 List after insertion: H->10->66->77->55->||| Enter a value to enter at the end of the list: 100 List after insertion: H->10->66->77->55->100->||| Enter a value to insert in the list: 11 Insert after: 77 List after insertion: H->10->66->77->11->55->100->||| Enter a value to insert in the list: 222 Insert before: 77 List after insertion: H->10->66->222->77->11->55->100->|||

Note: All the programming examples above are tested on Linux (Fedora) environment using cc compiler. If you have any problem in trying these examples on other systems, let us know by commenting, we’ll try to solve.

Read also: How to insert element in sorted link list.

Author: Srikanta

I write here to help the readers learn and understand computer programing, algorithms, networking, OS concepts etc. in a simple way. I have 20 years of working experience in computer networking and industrial automation. View all posts by Srikanta

If you also want to contribute, click here.