问题：

双链表Java删除方法不适用于除头节点以外的任何节点

史超英

2023-03-14

除了删除方法之外，我的所有方法都可以工作。虽然它只在要移除的节点是头部时起作用，但对于头部之后要移除的任何其他节点都不起作用。经过几个小时的调试，我发现删除头部以外的东西只有在引用“头部”本身时才起作用（不是通过将头部值存储在变量中），如head.next、head.next.next等。但是像curNode.next.prev=curNode.prev这样的语句似乎根本不会改变列表的顺序。下面附上了我的整个双链接类以及节点类，以及我用来检查代码的主要方法。

双链接节点类

public class DLNode {
    Object data;
    DLNode next;
    DLNode prev;

    DLNode(Object o) {
        data = o;
        next = null;
        prev = null;
    }
    public String toString() {
        return "[" + data + "]";
    }

}

双链表类

public class DLList {
    DLNode head;
    DLList(){
        head = null;
    }
    public void append(DLNode newNode) {
        if (head == null ) {
            head = newNode;
        }
        else {
            DLNode curNode = head;
            while (curNode.next != null) {
                curNode.prev = curNode;
                curNode = curNode.next;             
            }
            curNode.next = newNode;
            curNode.prev = newNode.prev;
        }

    }
    public void prepend(DLNode newNode) {
        if (head == null) {
            head.prev = newNode;
            head = newNode;
            newNode.prev = null;
        }
        else {
            DLNode n = head;
            head.prev = newNode;
            head = newNode;
            newNode.next = n;
            newNode.prev = null;

        }
    }
    public void insertAfter(DLNode curNode, DLNode newNode) {
        DLNode sucNode = head.next;
        if (head == null) {
            head = newNode;
        }
        else {
            sucNode = curNode.next;
            newNode.next = sucNode;
            newNode.prev = curNode;
            curNode.next = newNode;
            sucNode.prev = newNode;
        }

    }
    public void remove(DLNode curNode) {
        DLNode sucNode = curNode.next; //these variables don't seem to work without
        DLNode predNode = curNode.prev; //the head node directly referenced
        if (head == null) {
            curNode = null;
        }
        else if (curNode == head) { //only block that works
            head = sucNode;
        }
        else if (sucNode != null) {
            sucNode.prev = predNode; //where the problem is apparently
        }
        else if (predNode != null) {
            predNode.next = sucNode;
        }

    }
    public DLNode search(Object key) {
        DLNode curNode = head;
        while (curNode != null) {
            if (curNode.data == key) {
                return curNode;
            }
            curNode = curNode.next;
        }
        return curNode;
    }

    public void insertAfterNew(DLNode curNode, DLNode newNode) {
        DLNode sucNode = head.next;
        if (head == null) {
            head = newNode;
        }
        else if (curNode == null) {
            newNode.next = sucNode;
            head = newNode;
            sucNode.prev = newNode;
        }
        else {
            sucNode = curNode.next;
            newNode.next = sucNode;
            newNode.prev = curNode;
            curNode.next = newNode;
            sucNode.prev = newNode;
        }
    }

    public String toString() {
        String finalString = "X<-";
        DLNode curNode = head;
        if (head == null) {
            return "X";
        }
        while (curNode != null) {
            if (curNode.next == null) {
                finalString += curNode;
                curNode = curNode.next;
            }
            else {  
                finalString += curNode + "<=>";
                curNode = curNode.next;
            }
        }
        return finalString + "->X";
    }
    }

测试类与主

public class TestList {
    static final int N = 4;

    public static void main(String[] args) {
        testDLList();
    }

