Застрял в петле - PullRequest
Новая
       20

Застрял в петле

2 голосов
/ 11 июля 2009

Я пытаюсь реализовать свою собственную систему List в 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;
}

Но это не будет благоприятно для памяти огромных списков. Дайте мне знать, если вы можете определить проблему!

Ответы [ 5 ]

3 голосов
/ 11 июля 2009

Проблема в том, что ваш список поврежден. В точке, где у вас есть 2 элемента в списке, это выглядит примерно так:

  1. Список {info = Node (5,6), prev = null, next = 2}
  2. Список {info = Node (1,3), prev = 2, next = null}

Woops, обратите внимание, что второй элемент в поле prev списка указывает на себя? Ваша проблема в этом методе: 

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

В этой строке ref.last () - это метод, который циклически просматривает последний элемент в списке, ref. Однако последний элемент не соответствует ожидаемому, поскольку предыдущая строка выглядит следующим образом: 

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

То, что вы хотите найти, это последний элемент, который был бы до , вы устанавливаете его следующее поле, добавляя новый список в конце. Однако, снова вызвав метод last , вы обнаружите последний элемент new после добавления нового списка. Вот почему его последний узел в конечном итоге указывает на себя.

Измените метод 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 . Похоже, это вызывает у вас всевозможные неприятные случаи, которые вам нужно проверить.

1 голос
/ 11 июля 2009

Ваш код содержит большой потенциал для бесконечных циклов. Попробуйте переписать код, который выглядит как 

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

до 

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

как можно больше.

Также убедитесь, что next последнего элемента вашего List никогда не будет указывать на первый элемент вашего List, или вы действительно будете бегать кругами в течение длительного времени .

1 голос
/ 11 июля 2009

Возможно, вы используете == для объектов. 

if(ref.info() == o)

Даже если это не ваша проблема для вашего бесконечного цикла, это проблема, которую вам нужно решить.

0 голосов
/ 11 июля 2009

Я пытаюсь реализовать свою собственную систему List в Java.

Мое предложение, не надо. Вы должны повторно использовать встроенный список, который является стандартным и работает. Если вы хотите знать, как это работает, вы можете прочитать источник.

Знание того, как написать свою собственную реализацию List, может быть полезно в интервью, но я настоятельно рекомендую, чтобы вы никогда не делали этого на реальной работе!

0 голосов
/ 11 июля 2009

ваша проблема в 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 () всегда будет истинным, и он всегда ссылался на себя как на свой предыдущий, так что он будет постоянно повторять себя в ref = ref.prev(); строка.

...