java - Reversing a Doubly Linked List

Question

This method right below reverses a doubly linked list with n elements. I dont understand how this really works. I have added comments, please correct me if I am wrong. I am not sure how the traversing process works.

 public void reverseDLL( ) {
   Node temp=head; //swap head and tail
   head=tail; // head now points to tail
   tail=temp; //tail points to head
    //traverse the list swapping prev and next fields of each node
  Node p=head; //create a node and point to head

  while(p!=null) //while p does not equal null
    { //swap prev and next of current node
      temp=p.next; // p.next does that not equal null? confusing.
      p.next=p.prev; //this line makes sense since you have to reverse the link
      p.prev=temp; //having trouble visualizing this.
      p=p.next;//advance current node which makes sense
    }
 }

Answer 1

Let's try stepping through the code a few lines at a time.

Node temp=head;
head=tail;
tail=temp;

Here we are just setting up some variables. We are swapping our head to point to the tail and the tail to the head.

Now we define our starting node. This is our new head that used to be the tail.

Node p=head; //create a node and point to head

while(p!=null)
{ 
    temp=p.next; 

At this point, this is what we are looking at (note: if this is the first iteration, next would point to null but that doesn't matter, just assume A is null for that case):

So we have next pointing to A and prev pointing to B. We want these to be swapped. To do so, we go ahead and assign next to prev (which points to B) so now next and prev both point to B.

    p.next=p.prev; 

Great! We're half way there. Now we have:

Now our last step is to have prev point to what next used to point to. How are we going to get to it? Luckily, we stored what next used to point to (in other words, A) in temp. So let's use that to assign prev.

    p.prev=temp; 

Alas, we have:

Now this node has been swapped, and we move on to the next.

    p=p.next;
}

Rinse and repeat.

All together:

Node p=head; //create a node and point to head

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