Java - 如何从链表中删除一个节点？

Question

这段代码是一个表格，其中包含插入名称、删除、显示和退出选项。

这段代码运行良好，但我的唯一问题是如何在节点中删除所选择的名称。

class Node{

Node in;
String name;

public Node(){

    in = null;

}

public Node(String n){

    in = null;
    name = n;

}

public void setIn(Node n){

    in = n;

}

public Node getIn(){

    return in;

}

public void setName(String n){

    name = n;

}

public String getName(){

    return name;

}




 public class Main{

public static void main(String args[]){
    Scanner scan = new Scanner(System.in);
    LinkedList bi = new LinkedList();
    while(true){

        System.out.println("Choose!\n[a] Insert Name\n[b] Delete\n[c] Show\n[d] Exit");
        char c = scan.next().charAt(0);
        System.out.println();

        if(c == 'a'){

            System.out.print("Enter Name: ");
            bi.insert(scan.next());
            System.out.println();

        }
        else if(c == 'b'){

            System.out.print("Enter Name to delete: ");
            bi.delete(scan.next());
            System.out.println();
        }
        else if(c == 'c'){

            bi.show();
            System.out.println();

        }
        else if(c == 'd'){

            System.exit(0);

        }

    }

}

  }


class LinkedList{

private Node root;

public LinkedList(){

    root = null;
}

public void insert(String n){

    root = insert(root, n);

}

private Node insert(Node n, String r){

    if(n == null){

        n = new Node(r);

    }
    else{

        n.in = insert(n.in, r);

    }

    return n;

}

public void delete(String n){

    root = delete(root, n);

}

private Node delete(Node n, String r){




}

public void show(){

    show(root);

}

private Node show(Node n){
    if(n == null){

        System.out.println("Empy list!");

    }
    else{

        while(n!=null){

            System.out.println(n.getName());
            n = n.getIn();

        }

    }

    return n;
}

 }

我不知道如何删除一个节点。我的删除方法应该加什么?

public void delete(String n){

    root = delete(root, n);

}

private Node delete(Node n, String r){




}

- user3505049

---

正如其他人所说，先试一试。提示：在搜索要删除的节点时，使用两个指针遍历列表。 - Inertiatic

Answer 1

我们可以为您编写代码，但这样做没有意义。相反，我建议您在纸上绘制链表数据结构，使用方框表示列表节点和节点字段，使用箭头表示指针/引用。然后，为算法的本地变量绘制更多的方框，并进行“手动执行”。这将帮助您可视化您的代码应该做什么。

一旦您这样做了几次，您就能在脑海中形象化地想象出来...

引用： 抱歉，不能给你提供示例。通过自己解决问题，您将学到更多。请参见上文。

- Stephen C

Answer 2

要删除节点，实际上需要更新其前一个节点的“next”指针为要删除节点的“next”指针，并且保留的节点最终会被垃圾回收。唯一需要注意的是，如果要删除的节点是根节点，则需要更新根节点。

private Node delete(Node root, String data)
{
    //in case list is empty then return
    if(root==null) return n;
    //in case node to be deleted is root then just return next as new root
    if (root.name.equals(data)) return root.in;

    Node curr = root;
    while(curr.in!=null)
    {
        if (curr.in.name.equals(data))
        {
            //curr.in's referenced Node will be garbage collected (or run some cleanup manually on it)
            curr.in = curr.in.in;
            //we are done and root is same
            return root;
        }
        curr = curr.in;
    }
    //if here then not found and nothing changed
    return root;
}

- gitesh.tyagi

---

root = null 在函数内部不会执行任何操作。Java 是按值传递，而不是按引用传递。 - majurageerthan

Answer 3

while (node != null) {

            if (node.getNext() == null || head.getNext() == null) {
                break;

            } else if (head.getData() == data) {
                head = head.getNext();
            } else if (node.getNext().getData()==null&&data==null||node.getNext().getData().equals(data)) {
                node.setNext(node.getNext().getNext());
            } else {
                node = node.getNext();
            }
        }
    }

    return head;

- Kartik Imley

---

欢迎来到 Stack Overflow！当你回复仅有代码时，请尽量解释一下它的含义。 - David García Bodego

Answer 4

你是想从节点中移除名字，还是将节点从列表中移除？如果是要将节点从列表中移除，可以使用 LinkedList.remove(int index) 方法。你需要先找到要移除的节点的索引。

【编辑】就像其他人所说的，你应该尝试自己解决问题，但这里提供一个提示：可以使用 LinkedList.get(int index) 访问每个节点。可以使用 LinkedList.size() 获取列表长度。这可能是使用“for”循环的好地方。

- Quasitonality