Trouble tracing reverse function for doubly inked list

Question

I have a complete working method to reverse a doubly linked list. To be honest I've been going back and fourth for months trying to trace this code to see exactly how it works but I get confused at the end of the while look when I update my current node with current.prev

Ive tried to print out the values of the nodes for each time it changes the next and previous pointers however I get a nullpointerexception, so no luck there.

public void reverse(){
    Node temp  = null;
    Node current = head; 

    while(current != null){
        temp = current.prev;
        current.prev = current.next;
        current.next = temp;
        current = current.prev;
    }

    if(temp != null){
        head = temp.prev;
    }
}

There are no errors here, I passed it thru my own test cases for the worst and best scenario. I just can't seem to understand what is going on. I know this is essentially swapping the next and prev pointers but I need to know how.

so, your problem is the NullPointerException? Saying "there are no errors here" is not really true, considering an Exception is thrown. — Stultuske, Aug 21 '19 at 06:04
So the this exception is thrown if I try to trace by using System.out.print() because at at some points the value is null and won't allow me to print them. otherwise, if I try something like node.next.next.next or node.prev.prev.prev and any point it tells me that the list is a doubly linked list and don't lose nodes when reversing it. — cslol, Aug 21 '19 at 06:10
Then today would be a good day to learn. Your debugger lets you step through your program line by line, and see the values of every variable at each point. It's perfect for situations like this. If you're going to become a professional programmer, your debugger will save you literally YEARS of time, over the course of your career. — Dawood ibn Kareem, Aug 21 '19 at 19:34

score 0 · Answer 1 · answered Aug 21 '19 at 06:16

public void reverse(){
// Create initial values
Node temp  = null;
// Note that you are using current to traverse through the linked list
Node current = head; 

// While current is not at the end of the original (non-reversed) list
while(current != null){
    // Swapping prev and next
    temp = current.prev; // temp 'temporarily' holds copy of current.prev
    current.prev = current.next; // current.prev is overwritten with current.next
    current.next = temp; // current.next is overwritten with temp (containing original current.prev)
    // You are setting current to the newly redefined prev
    // This was equal to current->next in the original (non-reversed) list
    // So you are traversing through the original list
    // Anything 'before' this has already been reversed
    // Anything 'after' still needs to be reversed
    current = current.prev;
}

// Condition checks for edge case of a one node linked list
if(temp != null){
    // Set the head of the reversed list
    head = temp.prev;
}

Commented code above. I'm not a Java programmer, but in C I would print out the addresses of each node before and after the reversal to check I am doing things properly. Perhaps, you can use hashcodes to do something similar?

score 0 · Answer 2 · answered Aug 21 '19 at 06:18

This is similar to a swap in Java:

  while(current != null){
        temp = current.prev;  //gets the 'end' of the doubly linked list
        current.prev = current.next; //sets the 'end' of the doubly linked list to the 'first' of the list
        current.next = temp;  //sets the 'first' of the list to temp, which is the 'end' of the list
        current = current.prev;  //iterate through the list in reverse order (similar to i++ in for loops)
    }

 if(temp != null){
        head = temp.prev;  //edge case when there is only 1 node.
    }

Trouble tracing reverse function for doubly inked list

2 Answers2