Java program to delete all even nodes from a singly linked list

This Java program efficiently removes all even-valued nodes from a singly linked list. Let's refine the explanation and presentation for clarity.

This article demonstrates how to remove all even-numbered nodes from a singly linked list in Java. We'll cover creating the list, adding nodes, deleting even-valued nodes, and displaying the final list.

A singly linked list is a linear data structure where each node points to the next node in the sequence. Each node contains data (in this case, an integer) and a pointer to the next node.

Problem: Delete all even-valued nodes from a singly linked list.

Input Example:

<code>Original List: 1 2 3 4 5 6</code>

Output Example:

<code>Original List: 1 2 3 4 5 6
List after deleting even nodes: 1 3 5</code>

Algorithm:

1. Initialization: Create an empty singly linked list.
2. Node Insertion: Add nodes with integer values (e.g., 1, 2, 3, 4, 5, 6) to the list.
3. Even Node Removal:
   • Remove Leading Evens: Iterate from the head of the list, removing any even-valued nodes at the beginning until an odd-valued node is encountered.
   • Remove Internal Evens: Traverse the remaining list. If a node's next node has an even value, bypass it by linking the current node directly to the node after the even-valued node.
4. Output: Print the remaining nodes in the list.

Java Code:

public class LinkedList {
    static class Node {
        int data;
        Node next;

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

    Node head;

    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }

    public void deleteEvenNodes() {
        //Remove leading even nodes
        while (head != null && head.data % 2 == 0) {
            head = head.next;
        }

        //Remove internal even nodes
        if (head != null) {  //Check if list is not empty after removing leading evens
            Node current = head;
            while (current != null && current.next != null) {
                if (current.next.data % 2 == 0) {
                    current.next = current.next.next;
                } else {
                    current = current.next;
                }
            }
        }
    }

    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);
        list.insert(6);

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

        list.deleteEvenNodes();

        System.out.println("List after deleting even nodes:");
        list.printList();
    }
}

Output:

<code>Original List:
1 2 3 4 5 6 
List after deleting even nodes:
1 3 5 </code>

This improved version includes a more concise explanation, clearer code comments, and handles the edge case where all nodes are even (resulting in an empty list). The addition of a check (if (head != null)) before processing internal nodes prevents a NullPointerException if all leading nodes were even.

The above is the detailed content of Java program to delete all even nodes from a singly linked list. For more information, please follow other related articles on the PHP Chinese website!