Java Program to Reverse a Singly Linked List

This program demonstrates how to reverse a singly linked list in Java. A singly linked list is a data structure where each node contains a value and a reference (or link) to the next node in the sequence. The task of reversing the list involves changing the direction of these links so that the list is traversed in the opposite order.

Program Structure

The program consists of the following components:

• Node class: This class represents an individual node in the singly linked list. It contains an integer value and a reference to the next node.
• LinkedList class: This class provides methods to manipulate the singly linked list, including adding nodes and reversing the list.
• main method: The entry point of the program, where the linked list is created, populated, and reversed.

Program Code

/**
 * This class represents a node in a singly linked list.
 */
class Node {
    int data;
    Node next;

    // Constructor to create a new node
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

/**
 * This class implements a singly linked list and provides methods
 * to reverse the list.
 */
class LinkedList {
    Node head;

    /**
     * Adds a new node with the specified data to the end of the list.
     *
     * @param data The data for the new node.
     */
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    /**
     * Reverses the singly linked list.
     */
    public void reverse() {
        Node prev = null;
        Node current = head;
        Node next = null;

        while (current != null) {
            next = current.next;  // Store the next node
            current.next = prev;  // Reverse the current node's pointer
            prev = current;       // Move pointers one position ahead
            current = next;
        }
        head = prev;  // Update the head to the new first node
    }

    /**
     * Displays the contents of the linked list.
     */
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

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

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

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

        // Reversing the linked list
        list.reverse();

        System.out.println("Reversed List:");
        list.display();
    }
}

Explanation

Here’s a step-by-step explanation of the program:

1. Node Class

The Node class represents a single element in the linked list. Each node contains:

• data: The integer value stored in the node.
• next: A reference to the next node in the list.

2. LinkedList Class

The LinkedList class manages the linked list. It includes methods to add a node, reverse the list, and display the list.

Adding Nodes

The add method appends a new node with the given data to the end of the list. If the list is empty, the new node becomes the head of the list.

Reversing the List

The reverse method changes the direction of the pointers in the list. It iterates through the list and for each node, it reverses the direction of the next pointer. The process continues until all nodes have been processed, and finally, the head is updated to point to the last node, which is now the first node after reversal.

Displaying the List

The display method prints the values of all nodes in the list from the head to the last node.

3. Main Method

In the main method, a linked list is created and populated with five elements. The list is then displayed in its original order. After calling the reverse method, the list is displayed again, showing the reversed order of elements.

Conclusion

This program effectively demonstrates how to reverse a singly linked list in Java. By understanding the manipulation of pointers in the reverse method, you can apply similar logic to other linked list operations.