Java: удаление узла из связанного списка

Я пытаюсь удалить узел в связанном списке в java, но продолжаю получать исключение NullPointerException при попытке использовать мой метод deletenode ().

I get the following error trace:
Exception in thread "main" java.lang.NullPointerException
at linkedlist.LinkedList.deletenode(LinkedList.java:44)
at linkedlist.LinkedList.main(LinkedList.java:69)
/Users/carsongedeus/Library/Caches/NetBeans/8.2/executor-snippets/run.xml:53: 
Java returned: 1
BUILD FAILED (total time: 3 seconds)


package linkedlist;

import java.util.Scanner;

/**
 *
 * @author carsongedeus
 */

class Node {

    int data;
    Node next;

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

public class LinkedList {

    Node head;
    Node temp;

Вставка в начало списка.

    public Node insertnode(int data) {

        if (head == null) {
            head = new Node(data);
        } else {
            temp = new Node(data);
            temp.next = head;
            head = temp;
        }
        return head;
    }

Метод Delete выдает исключение NULLPointerException после того, как пользователь вводит указанное целое число в узле связанного списка.

    public void deletenode(int data) {

        Node trace;
        Node del;

        for(trace = head; trace != null; trace = trace.next) {

            if (trace.next.data == data) {
                del = trace.next;
                trace = trace.next.next;
                del.next = null;
            }
        }
    }

Принтер

    public void printer() {
        System.out.println(head.data);
    }

    public static void main(String[] args) {

        LinkedList linkedlist = new LinkedList();
        Scanner scan = new Scanner(System.in);
        int n;

        for(int i = 0; i < (n = (int)(Math.random()*100+1)); i++) {
            linkedlist.insertnode((int)(Math.random()*100+1));
            linkedlist.printer();
        }

        System.out.println("Delete something: ");
        int input = scan.nextInt();
        linkedlist.deletenode(input);

        for(int j = 0; j < n; j++) {
            linkedlist.printer();
        }
    }
}

не могли бы вы загрузить трассировку ошибок?

Dhiral Kaniya 29.07.2018 18:33

ваш метод удаления узла будет иметь npe, если head = null (в списке нет узлов) или если в списке есть один узел. должен проверять, если текущий элемент trace.data == data не trace.next.data == data

JasonM1 29.07.2018 18:34

замените trace.next.data==data на trace.data==data.

Dhiral Kaniya 29.07.2018 18:35
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
2
3
1 473
4

Ответы 4

public void deletenode(int data) {
    if (head != null && head.data == data) {
        head = head.next; // delete head
        return;
    }
    Node prev = null;
    Node cur = head;
    while (cur != null && cur.data != data) {
        prev = cur;
        cur = cur.next;
    }
    prev.next = cur.next; // delete cur
}

В вашем подходе удаляемый узел - это trace.next (который вы называете del). Это означает, что указатель tracenext необходимо обновить до trace.next.next, эффективно «пропуская» удаляемый узел (trace.next). Это выглядит так: trace.next = trace.next.next

Вместо этого вы изменяете сам trace, устанавливая его на trace.next.next. Я понимаю, что это сделано для того, чтобы итерация работала правильно, но испортит остальную часть вашего кода, поскольку вы потеряли указатель на узел, который нужно обновить. Если мы изменим trace.next, цикл позаботится о правильном перемещении указателя при запуске trace = trace.next при завершении.

В Java объект, на который больше нет ссылок, удаляется из памяти компьютера - этот процесс называется сборкой мусора. Поскольку мы уже изменили trace.next на этом этапе, больше нет ссылок на удаляемый узел, за исключением созданной вами переменной del. Как только эта переменная выходит из области видимости по завершении этой функции, узел будет удален сборщиком мусора без каких-либо дальнейших действий с вашей стороны. Вам даже действительно не нужна переменная del; как только мы потеряем ссылку на старый trace.next, обновив (пропустив) его, больше не будет никаких ссылок на этот узел, и сборщик мусора отбросит его.

Принимая все это во внимание, ваш код просто становится:

public void deletenode(int data) {

    Node trace;

    for(trace = head; trace != null; trace = trace.next) {

        if (trace.next.data == data) {
            trace.next = trace.next.next;
        }
    }
}

Не объявляйте временное поле: вместо этого используйте локальную переменную:

public Node insertnode(int data) {

    if (head == null) {
        head = new Node(data);
    } else {
        Node temp = new Node(data);
        temp.next = head;
        head = temp;
    }
    return head;
}

Чтобы ответить на ваш вопрос, вы проверяете, не является ли trace не нулевым, а затем пытаетесь получить доступ к trace.next.data без тестирования trace.next.

Попробуйте что-то вроде этого:

public void deletenode(int data) {

    Node prev = null;

    for(Node trace = head; trace != null; trace = trace.next) {

        if (trace.data == data) {
            if (prev == null) {
                head = trace.next;
            } else {
                prev.next = trace.next;
            }
        } else {
            prev = trace;
        }
    }
}

Я считаю, что ваш подход к проблеме неверен. Найдите подходящий способ ответа на вопрос, связанный со списком.

LinkedListNode класс:

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

Вставка в начале:

 LinkedListNode insertNodeAtBegining(LinkedListNode head, int val) {
        LinkedListNode temp= head;
        head= new LinkedListNode(val);
        head.next=temp;
        return head;
    }

Удаление узла:

LinkedListNode deleteNode(LinkedListNode head, LinkedListNode node) {
    if (head==null) {
        return head;
    }
    if (head.data==node.data) {
        return head.next;
    }

    LinkedListNode temp=head;
    while(temp.next!=null) {
        if (temp.next.data==node.data) {
            temp.next=temp.next.next;
        }
        temp=temp.next;
    }
    return head;
}

Другие вопросы по теме

Я не понимаю логики этого утверждения "cur = prev-> next;" в функции deleteall (key)
Обязательно ли пространственная сложность рекурсивного алгоритма не меньше глубины рекурсивного вызова?
Как рекурсивно объединить 2 отсортированных связанных списка в новый отсортированный список?
Ошибка NullPointerException при попытке найти значение последнего элемента в связанном списке
Использование простого цикла while для решения цикла связанного списка в Python возвращает AssertionError
Реализация Double LinkedList - максимальная глубина рекурсии при вызове головного узла
Как проверить, является ли связанный список круговым или нет, без использования дополнительной памяти или переменной?
Общий единый связанный список с unique_ptr, неизвестными ошибками в MS Visual Studio C++
Связанный список удалить узел дублирования из Java
Общий односвязный список с использованием std :: unique_ptr, неизвестные ошибки некомпиляции в Microsoft Visual Studio C++