java - 双链表删节点老是失败

Question

节点类

public class BidirectionalNode<Item> {

    private BidirectionalNode<Item> previous;
    private Item item;
    private BidirectionalNode<Item> next;
    
    public BidirectionalNode() {
        super();
        // TODO Auto-generated constructor stub
    }

    public BidirectionalNode(BidirectionalNode<Item> previous, Item item, BidirectionalNode<Item> next) {
        super();
        this.previous = previous;
        this.item = item;
        this.next = next;
    }

    public BidirectionalNode<Item> getPrevious() {
        return previous;
    }

    public void setPrevious(BidirectionalNode<Item> previous) {
        this.previous = previous;
    }

    public Item getItem() {
        return item;
    }

    public void setItem(Item item) {
        this.item = item;
    }

    public BidirectionalNode<Item> getNext() {
        return next;
    }

    public void setNext(BidirectionalNode<Item> next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "BidirectionalNode [previous=" + previous + ", item=" + item + ", next=" + next + "]";
    }
    
}

双链表类

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @author 
 *
 * @param <Item>
 */
public class DoubleLinkedList<Item> implements Iterable<Item> {
    private BidirectionalNode<Item> first, last;
    private int n;

    public DoubleLinkedList() {
        super();
        first = null;
        last = null;
        n = 0;

    }

    public boolean isHadNode(BidirectionalNode node) {

        BidirectionalNode<Item> nowNode = first;
        for (int i = 1; i < n; i++) {
            if (nowNode.equals(node)) {
                return true;

            } else {
                nowNode = nowNode.getNext();
            }
        }
        throw new NoSuchElementException("can't find this node!");
    }

    /**
     * 在表头插入结点
     * 
     * @param item
     */
    public void insterAtFirst(BidirectionalNode<Item> newNode) {
        // 插入需要判断两种情况，一种链表不为空，一种链表为空
        if (first != null) {
            // 不为空，则原first放置到新first的后面
            // change operater
            BidirectionalNode<Item> oldFirst = first;
            // init to firstNode
            first = newNode;
            first.setPrevious(null);
            first.setNext(oldFirst);
            oldFirst.setPrevious(first);
            n++;
        } else if (first == null) {
            // 如果链表为空。那么它就是唯一的结点——首结点是它，尾结点也是它。
            first = newNode;
            last = newNode;
            n++;
        }
    }

    /**
     * 在表尾插入结点
     * 
     * @param item
     */
    public void insertAtLast(BidirectionalNode<Item> newNode) {
        // 还是要考虑两个情况，链表是否为空
        if (last != null) {
            // TODO 这里还要判断一个元素的情况下...
            BidirectionalNode<Item> oldLast = last;
            last = newNode;
            last.setPrevious(oldLast);
            last.setNext(null);
            oldLast.setNext(last);
            n++;
        } else if (first == null) {
            // 如果链表为空。那么它就是唯一的结点——首结点是它，尾结点也是它。
            first = newNode;
            last = newNode;
            n++;
        }
    }

    /**
     * 从表头删除结点
     */
    public void deleteAtFirst() {
        // 如果为空，则不能正常删除，抛出异常
        if (first == null) {
            throw new NoSuchElementException("DoubleLinkedList is Empty");
        }
        if (n == 1) {
            first = null;
            last = null;
        } else {
            BidirectionalNode<Item> oldFirst = first;
            first = oldFirst.getNext();
            first.setPrevious(null);
            // 释放掉oldFirst
            oldFirst = null;
            n--;
        }
    }

    /**
     * 从表尾删除结点
     */
    public void deleteAtLast() {
        if (first == null) {
            throw new NoSuchElementException("DoubleLinkedList is Empty");
        }
        if (n == 1) {
            first = null;
            last = null;
        } else {
            BidirectionalNode<Item> oldLast = last;
            last = oldLast.getPrevious();
            last.setNext(null);
            // 释放掉oldLast
            oldLast = null;
            n--;
        }
    }

    /**
     * 在指定结点前插入
     * 
     * @param node
     * @param newNode
     */
    public void insertBefore(BidirectionalNode<Item> node, BidirectionalNode<Item> newNode) {
        if (first == null) {
            throw new NoSuchElementException("DoubleLinkedList is Empty");
        }
        // 判断是否有这个节点
        isHadNode(node);
        // 判断：只有一个结点
        if (n == 1) {
            first.setPrevious(newNode);
            newNode.setNext(first);
            n++;
        } else {

            // 处理前面的指向
            newNode.setPrevious(node.getPrevious());
            node.getPrevious().setNext(newNode);
            // 处理后面的指向
            newNode.setNext(node);
            node.setPrevious(newNode);
            n++;
        }
    }

