Implement a Singly Linked List

Problem Statement:

Create a Java program to implement a singly linked list. A singly linked list is a linear data structure where each element is a node containing data and a reference to the next node in the sequence. This program will involve creating nodes, adding elements, and performing operations such as displaying the list, adding elements, and deleting elements.

Node Definition:

• Each node in the singly linked list will have two properties:
  • data: The value stored in the node.
  • next: A reference to the next node in the list.

Example Operations:

• Insertion: Add a new node to the end of the list.
• Deletion: Remove a node from the list by value.
• Traversal: Print all elements of the list.

Step-by-Step Solution:

Step 1: Define the Node Class

• Create a class Node to represent a single node in the linked list.

public class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Step 2: Define the LinkedList Class

• Create a class SinglyLinkedList to manage the linked list operations.

public class SinglyLinkedList {
    Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
    
    // Method to add a node to the end of the list
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
    
    // Method to delete a node by value
    public void delete(int value) {
        if (head == null) return;
        if (head.data == value) {
            head = head.next;
            return;
        }
        Node current = head;
        while (current.next != null && current.next.data != value) {
            current = current.next;
        }
        if (current.next != null) {
            current.next = current.next.next;
        }
    }
    
    // Method to print all nodes in the list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

Complete Solution:

public class LinkedListExample {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.append(4);

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

        list.delete(3);
        System.out.println("After deleting 3:");
        list.display();
    }
}

Explanation:

• Node Class: Defines the basic structure of a node with data and next properties.
• SinglyLinkedList Class: Manages the list operations, including adding nodes to the end, deleting nodes by value, and displaying the list.
• Appending Nodes: Adds new nodes to the end of the list, adjusting the next references accordingly.
• Deleting Nodes: Removes nodes by value, handling cases where the node to delete is at the head or elsewhere in the list.
• Displaying the List: Traverses the list from the head to the end, printing each node’s data.

Example:

SinglyLinkedList list = new SinglyLinkedList();
list.append(10);
list.append(20);
list.append(30);
list.display(); // Output: 10 -> 20 -> 30 -> null
list.delete(20);
list.display(); // Output: 10 -> 30 -> null

This program demonstrates how to implement a singly linked list in Java, covering the essential operations and providing a foundation for more complex data structure manipulations.