如何从链表中删除一个值？

Question

我正在为我的数据结构 class 开发一个项目，该项目要求我编写一个 class 来实现一个整数链表。

Use an inner class for the Node.

Include the methods below.

Write a tester to enable you to test all of the methods with whatever data you want in any order.

我必须创建一个名为“public boolean delete(int item)”的方法。此方法旨在“从列表中删除一个项目和 return 一个布尔值，指示该项目是否已删除”我在下面有此方法的代码。但是，当我尝试从我的列表中删除一个项目时，没有任何变化。我尝试删除的项目仍然存在，但确实 return确实有一个项目被删除了。有人知道我在代码中做错了什么以及如何解决吗？

import java.util.Random;
import java.util.Scanner;

public class LinkedListOfInts {
    Node head;
    Node tail;

    private class Node {
        int value;
        Node nextNode;

        public Node(int value, Node nextNode) {
            this.value = value;
            this.nextNode = nextNode;
        }

    }

    public LinkedListOfInts(LinkedListOfInts other) {
        Node tail = null;
        for (Node n = other.head; n != null; n = n.nextNode) {
            if (tail == null)
                this.head = tail = new Node(n.value, null);
            else {
                tail.nextNode = new Node(n.value, null);
                tail = tail.nextNode;
            }
        }
    }

    public LinkedListOfInts(int[] other) {
        Node[] nodes = new Node[other.length];
        for (int index = 0; index < other.length; index++) {
            nodes[index] = new Node(other[index], null);
            if (index > 0) {
                nodes[index - 1].nextNode = nodes[index];
            }
        }

        head = nodes[0];
    }

    public LinkedListOfInts(int N, int low, int high) {
        Random random = new Random();
        for (int i = 0; i < N; i++)
            this.addToFront(random.nextInt(high - low) + low);
    }

    public void addToFront(int x) {
        head = new Node(x, head);
    }

    public int deleteFromFront() {
        int headValue = -1;
        if (head == null)
            return headValue;
        else {
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                headValue = head.value;
                head = head.nextNode;
            }
        }
        return headValue;
    }

    public boolean delete(int item) {
        Node previous = null;
        for (Node ptr = head; ptr != null; ptr = ptr.nextNode) {
            if (ptr.value == item) {
                if (previous != null) {
                    previous = ptr;
                } else
                    deleteFromFront();
                return true;
            }
            previous = ptr;
        }
        return false;
    }

    public String toString() {
        String result = " ";
        for (Node ptr = head; ptr != null; ptr = ptr.nextNode)
            result += ptr.value + " ";
        return result;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        LinkedListOfInts list = new LinkedListOfInts(10, 1, 20);
        LinkedListOfInts copy = new LinkedListOfInts(list);
        boolean done = false;
        while (!done) {
            System.out.println("1. Delete an Item in the Array");
            System.out.println("2. toString");
            switch (input.nextInt()) {
            case 11:
                System.out.println("Delete an Item in the Array");
                System.out.println(list.delete(input.nextInt()));
                break;
            case 12:
                System.out.println("toString");
                System.out.println(list.toString());
                break;
            }
        }
    }
}

Answer 1

因为局部变量是局部的。让我们来看看你的 delete 方法：

Node previous = null;

这声明了一个名为 previous 的新局部变量，该变量当前未指向任何内容。与所有局部变量和所有非原始变量一样，[A] 一旦方法终止，这个东西就会消失，[B] 它是一个指针。（用 java 的说法，参考）。这就像石板上的地址，而不是房子。这是房子的地址。

previous = ptr;

这会擦除您石板上的内容并复制住家地址。它不会复制房子，也不会在擦除该地址并复制 'ptr' 石板上的任何地址之前对地址在您石板上的房子有任何影响。

... method ends

... 然后 previous 去了。在垃圾桶里。

a.b 是 java-ese 用于：开车到石板 'a' 上的地址，并要求房子 'b'（或改变房子的一些东西，如果您正在处理字段而不是调用方法）。

所以，pointer = foo一事无成。 head.something = foo，这确实有用，现在你在开车。您必须开车到某个地方，或更改您的字段之一，此代码才能执行任何操作。

previous.nextNode = ptr.nextNode; 更符合您的需求。 previous是你之前访问过的节点地址的copy。更改小纸条上的地址不会有任何效果，你想开车过去。 previous.nextNode是：找到那张名为'previous'的纸上潦草的地址，开车过去。进入房子，找到标有 'nextNode' 的盒子。打开盒子，你会发现一张纸条，里面有地址。拿那个地址，把它划掉，然后在上面写一个新地址。

现在，如果其他人拿着写有相同地址的另一张纸，继续行驶并拉出那个盒子，他们就会看到您所做的更改。

在 java 中，几乎所有内容都是写在便条上的地址，而不是对象本身。（唯一的例外是原语：int、long、double、float、boolean、char、short、byte).

如何从链表中删除一个值？

How can I delete a value from a Linked List?

java

methods

boolean

linked-list

data-structures