Having issues traversing Doubly Linked List in reverse

Question

I'm really struggling to fix my code for this. I've created a Doubly Linked list that I am trying to traverse in reverse.

Any ideas?

Here's my code: Node.java:

public class Node {
String data;
Node next;


public Node(String data) {
    super();
    this.data = data;
    this.next = null;
}

public String getData() {
    return data;
}

public void setData(String data) {
    this.data = data;
}

public Node getNext() {
    if (this.next != null)
        return this.next;
    else
        return null;
}

public void setNext(Node a) {
    this.next = a;
}

@Override
public String toString() {          //CHECK
    if(data== null){
        return "null";
    }
    else
        return data  + "-->";
}

}

Here's the second class "DNode.java":

public class DNode extends Node {

Node prev;

public DNode(String data) {
    super(data);
    this.prev = null;
}

public Node getPrev() {
    return prev;
}

public void setPrev(Node prev) {
    this.prev = prev;
}

}

Lastly, here is DoublyLinkedList.java: (Overrides "add" and "remove" methods from another class "Linked List")

public class DoublyLinkedList extends LinkedList {

DNode head, tail,current; 

public DoublyLinkedList() {

    this.head = this.tail = this.current = null; 
}



public void add(DNode a) {   //CHECK
    if (this.head == null) {
        this.head = tail = current= a;
        this.head.prev = null;
    }
    else{
        //a.setPrev(this.current);
        this.current.next= a;
        a.setPrev(this.current);
        this.current = this.tail = a;
    }
}
@Override
public void remove(String removestring) { 
    this.current = head;
    this.current.prev = head;
    while (this.current.getData() != removestring) {

        if (this.current.next == null) {

            System.out.println("not found");
            return;
        } else {
            this.current.prev = this.current;
            this.current = (DNode) current.next;
        }
    }
    if (this.current == head) {

        head = (DNode) head.next;

    } else {
        this.current.prev.next = (DNode) this.current.next;

    }
}



public void printList() {
    DNode temp = this.head;
    while (temp != null) {
        System.out.println(temp);
        temp = (DNode) temp.getNext();
    }

}

    public void reverseList(){
            this.current = this.tail;
    this.current.setNext(this.current.getPrev());
    this.current.setPrev(null);
    this.current = (DNode) this.current.getNext();


    while(this.current.getPrev()!= null){
        if(this.current.getNext() == null){
            this.current.setNext((this.current).getPrev()); 
            this.current.setPrev(null);
            this.current = (DNode)this.current.getNext();
        }
        else{
            DNode tempprev = (DNode) this.current.getNext();
            this.current.setNext(this.current.getPrev()); 
            this.current.setPrev(tempprev);
            this.current = (DNode) this.current.getNext();
        }
        DNode temp2 = this.tail;
        this.head = this.tail;
        this.tail = temp2;
    }

}

I'm able to print the list going forwards, but going backwards I am running into an infinite loop. Any ideas?

Thanks!

Answer 1

Well, we already have a method to go forwards. Because this is doubly linked, we can just convert this code line by line and instead of moving next (forwards) we move previous (backwards). We also start at the tail instead of the head.

Whereas this was your old method for printing forwards:

public void printList() {
    DNode temp = this.head;
    while (temp != null) {
        System.out.println(temp);
        temp = (DNode) temp.getNext();
    }

}

This could be your new method for printing backwards:

public void printBackwardsList() {
    DNode temp = this.tail;
    while(temp != null) {
        System.out.println(temp);
        temp = (DNode) temp.getPrev();
    }
}

Notice how they are almost exactly the same, except we swapped out tail for head and getNext for getPrev.

Answer 2

Your class model seems overly complex. You don't need a DNode class at all to do this. Your method to print the list in reverse should be as simple as the method to print the list normally

public void printListReverse() {
    Node temp = this.tail;
    while (temp != null) {
        System.out.println(temp);
        temp = temp.getPrevious();
    }
}

assuming you build and maintain the list properly.

Answer 3

while(this.current.getPrev()!= null)

replace with

while(this.current.getPrev()!= head)