1. Introduction

Deletion is one of the primary operations in a linked list, allowing us to remove a node based on its value or position. In this blog post, we will walk through the process of implementing deletion operations in a singly linked list using Java.

2. Program Steps

1. Define a Node class to represent each element of the linked list.

2. Implement a LinkedList class to manage the list operations.

3. Within the LinkedList class, add methods for the following:

– deleteFirstOccurrence(int value): Deletes the first occurrence of a given value.

– deleteAtPosition(int position): Deletes a node at a specified position.

4. Test the methods with a driver program.

3. Code Program

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    // Add a new node at the end
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    // Delete first occurrence of a value
    public void deleteFirstOccurrence(int value) {
        if (head == null) return;

        if (head.data == value) {
            head = head.next;
            return;
        }

        Node temp = head;
        while (temp.next != null && temp.next.data != value) {
            temp = temp.next;
        }

        if (temp.next != null) {
            temp.next = temp.next.next;
        }
    }

    // Delete node at a given position
    public void deleteAtPosition(int position) {
        if (head == null) return;

        Node temp = head;

        if (position == 0) {
            head = temp.next;
            return;
        }

        for (int i=0; temp!=null && i<position-1; i++) {
            temp = temp.next;
        }

        if (temp == null || temp.next == null) return;

        temp.next = temp.next.next;
    }

    // Utility function to print the list
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }
}

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.append(10);
        list.append(20);
        list.append(30);
        list.append(40);
        list.append(50);

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

        list.deleteFirstOccurrence(30);
        System.out.println("\nList after deleting value 30:");
        list.printList();

        list.deleteAtPosition(2);
        System.out.println("\nList after deleting at position 2:");
        list.printList();
    }
}

Output:

Original List:
10 -> 20 -> 30 -> 40 -> 50 -> NULL

List after deleting value 30:
10 -> 20 -> 40 -> 50 -> NULL

List after deleting at position 2:
10 -> 20 -> 50 -> NULL

4. Step By Step Explanation

1. The Node class represents an individual node in the linked list. Each node contains data and a reference to the next node, next.

2. The LinkedList class offers methods to manipulate the linked list.

3. The deleteFirstOccurrence method deletes the first node with a specified value:

– If the head node matches the value, it updates the head pointer.

– Otherwise, it traverses the list until it finds the value and then updates the pointers to delete it.

4. The deleteAtPosition method deletes a node at a specified position.

5. In the LinkedListDemo class, we demonstrate the functionality by creating a linked list, deleting a specific value, and then deleting a node at a certain position.

Using these deletion methods, we can easily manage and modify our linked list in various ways.