    /**
     * 在指定结点后插入
     * 
     * @param node
     * @param newNode
     */
    public void insertAfter(BidirectionalNode<Item> node, BidirectionalNode<Item> newNode) {
        if (first == null) {
            throw new NoSuchElementException("DoubleLinkedList is Empty");
        }
        isHadNode(node);
        // 判断：只有一个结点
        if (n == 1) {
            newNode.setPrevious(first);
            first.setNext(newNode);
            n++;
        } else {
            // 处理后面的指向
            newNode.setNext(node.getNext());
            node.getNext().setPrevious(newNode);
            // 处理前面的指向
            newNode.setPrevious(node);
            node.setNext(newNode);
            n++;
        }
    }

    /**
     * 删除指定结点
     * 
     * @param node
     */
    public void deleteNode(BidirectionalNode<Item> node) {
        if (first == null) {
            throw new NoSuchElementException("DoubleLinkedList is Empty");
        }
        isHadNode(node);
        if (n == 1) {
            first = null;
            last = null;
            n--;
        } else {
            if (!first.equals(node)) {
                node.getPrevious().setNext(node.getNext());
            }
            if (!last.equals(node)) {
                node.getNext().setPrevious(node.getPrevious());
            }
            BidirectionalNode<Item> nowNode = first;
            for (int i = 1; i < n; i++) {
                if (nowNode.equals(node)) {
                    nowNode = null;
                    break;
                } else {
                    nowNode = nowNode.getNext();
                }
            }
            n--;
        }
    }



    public boolean isEmpty() {
        return first == null;
    }

//忽略一些没用的代码...


}

测试代码

        DoubleLinkedList<String> dll = new DoubleLinkedList<String>();
        BidirectionalNode<String > nb1 = new BidirectionalNode<String>(null,"a",null);
        BidirectionalNode<String > nb2 = new BidirectionalNode<String>(null,"b",null);
        BidirectionalNode<String > nb3 = new BidirectionalNode<String>(null,"c",null);
        BidirectionalNode<String > nb4 = new BidirectionalNode<String>(null,"d",null);
        BidirectionalNode<String > nb11 = new BidirectionalNode<String>(null,"aa",null);
        BidirectionalNode<String > nb22 = new BidirectionalNode<String>(null,"bb",null);
        dll.insterAtFirst(nb1);
        dll.insertAtLast(nb2);
        dll.insterAtFirst(nb3);
        dll.insertAtLast(nb4);
        dll.insertBefore(nb1, nb11);
        dll.insertAfter(nb2, nb22);
        dll.deleteNode(nb3);

一直没搞搞懂 deleteNode为什么删除不成功，里面的元素还是没有被删减，n倒是减了。感觉是基础语法的问题。。

Answer 1

    public void deleteNode(BidirectionalNode<Item> node)
    {
        if (first == null){
            throw new NoSuchElementException("DoubleLinkedList is Empty");
        }
        isHadNode(node);
        if (n == 1){
            first = null;
            last = null;
        }
        else{
            if (first == node){
                first = first.getNext();
                first.setPrevious(null);
            }
            else if (last == node){
                last = last.getPrevious();
                last.setNext(null);
            }
            else{
                node.getPrevious().setNext(node.getNext());
                node.getNext().setPrevious(node.getPrevious());
            }
        }
        n--;
    }

Answer 2

for (int i = 1; i < n; i++) {
 if (nowNode.equals(node)) {
    nowNode = null;
    break;
 } else {
    nowNode = nowNode.getNext();
 }
}
n--;

Écrivez simplement n-- devant break et vous saurez. Puisque lorsqu'un paramètre de référence de fonction est passé, la référence elle-même est copiée, donc nowNode.equals(node) ne sera jamais true. Je ne connais pas très bien Java. Il devrait y avoir une méthode de transmission de paramètres appelée out ou ref.

De plus, votre façon de supprimer simplement le nœud pointant vers null n'est pas du tout correcte, car dans ce cas, votre liste chaînée sera rompue.