陷入循环

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() 时，我会进入无限循环。

在经历了很多断点之后，我在代码中标记了我遇到困难的地方。 显然 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. 列表 { info = Node(5,6), prev = null, next = 2 }
2. 列表 { 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());

您想要查找的是最后一个项目，因为它在您设置它之前 em>next 字段，将新列表附加到末尾。 但是，通过再次调用 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;
}

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

即便如此，您的代码仍然比实际情况复杂得多。 您应该查找如何实现双链表的示例，您会发现一些示例向您展示如何更简单地实现它。 您的删除方法尤其过于复杂。

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

Answer 2

这可能是因为您在对象上使用了 == 。

if(ref.info() == o)

即使这不是您的无限循环的确切问题，这也是您需要解决的问题。

Answer 3

您的代码包含大量无限循环的潜力。 尝试

while (true) {
    // do something interesting
    if (someCondition)
        // go forward in the loop
    else
        break;
}

重写看起来像的

while (someCondition) {
    // do something interesting
    // go forward in the loop
}

尽可能

代码。 另外，请确保 List 最后一个元素的 next 永远不会指向 List 的第一个元素，否则您确实会兜圈子很长一段时间。

Answer 4

您的问题出在 addList: 中：

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

        List  ref = this;
        //you should get a reference to the original "last"
        ref.last().setNext(newList.first());
        newList.first().setPrev(ref.last());

        return ref;
    }

改为这样做：

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

您总是将第二个项目添加到列表中，并将其设为最后一个。 这样，当您删除它时，它只会对其自身执行 killNext 操作，并且您的第一个节点将保持不变。 然后，您会将自引用节点返回到您的调用示例，而不是对您认为应该是剩余列表的引用。 当您在该节点上调用 count() 时，它将调用 first() 并陷入循环，因为 !isFirst() 始终为 true，而且它是始终将自身作为其前一个引用，因此它会在 ref = ref.prev(); 行中不断重新定位自身。

Answer 5

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

我的建议是，不要。 您应该重用标准且有效的内置列表。 如果你想知道它是如何工作的，你可以阅读源代码。

了解如何编写自己的 List 实现可能在面试中很有用，但我强烈建议您永远不要在真正的工作中这样做！