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!

This is homework. My professor assigned it and later realized that it made little sense...we still have to do it though..it's been a pain — user2376566
– user2376566, Commented Dec 5, 2013 at 4:45

Vineet Kosaraju · Accepted Answer · 2013-12-05 04:48:43Z

4

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.

answered Dec 5, 2013 at 4:48

Vineet Kosaraju

5,8702 gold badges23 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user2376566 Over a year ago

This made things quite a bit easier. I just started learning about basic data Structures such as singly and doubly linked lists..I know this was a very basic question. Thanks for the answer!

Vineet Kosaraju Over a year ago

No problem, glad to help. Its very hard to think backwards, our minds aren't made that way but forwards is easy. Please press the green check mark to one of these three answers to tell others that it is the correct solution :)

jhurtado Over a year ago

@VineetKosaraju upvote for the friendly way to answer a very basic question.

Amir Afghani · Accepted Answer · 2013-12-05 04:48:05Z

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.

answered Dec 5, 2013 at 4:48

Amir Afghani

38.7k17 gold badges87 silver badges127 bronze badges

5 Comments

Vineet Kosaraju Over a year ago

I don't think his Node's have a getPrevious method and that is why he is using DNode.

Amir Afghani Over a year ago

Then he can add that method on Node

vandale Over a year ago

@AmirAfghani since this is homework, that most likely is not an option

Amir Afghani Over a year ago

Thats too bad - I'm sorry your teacher doesn't know how to model data. If it were me, I'd argue with the professor about the given classes

user2376566 Over a year ago

Thanks! It was just weird because of the extra unnecessary class.This is definitely a much simpler way of dealing with it.

Nihar · Accepted Answer · 2013-12-05 04:48:06Z

0

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

replace with

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

answered Dec 5, 2013 at 4:48

Nihar

5512 gold badges10 silver badges29 bronze badges

Collectives™ on Stack Overflow

Having issues traversing Doubly Linked List in reverse

3 Answers 3

3 Comments

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related