双链表删节点老是失败

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

你把n--写到break前面你就知道了。由于函数引用参数传递时，引用本身是复制的，所以nowNode.equals(node)永远不会为true。java我不太熟悉，应该有种类似叫out或ref的参数传递方式。

另外，你这里只是把node指向null的删除方式根本不对，因为这样的话，你的链表就断掉了。