Java Program to Insert a Node at the Beginning of a Linked List

Introduction

Inserting a node at the beginning of a linked list involves adding a new node before the current head node, then updating the head to point to the new node. This operation is commonly used when you need to prepend data to the list. This guide will walk you through writing a Java program that inserts a node at the beginning of a singly linked list.

Problem Statement

Create a Java program that:

Implements a singly linked list.
Inserts a node at the beginning of the linked list.
Displays the linked list before and after the insertion.

Example:

Input: Linked list: 2 -> 3 -> 4 -> 5, insert node with value 1
Output: 1 -> 2 -> 3 -> 4 -> 5
Input: Linked list: 10 -> 20 -> 30, insert node with value 5
Output: 5 -> 10 -> 20 -> 30

Solution Steps

Create the Linked List and Node Structure: Define a Node class to represent each element in the linked list and a LinkedList class to manage the list.
Add Nodes to the Linked List: Implement methods to add nodes to the linked list.
Insert a Node at the Beginning of the Linked List:

Create a new node with the specified value.
Set the new node’s next pointer to the current head node.
Update the head to point to the new node.

Display the Result: Output the linked list before and after inserting the new node.

Java Program

// Java Program to Insert a Node at the Beginning of a Linked List
// Author: https://www.rameshfadatare.com/

class Node {
    int data;
    Node next;

    // Constructor to initialize the node
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // Method to add a new node at the end of the list
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            // Step 1: Initialize the head if the list is empty
            head = newNode;
        } else {
            // Step 2: Traverse to the end of the list and add the new node
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Method to insert a new node at the beginning of the list
    public void insertAtBeginning(int data) {
        // Step 3: Create a new node with the given data
        Node newNode = new Node(data);

        // Step 4: Point the new node's next to the current head
        newNode.next = head;

        // Step 5: Update the head to point to the new node
        head = newNode;
    }

    // Method to display the linked list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class InsertAtBeginning {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Adding elements to the linked list
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        System.out.println("Original Linked List:");
        list.display();

        // Inserting a node at the beginning of the linked list
        list.insertAtBeginning(1);

        System.out.println("Linked List after inserting node with value 1 at the beginning:");
        list.display();
    }
}

Explanation

Step 1: Initialize the Node Class

The Node class represents a single node in the linked list. Each node contains data and a reference to the next node in the list.
The constructor initializes the node with data and sets the next pointer to null.

Step 2: Initialize the LinkedList Class

The LinkedList class manages the linked list. The class contains the head node that points to the first node in the list.
The add() method appends a new node to the end of the list. If the list is empty, the head node is set to the new node.

Step 3: Insert a Node at the Beginning of the Linked List

The insertAtBeginning() method adds a new node to the start of the linked list:
- A new node is created with the given data.
- The new node’s next pointer is set to point to the current head node.
- The head is updated to point to the new node.

Output Example

Original Linked List:
2 -> 3 -> 4 -> 5 -> null
Linked List after inserting node with value 1 at the beginning:
1 -> 2 -> 3 -> 4 -> 5 -> null

Example with Different Input

If you modify the input list to:

list.add(10);
list.add(20);
list.add(30);

And insert the node with value 5 at the beginning:

list.insertAtBeginning(5);

The output will be:

Original Linked List:
10 -> 20 -> 30 -> null
Linked List after inserting node with value 5 at the beginning:
5 -> 10 -> 20 -> 30 -> null

Conclusion

This Java program demonstrates how to insert a node at the beginning of a singly linked list by adjusting the head pointer. The program efficiently adds the node to the front of the list, providing a fundamental operation that is useful in various scenarios. This exercise is valuable for understanding how to manage and manipulate linked lists in Java programming.