Referring to a Double Linked List

Question

This method, located below, reverses a doubly linked list with n elements. I do not understand how this works. I have added comments, please correct me if I am wrong. I'm not sure how the moving 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

Try executing the code a few lines at a time.

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

Here we just set up some variables. We exchange the head, pointing to the tail and tail to the head.

Now we define our starting node. This is our new head, which used to be a tail.

 Node p=head; //create a node and point to head while(p!=null) { temp=p.next; 

At this point, we will consider this (note: if this is the first iteration, next will point to zero, but it does not matter, just assume that for this case the value of N is zero):

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

  p.next=p.prev; 

Excellent! We are halfway there. Now we have:

Now our last step is to prev to indicate which next to point to. How do we get to this? Fortunately, we saved what next used to indicate (in other words, A) in temp . So let me use this to assign prev .

  p.prev=temp; 

Alas, we have:

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

  p=p.next; } 

Rinse and repeat.

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; } 

Answer 2

Hope this helps you.

 struct node* current = head; struct node* next; struct node* prev = NULL; while (current != NULL) //traverse the whole linked list { next = current->next; //temporarily store the next node current->next = prev; //now assign the prev!node to next of current node prev = current; //update the previous pointer current = next; //update the current pointer } 

Look at that number.

I hope you get it.

thanks

Answer 3

It simply replaces the previous and next pointers in each element of the list. So your comment is correct. The new pointer to the next chapter starts from zero. And it is copied to its previous pointer. Of course, as the head of the list, its background should be zero.

Vj shah's answer does the same only with different code.

Answer 4

The key to how this spread works is to see what a simple doubly linked list looks like before and after it is canceled. When you see what needs to happen to change the list, the method will be easier to understand.

Suppose you had Nodes , as in the first node, at 0:

 node 0 1 2 3 4 data ALIST next 1 2 3 4 null prev null 0 1 2 3 

Moving the nodes above starting at 0 gives the output: ALIST

Leaving the data of each of them node in place, you can cancel the list by replacing the prev and next node values ​​for each node:

 node 0 1 2 3 4 data ALIST next null 0 1 2 3 prev 1 2 3 4 null 

Moving the nodes above starting at 4 gives the result: TSILA

The code for this is simple, assuming you have a node class as such:

 public class Node { private char ch; private Node next; private Node prev; } public static Node reverse(Node trav) { Node swapped; while (trav != null) { swapped.next = trav.prev; swapped.prev = trav.next; trav = swap; trav = trav.prev; // it was swapped so you need to follow prev } return trav // return the new head node } 

Answer 5

 public void reverseList(){ Entry<E> refEntry = header.previous; for(int i = 0; i < size-1; i++){ Entry<E> first = header.next; first.next.previous = first.previous; first.previous.next = first.next; first.previous = refEntry; first.next = refEntry.next; refEntry.next.previous = first; refEntry.next = first; } refEntry.previous = header; } 

Basically, the algorithm supports pointer(refEntry) for the record, which will be the first item in the list after the spread.

The first list item is then removed in iterations and added after refEntry .

Answer 6

With the bidirectional header below, I understand. Does it help? Is it correct?

The loop can be broken when the current is one node behind the tail, but for simplicity, let it reach the tail. In addition, before starting the cycle, you must perform normal checks for a list of size 0 or 1.

 H 1 2 3 4 5 //current pointer at head * H 5 1 2 3 4 //bring current tail to the next of current pointer. Update current tail. * H 5 1 2 3 4 //advance current pointer to next * H 5 4 1 2 3 //bring current tail to the next of current pointer. Update current tail. * H 5 4 1 2 3 //advance current pointer to next * H 5 4 3 1 2 // and so on.. * H 5 4 3 1 2 * H 5 4 3 2 1 * H 5 4 3 2 1 * H 5 4 3 2 1 * H 5 4 3 2 1 //break out when current pointer is at the tail. * 

Answer 7

It can be run from the head of the node also for simplicity, otherwise the algorithm remains the same:

 Node currentNode=head; while(currentNode!=null){ Node temp = currentNode.next; currentNode.next=currentNode.prev; currentNode.prev=temp; currentNode=currentNode.prev; } 

Answer 8

My version without recursion that I wrote in Java The idea is behind: first reach the end of the list, mark this node as a new head, then start moving backwards by flipping connections / Links (further, backward) until you leave the node no longer.

  Node Reverse(Node head) { //If List is empty or having one node if (head == null || head.next == null) return head; //Else Node current = head; //First move to the end of list while (current.next != null) { current = current.next; } //Shift head at tail of list head = current; //Let the magic begin while (current != null) { Node prev = current.prev; current.prev = current.next; current.next = prev; current = prev; } return head; } 

Hope this helps.