Description

To add node before given node of the singly linked list - 
case 1: When list is empty
    create a node and assign the address of newly created node to the head
Case 2: When list has few elements
    step 1 : create a new node 
    step 2 : Traverse the list to reach the data before which new node to insert. Maintain
    one more address field which will point previous node during traversing.
    step 3 : Assign the address of node before which new node to insert into next field of newly created node.
    step 4 : Assign the address of new node to next field of previous node before which new node to be inserted.
    
Note: Here head contains the address of first node

C/C++

/* C program of Program To Add a node before given node singly linked list */
//Save it as add_node_before_given_node_singly_linked_list.c

#include<stdio.h>
#include<malloc.h>
struct node *create(int);
void display(struct node *);
struct node *insert_end(struct node *);
struct node *insert_node_before_given_node(struct node *);

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

int main(){
    int n;
    struct node *head;
    printf("Enter number of nodes : ");
    scanf("%d",&n);
    
    //Calling function to create node
    head=create(n);
    
    //Calling function to display list
    display(head);
    
    //Code to insert the node before given node of linked list
    head=insert_node_before_given_node(head);
    printf("\nThe linked list after addition of node before given node - \n");
    
    //Calling function to display list after addition of node before given node
    display(head);

    return 0;
}

struct node *create(int n){
    int i;
    struct node *head=NULL;
    struct node *ptr,*newNode;

    for(i=0;i<n;i++){
        
        //Creating a new node
        newNode=(struct node*)malloc(sizeof(struct node*));
        
        //Assigning data to newly created node
        printf("Enter the value of %d node : ",i+1);
        scanf("%d",&newNode->data);
        newNode->next=NULL;
        
        /*If list is empty assign the address of newly created node to head*/
        if(head==NULL){
            head=newNode;
        }else{
            
            /* If list already have few elements then loop through 
            list and add newly created node at the end of list*/
            ptr=head;
            while(ptr->next!=NULL){
                ptr=ptr->next;
            }
            ptr->next=newNode;
        }
    }
    return head;
}

void display(struct node *head){
    struct node *ptr;
    
    //If list is empty
    if(head==NULL){
        printf("The linked list is empty");
    }else{
        
        /*If list has elements then loop through the loop and
        print elements one by one in sequential manner*/
        ptr=head;
        while(ptr!=NULL){
            printf("The node value = %d and their address = %u\n",ptr->data,ptr);
            ptr=ptr->next;
        }
    }
}

struct node *insert_node_before_given_node(struct node *head){

    int val;
    struct node *newNode, *ptr, *preptr;
    
    //Creating a new node to be added before given node
    newNode=(struct node*)malloc(sizeof(struct node*));
    printf("\nEnter the data for new node to be added before a node : ");
    scanf("%d",&newNode->data);
    newNode->next=NULL;
    
    //assign the address of newly created node to the head if list is empty
    if(head==NULL){
        head=newNode;
    }else{
        printf("\nEnter the value from list before which new node to insert : ");
        scanf("%d",&val);
        ptr=head;
        
        //Traverse a list until value of list before which new node to insert
        while(ptr->data!=val){
            preptr=ptr;
            ptr=ptr->next;
        }
        newNode->next=ptr;
        preptr->next=newNode;
    }
    return head;
}

Input:
Enter number of nodes : 4
Enter the value of 1 node : 1
Enter the value of 2 node : 2
Enter the value of 3 node : 3
Enter the value of 4 node : 4
The node value = 1 and their address = 9571680
The node value = 2 and their address = 9571712
The node value = 3 and their address = 9571728
The node value = 4 and their address = 9571744

Enter the data for new node to be added before a node : 5

Enter the value from list before which new node to insert : 3

Output:
The linked list after addition of node before given node -
The node value = 1 and their address = 9571680
The node value = 2 and their address = 9571712
The node value = 5 and their address = 9571760
The node value = 3 and their address = 9571728
The node value = 4 and their address = 9571744

Java

/* Java program of Program To Add a node before given node singly linked list */
//Save it as AddNodeBeforeGivenNodeSinglyLinkedList.java

import java.io.*;
import java.util.Scanner;

public class AddNodeBeforeGivenNodeSinglyLinkedList {
    
    // Declaring node
    class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
            
            // Assigning null value to the next field
            this.next = null;
        }
    }

    public Node head = null;
    
    // Function to add node
    public void addNode(int data) {
        
        // Creating a new node
        Node newNode = new Node(data);
        
        /* If list is empty assign the address of newly created node to head */
        if (head == null) {
            head = newNode;
        } else {
            
            /* If list already have few elements then loop through 
            list and add newly created node at the end of list*/
            Node ptr = head;
            while (ptr.next != null) {
                ptr = ptr.next;
            }
            ptr.next = newNode;
        }
    }

    public void display() {
        Node ptr = head;
        
        // If list is empty
        if (ptr == null) {
            System.out.println("The list is empty");
            return;
        }
        System.out.println("The nodes of lists are : ");
        
        /*If list has elements then loop through the loop and print elements one by one
         in sequential manner*/
        while (ptr != null) {
            System.out.print(ptr.data + " ");
            ptr = ptr.next;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        AddNodeBeforeGivenNodeSinglyLinkedList list = new AddNodeBeforeGivenNodeSinglyLinkedList();

        System.out.println("Enter number of node you want to enter : ");
        int n = scanner.nextInt();

        for (int i = 0; i < n; i++) {
            System.out.println("Enter value of " + (i + 1) + " node : ");
            int val = scanner.nextInt();
            list.addNode(val);
        }
        
        // Calling function to display list
        list.display();

        System.out.println("\nEnter the value you want to insert before given node : ");
        int val = scanner.nextInt();
        
        list.insert_node_before_given_node(val);
        
        // Calling function to display list after addition of node before given node
        System.out.println("After addition of node before given node - ");
        list.display();
    }

    private void insert_node_before_given_node(int val) {

        Scanner scanner = new Scanner(System.in);
        
        Node preptr = null, ptr;
        
        //Creating a new node to be added before given node
        Node newNode = new Node(val);
        ptr=head;
        
        //assign the address of newly created node to the head if list is empty
        if(ptr==null) {
            head=newNode;
        }else {
            System.out.println("Enter the value from list before which new node to insert : ");
            int valueToInsert=scanner.nextInt();
            
            //Traverse a list until value of list before which new node to insert
            while(ptr.data!=valueToInsert) {
                preptr=ptr;
                ptr=ptr.next;
            }
            newNode.next=ptr;
            preptr.next=newNode;
        }
    }
}

Input:
Enter number of node you want to enter : 
5
Enter value of 1 node : 
1
Enter value of 2 node : 
2
Enter value of 3 node : 
3
Enter value of 4 node : 
4
Enter value of 5 node : 
5
The nodes of lists are : 
1 2 3 4 5 
Enter the value you want to insert before given node : 
8
Enter the value from list before which new node to insert : 
4

Output:
After addition of node before given node - 
The nodes of lists are : 
1 2 3 8 4 5

Related Programs