    static void testDLList() {

        System.out.println("Doubly-Linked List");

        DLList list2 = new DLList();

        for (int i = 0; i < N; i++) 
            list2.append(new DLNode(i));
        for (double d = N; d < 2 * N; d++)
            list2.append(new DLNode(d));

        System.out.println(list2);

        DLNode temp = list2.search(1); //remove works when the value in search is 0
        System.out.println(temp); // since 0 is head, but not with other values in list

        list2.insertAfter(temp, new DLNode(2000));
        System.out.println(list2);

        list2.remove(temp);
        System.out.println(list2);

        System.out.println();
    }

共有2个答案

汪坚

2023-03-14

问题出在你的append中。我已经评论了要删除的行的原因，也添加了一些。

public void append(DLNode newNode) {
    if (head == null ) {
        head = newNode;
    }
    else {
        DLNode curNode = head;
        while (curNode.next != null) {
           // curNode.prev = curNode; Shouldn't be updating the prev when traversing
            curNode = curNode.next;     //Traverse         
        }
        curNode.next = newNode;
        newNode.prev = curNode;
        //curNode.prev = newNode.prev; This also must be removed. This cuts off the nodes from the list
    }
 }

解鸿运

2023-03-14

你必须应用user7的答案和我在评论中提出的建议。

public void append(DLNode newNode) {
    if (head == null ) {
        head = newNode;
    }
    else {
        DLNode curNode = head;
        while (curNode.next != null)
            curNode = curNode.next; 
        curNode.next = newNode;
        newNode.prev = curNode;
    }

}

public void remove(DLNode curNode) {
    DLNode sucNode = curNode.next;
    DLNode predNode = curNode.prev;
    if (sucNode != null)
        sucNode.prev = predNode;
    if (predNode != null)
        predNode.next = sucNode;
    else if (curNode == head)
        head = sucNode;
    else
        throw new IllegalArgumentException();

}

有关append（）更改的解释，请参见user7的回答。至于删除（），有四种情况：

如果列表看起来像predNode

fixedremove（）方法正确处理这四种情况，并在predNode==null时检查curNode==head。

您的insertAfter（）也已损坏。首先，head==null检查是无用的，因为head。next将始终在到达head==null检查之前抛出NullPointerException。我不太确定我是否遵循了预期的逻辑，但这里有一个固定的版本和解释：

public void insertAfter(DLNode curNode, DLNode newNode) {
    DLNode sucNode;

    if (curNode == null) {
        sucNode = head;
        head = newNode;
    } else {
        sucNode = curNode.next;
        curNode.next = newNode;
    }
    newNode.prev = curNode;

    newNode.next = sucNode;
    if (sucNode != null)
        sucNode.prev = newNode;
}

如果列表为空，即curNode==null

由于head.prev将始终在head==null分支中抛出一个NullPointerExcture，因此您的preend（）也被破坏了。头！=null分支正常工作，但使用了不必要的临时变量。这里有一个固定的版本：

public void prepend(DLNode newNode) {
    if (head == null) {
        newNode.next = null;
        head = newNode;
        newNode.prev = null;
    } else {
        head.prev = newNode;
        newNode.next = head;
        newNode.prev = null;
        head = newNode;
    }
}

类似资料：

删除双链表中的节点(C++)

这是我的remove函数，用于删除具有元素的节点。我得到了一个seg错误，我很确定这是因为temp->prev是前面的哨兵，所以从技术上来说，它不在双链表中。如果这是正确的，我实际上如何防止这种情况？如有任何帮助，不胜感激。编辑：刚刚更新了代码，但仍然出现了Seg错误
链表（删除节点）

我的问题是，如果用户输入一个姓氏，并且在链接列表中有多个相同的姓氏，并且其中一个姓氏在head节点中。如何在不删除头部节点的情况下删除另一个姓氏。我尝试了一些我能想到的方法，但是删除了所需的节点（这很好），包括头部节点（这不是我想要的…）
从循环双链表（Java）中删除节点？

我理解得对吗？（从虚拟节点开始） dummy->a->b->c->d->dummy（环绕到dummy节点）因此，如果我想删除第一个实际的数据段(A)，我需要将它分配给一个临时变量。所以Node first=head.next。然后我需要有一个虚拟的头部引用“B”，所以我需要做head.next=first.next。这就是所有需要做的吗？在从列表中删除任何节点N的情况下（假设它在列表中），这是
Java删除节点链表不工作

我有一种工作方法，可以在给定键的情况下删除链表中的节点。那时我将节点类嵌套在LinkedList类中，可以直接访问节点类的成员（例如head.next和head.data）。我对代码进行了重构，使其具有一个单独的节点类，并为数据和下一个成员设置了访问器和mutator方法。（我正在准备面试，所以我正在处理许多linkedlist问题，所以我认为有一个单独的类可以让我不必复制和粘贴很多代码。这是我
如何删除双向链表中的备用节点？

我写了下面的代码，但它在执行create（）函数后停止工作。我想从头节点开始删除替代元素。我的delete_Alt（）函数正确吗？请告诉我哪里错了。
如何删除双链接列表中的节点

我有麻烦删除双向链表中的节点，程序崩溃，我不能解决这个问题。你能帮我吗？这是创建新节点，查看它们并删除它们的完整代码。我认为这个问题与Node del的scanf（）有关，但我不确定。当我只是通过或

双链表Java删除方法不适用于除头节点以外的任何节点

共有2个答案

相关问答

相关文章

相关阅读

相关工具

相关文档