Java：从链表中删除节点

Question

我正在尝试在 java 中删除链表中的节点，但是在尝试使用我的 deletenode() 方法时，我不断收到 NullPointerException。

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();

        }

    }

}

Answer 1

在您的方法中，要删除的节点是trace.next（您将其称为del）。这意味着需要将thattrace的next指针更新为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) {&nbsp; &nbsp; Node trace;&nbsp; &nbsp; for(trace = head; trace != null; trace = trace.next) {&nbsp; &nbsp; &nbsp; &nbsp; if(trace.next.data == data) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; trace.next = trace.next.next;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}

Answer 2

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