Stuck in a loop ! :o

Question

Hi. I'm trying to implement my own List system in Java.

the List class file :

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

And i was testing it out like this :

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

Now, everything is fine when i add the first two nodes. However, i go into an infinite loop when i call the count() AFTER i delete a node.

And after going through a lot of breakpoints, I've marked the place in the code where i get stuck. Apparently something is wrong in the delete() function. And either the fact that i haven't slept last two nights or I'm simply losing it, i cannot figure out what i'm doing wrong :(

For the time being, i've replaced my delete code with this :

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

But this wouldnt be memory-friendly for huge lists. Let me know if you can spot the problem!

-Thanks :D

Answer 1

Isn't delete nothing more then:

void delete(object toDelete) {
List current = prev;
while(true) {
if(current.info == toDelete) {
current.prev.next = current.next;
current.next.prev = current.prev;
return;
}
current = current.next;
}

Answer 2

It could be the fact that you are using == on Objects.

if(ref.info() == o)

Even if it isn't your exact problem for your infinite loop, it is a problem that you need to address.

Answer 3

Your code contains lots of potential for infinite loops. Try to rewrite code that looks like

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

to

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

as much as possible.

Also, make sure that that the next of the last element of your List will never point back to the first element of your List, or you'll be running around in circles for a long time indeed.

Answer 4

your problem is in 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;
    }

do this instead:

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

You were always adding the second item to the list and making it its own last. This way, when you deleted it, it would only perform the killNext operation on itself and your first node would be untouched. You would then return the self-referencing node back to your calling example, not a ref to what you thought should be the remaining list. When you called count() on that node, it would call first() and would get stuck in the loop because !isFirst() would always be true, and it was always referencing itself as its previous, so it would continually reassnging itself in the ref = ref.prev(); line.

Answer 5

The problem is that your list ends up corrupted. At the point where you have 2 items in the list, it looks something like this:

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

Woops, notice the second item in the list's prev field is pointing at itself? Your problem is in this method:

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

On that line, ref.last() is a method that loops through looking for the last item in the list, ref. However, the last item isn't what you expect it to be, because the previous line looks like this:

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

What you want to look for is the last item as it would have been before you set it's next field by appending the new list on the end. However, by calling the last method again, you're finding the new last item, after the new list has been appended. That's why its last node ends up pointing to itself.

Change your addList method to look like this:

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

...and it will work. By caching the reference to the end of the list before modifying it, you have the correct reference now.

Even so, your code is quite a bit more complicated than it has to be. You should look up an example of how to implement a double linked list and you will find examples that show you how to do it far simpler. Your delete method in particular is far too over-complicated.

I also think you have problems with representing the empty list as a node containing a null. That seems to be causing you to have all kinds of nasty edge cases you need to check for.

Answer 6

I'm trying to implement my own List system in Java.

My suggestion, don't. You should reuse the built in List which is standard and works. If you want to know how it work you can read the source.

Knowing how to write you own List implementation might be useful in interviews but I would strongly suggest you never do this in a real job!