Infinite iteration using self-writed LinkedList iterator

Question

I have problem with my self-writed double LinkedList. I have test program, which tests my idea and it runs infinitely. The problem is in method WyswietlListe() where condition !isDone() is always true. What is a problem with my isDome() method? I added stars near them to be found easier for you :)

public class Lista implements List {
private Element head = new Element(null); //wartownik
private int size; 
public Lista(){
    clear();
}

public void clear(){
    head.setPrevious(head);
    head.setNext(head);
    size=0;
}

public void insert(int index, Object value) throws IndexOutOfBoundsException {
   if (index<0 || index>size) throw new IndexOutOfBoundsException();
   Element element = new Element(value);
   element.wstawPrzed(getElement(index));
   ++size;
}

public Element getElement(int index) {
   Element szukany = head.getNext();
   for (int i=index; i>0; --i) 
       szukany = szukany.getNext();   
   return szukany;
}


 public Object get(int index) throws IndexOutOfBoundsException{
    if(index<0 || index>size) throw new IndexOutOfBoundsException();
    Element particular = head.getNext();
    for(int i=0; i <= index; i++)
        particular = particular.getNext();
    return particular.getValue();
}  

public boolean delete(Object o){
    if(head.getNext() == null) return false;
    if(head.getNext().getValue().equals(o)){
        head.setNext(head.getNext().getNext());
        size--;
        return true;
    }

    Element delete = head.getNext();
    while(delete != null && delete.getNext() != null){
        if(delete.getNext().getValue().equals(o)){
            delete.setNext(delete.getNext().getNext());
                            size--;
            return true;
        }
        delete = delete.getNext();
    }
    return false;
}

public int size(){
    return size;
}

public boolean isEmpty(){
    return size == 0;
}

 public void infoOStanie() {
    if (isEmpty()) {
      System.out.println("Lista pusta.");
  }
  else
  {
      System.out.println("Lista zawiera " + size() + " elementow.");
  }

}

public IteratorListowy iterator() {
    return new IteratorListowy();
}

**public void wyswietlListe() {
    IteratorListowy iterator = iterator();
    for (iterator.first(); !iterator.isDone(); iterator.next())
    {
        System.out.println(iterator.current());
    }
    System.out.println();
 }**

 private static final class Element{
    private Object value; 
    private Element next; //Referencja do kolejnego obiektu
    private Element previous; //Referencja do elementu poprzedniego

    public Element(Object value){ 
        setValue(value); 
      }

    public void setValue(Object value) {
        this.value = value;
    }

    public Object getValue() {
        return value;
    }

    //ustawia referencję this.next na obiekt next podany w atgumencie
    public void setNext(Element next) {
        if (next != null)
        this.next = next;
    }

    public Element getNext(){
        return next;
    }

    public void setPrevious(Element previous) {
        if (previous != null)
        this.previous = previous;
    }

    public Element getPrevious() {
        return previous;
    }

    public void wstawPrzed(Element next) {
        Element previous = next.getPrevious();
        setNext(next);
        setPrevious(previous);
        next.setPrevious(this);
        previous.setNext(this);
    } 

    public void delete() {
        previous.setNext(next);
        next.setPrevious(previous);
    }

}

private class IteratorListowy implements Iterator{
private Element current;

public IteratorListowy() {
   current = head;
} 

public void next() {
   current = current.next;
}   

public void previous() {
   current = current.previous;
}

**public boolean isDone() {
   return current.next == null;**
} 
public Object current() {
   return current.value;
}

public void first() {
   current = head.getNext();
}
}
}

and test:

public class Program {

public static void main(String[] args) {
  Lista lista = new Lista();
  Iterator iterator = lista.iterator();
  Student s1 = new Student("Kowalski", 3523);
  Student s2 = new Student("Polański", 45612);
  Student s3 = new Student("Karzeł", 8795);
  Student s4 = new Student("Pałka", 3218);
  Student s5 = new Student("Konowałek", 8432);
  Student s6 = new Student("Kłopotek", 6743);
  Student s7 = new Student("Ciołek", 14124);
  lista.insert(0, s1);
  lista.insert(0, s2);
  lista.insert(0, s3);
  lista.insert(0, s4);
  lista.insert(0, s5);
  lista.wyswietlListe();


  lista.infoOStanie();

  lista.clear();

  lista.infoOStanie();

}
}

Answer 1

The problem is with how you create the List. In your constructor, you call clear(), where you do that:

head.setPrevious(head);
head.setNext(head);

So, after that your list will be:

head |-next-> head
     |-previous-> head

After that, you will insert a new element (let's call it ele1), and call element.wstawPrzed(getElement(index));, which will do:

setNext(next);
setPrevious(previous);
next.setPrevious(this);
previous.setNext(this); 

So, after that your list will be:

head |-next-> ele1
     |-previous-> ele1

ele1 |-next-> head
     |-previous-> head

Let's insert ele2:

head |-next-> ele1
     |-previous-> ele2

ele1 |-next-> ele2
     |-previous-> head

ele2 |-next-> head
     |-previous-> ele1

And so on...

As you can see, next will never be null for any of your elements, and so, the condition current.next == null will never be true, and your loop will never stop.

What you can do:

• change the condition to current == head

• change the way you build the list so that next and previous can point to null.