双链表 Java Remove 方法对头节点以外的任何节点都不起作用

Question

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

双向链接节点Class

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

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

}

双向链表Class

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";
    }
    }

使用 main

测试 Class

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

Answer 1

问题出在您的 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
    }
 }

Answer 2

您必须申请 together with the suggestions I made in 。

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() 更改的解释，请参见用户 7 的回答。至于remove()，有四种情况：

如果列表看起来像 predNode <-> curNode <-> sucNode，即 predNode != null && sucNode != null，您需要设置 sucNode.prev = predNode 和 predNode.next = sucNode
如果列表看起来像 predNode <-> curNode，即 predNode != null && sucNode == null，您需要设置 predNode.next = null
如果列表看起来像 curNode <-> sucNode，即 predNode == null && sucNode != null，您需要设置 sucNode.prev = null 和 head = sucNode
如果列表看起来像 curNode，即 predNode == null && sucNode == null，您需要设置 head = null

固定的 remove() 方法正确处理了这四种情况，并且在 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 == null，则需要设置newNode.prev = null、newNode.next = null、head = newNode
如果newNode要插入列表的头部，即curNode == null && head != null，则需要设置newNode.prev = null、newNode.next = head和head = newNode
如果newNode被附加到列表的尾部，即curNode != null && curNode.next == null，您需要设置newNode.prev = curNode、newNode.next = null和curNode.next = newNode
如果在两个节点之间插入newNode，即curNode != null && curNode.next != null，则需要设置newNode.prev = curNode、newNode.next = curNode.next和curNode.next = newNode

您的 prepend() 也已损坏，因为 head.prev 将始终在 head == null 分支中抛出 NullPointerException。 head != 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;
    }
}

双链表 Java Remove 方法对头节点以外的任何节点都不起作用

Doubly Linked List Java Remove method does not work for any node besides head node

java

linked-list

nodes

doubly-linked-list