java - 陷入循环

Question

我正在尝试用 Java 实现我自己的列表系统。

List 类文件:

package RoutingDemo.List;

/**
 * A 2-way Linked-List to store generic elements.
 *
 */
public class List   {

    /*
    Instance Variables
    ---------------------------------------------------------------------------
    */  
    /**
     * Reference to element.
     */
    private Object info;

    /**
     * Reference to previous NodeList instance.
     */
    private List prev;

    /**
     * Reference to next NodeList instance.
     */
    private List next;

    /*
    Constructors
    ---------------------------------------------------------------------------
    */
    /**
     * Creates a new empty list.
     */
    public List()   {
        prev = null;
        next = null;
        info = null;
    }


    /*
    Methods
    ---------------------------------------------------------------------------
    */  
    /**
     * Adds an element to the list.
     *
     * @param o Element to be added
     */
    public List add(Object o)   {
        if(info == null)    {
                info = o;
                prev = null;
                next = null;
                return this;
        }   else    {
                List temp = new List();
                temp.add(o);

                return addList(temp);
        }
    }


    /**
     * Appends an existing list to this list.
     *
     * @param newList List to be appended
     */
    public List addList(List newList)   {
        if(newList.info() == null)
                return this;

        List  ref = this;
        ref.last().setNext(newList.first());
        newList.first().setPrev(ref.last());

        return ref;
    }


    /**
     * Get number of elements in the list.
     *
     * @return number of elements in list
     */
    public int count()  {
        if(info == null)
                return 0;

        List ref = this.first();
        int count = 0;

        while(true) {
            count++;
            if(!ref.isLast())
                    ref = ref.next();  
                else
                    break;
        }           
        return count;
    }


    /**
     * Deletes an element from the list.
     *
     * @param o Element to be deleted
     * @return List which does NOT
     * contain element o
     */
    public List delete(Object o)    {
        if(info == null)
                return this;

        List ref = this.first();        

        while(true) {
            if(ref.info() == o) {
                    if(ref.isFirst() && ref.isLast())   {
                            ref = new List();
                            break;
                    }   else if(ref.isFirst())  {
                            ref = ref.next();
                            ref.killPrev();
                            break;
                    }   else if(ref.isLast())   {
                            /* *** THIS IS THE CASE THAT WILL BE CALLED FOR THIS TEST **** */
                            ref = ref.prev();
                            ref.killNext();
                            break;
                    }   else    {               
                            ref.prev().setNext(ref.next());
                            ref.next().setPrev(ref.prev());
                            ref = ref.prev();
                            break;
                    }
            }   else    {
                    if(!ref.isLast())
                            ref = ref.next();
                        else 
                            break;
            }
        }
        return ref;

    }


    /**
     * Moves to first element in List.
     *
     *
     * @return List pointing to first
     * element in list
     */
    public List first() {
        List ref = this;

        while(!ref.isFirst())   {
            /* *** STUCK HERE *** */
            ref = ref.prev();
        }

        return ref;
    }


    /**
      * Returns current list element.
      *
      * @return current list element
      */
    public Object info()    {
        return info;
    }


    /**
     * Checks whether list is empty.
     *
     * @return true, if list is empty
     * , false otherwise.
     */
    public boolean isEmpty()    {
            if(count() > 0)
                    return false;
                else
                    return true;
    }


    /**
     * Checks whether current element is the first element.
     *
     * @return true, if current element is
     * first element, false otherwise.
     */
    public boolean isFirst()    {
        if(prev == null)
                return true;
            else
                return false;
    }


    /**
     * checks whether current element is the last element.
     *
     * @return true, if current element is
     * last element, false otherwise
     */
    public boolean isLast() {
        if(next == null)
                return true;
            else
                return false;
    }


    /**
     * Cuts the list from next element.
     *
     *
     * @param l new link for current element
     */
    public void killNext()  {
        next = null;
    }


    /**
     * Cuts the list from previous element.
     *
     *
     * @param l new link
     */
    public void killPrev()  {
        prev = null;
    }


    /**
     * Moves to last element in List.
     *
     *
     * @return List pointing to last
     * element in list
     */
    public List last()  {
        List ref = this;

        while(!ref.isLast())    {
            ref = ref.next();
        }

        return ref;
    }


    /**
     * Moves to next element in List
     *
     *
     * @return List pointing to next
     * element in list
     */
    public List next()  {
        if(!isLast())
                return next;
            else
                return this;
    }


    /**
     * Moves to previous element in List
     *
     *
     * @return List pointing to previous
     * element in list
     */
    public List prev()  {
        if(!isFirst())
                return prev;
            else
                return this;
    }


    /**
     * Sets the next link
     *
     *
     * @param l new link for current element
     */
    public void setNext(List l) {
        next = l;
    }


    /**
     * Sets the prev link for current element
     *
     *
     * @param l new link
     */
    public void setPrev(List l) {
        prev = l;
    }
}

我是这样测试的:

    class Example   {
    Example()   {
        List nl = new List();
        nl = nl.add(new Node(5,6));
        System.out.println("" + nl.count());
        Node x = new Node(1,3);
        nl = nl.add(x);
        System.out.println("" + nl.count());
        nl = nl.delete(x);
        System.out.println("as" + nl.count());

    }
}

public class ListTest   {
    public static void main(String args[])  {
        new Example();
    }
}

现在，当我添加前两个节点时一切正常。但是，当我调用 count() after 删除一个节点时，我进入了无限循环。

在经历了很多断点之后，我在代码中标记了我卡住的地方。显然 delete() 函数有问题，我不知道我做错了什么。

目前，我已经用这个替换了我的 delete() 代码:

    public List delete(Object o)    {
    if(info == null)
            return this;

    List ref = this.first();        
    List temp = new List();

    while(true) {
        if(ref.info() != o)
                temp.add(ref.info());
        if(!ref.isLast())
                ref = ref.next();
            else
                break;
    }

    return temp;
}

但这对于巨大的列表来说不是内存友好的。如果您能发现问题，请告诉我!

Answer 1

问题是您的列表最终损坏了。当列表中有 2 个项目时，它看起来像这样:

1. List { info = Node(5,6), prev = null, next = 2 }
2. List { info = Node(1,3), prev = 2, next = null }

糟糕，注意到列表的 prev 字段中的第二项指向它自己了吗？你的问题出在这个方法中:

public List addList(List newList) {
    // ...
    newList.first().setPrev(ref.last()); // <-- here
}

在那一行，ref.last() 是一个循环查找列表中最后一项 ref 的方法。但是，最后一项不是您所期望的，因为前一行看起来像这样:

ref.last().setNext(newList.first());

您要查找的是最后一项，因为它在您通过在末尾附加新列表来将其设置为下一个 字段之前。但是，通过再次调用 last 方法，您将找到新的 最后一项，即在新列表被追加之后。这就是为什么它的最后一个节点最终指向它自己。

将您的addList 方法更改为如下所示:

public List addList(List newList)   {
    if(newList.info() == null)
                    return this;

    List ref = this;
    List last = ref.last();
    last.setNext(newList.first());
    newList.first().setPrev(last);

    return ref;
}

...它会起作用的。通过在修改之前将引用缓存到列表的末尾，您现在拥有正确的引用。

即便如此，您的代码还是比实际情况要复杂得多。您应该查看如何实现双链表的示例，您会发现示例向您展示了如何更简单地实现它。尤其是您的delete 方法过于复杂。

我还认为您在将空列表表示为包含 null 的节点时遇到了问题。这似乎导致您遇到各种需要检查的令人讨厌的边缘情况。