[<3DIC]

I am trying to write a method to reverse the elements in a doubly linked list, without creating any new nodes or a new linked list. My method follows, but will this actually work? or am i going to have to loop through the linked list and use some of the provided methods?

public DList reverse(DList L) 
  {
	  L.tail = L.head;
	  L.head = L.tail;
	     
	  return L;
  } // end reverse 

[macosxnerd101]

You need a temp variable to hold one of the Nodes when swapping. As you have it now, if tail = head, then head == head. You want to do the following for a basic swap, regardless of whether you are working with Strings, numbers, or Nodes.
-temp <-- head
-head <-- tail
-tail <-- temp

[<3DIC]

I don't think i can create a temp. Here is what my directions say to do:

"Write a Java method to reverse the order of elements in a doubly linked list. (Do not create a new list, reverse the elements in the existing list. Do not allocate any new nodes.)"

I take that to mean that i cant create anything new.

But in the class that im adding this to - DList, the constructor says something about dummy nodes, could i use them somehow?

/** Constructor that creates an empty list */
  public DList() 
  { 
    size = 0;
    head = new DNode(null, null, null);	// create dummy head node
    tail = new DNode(null, head, null);	// create dummy tail node
    head.setNext(tail);	// make head and tail point to each other
  }

[macosxnerd101]

You aren't creating a new Node (there is no new Node() syntax), just using a variable to reference an existing Node.

[<3DIC]

So this should work? (i remember you said to test to see if methods work, but i have yet to write my test program, and that seems to be much more difficult than writing the method and asking for your expert advice )

public DList reverse(DList L) 
  {
	  DNode temp = L.head;
	  
	  L.head = L.tail;
	  
	  L.tail = temp;
	     
	  return L;
  } // end reverse

[macosxnerd101]

Looks good to me. The only other thing to be careful about is the placement of the next and prev Nodes in your Node class. When you reverse, treat the previous pointers as next, and vice versa. Perhaps your LinkedList class should manage this boolean, inverting it when you reverse.

[<3DIC]

Tried above code and it didnt work, i have since come up with this code:
but when i run it with the test program that follows i get some errors.

public void reverse()
  {
       DNode temp;
       DNode current = this.head;
       
       DNode previousNode1 = current.getPrev();
 	   DNode nextNode1 = current.getNext();
 	   
 	  temp = previousNode1;
   
       /* swap next and prev for all nodes of
         doubly linked list */
       while (current !=  null)
       {
         temp = previousNode1;
         
         //current->prev = current->next;
         previousNode1 = nextNode1;
         
       //current->next = temp;
         nextNode1 = temp;
         
         current = previousNode1;
       }      
   
       /* Before changing head, check for the cases like empty
          list and list with only one node */
       if(temp != null )
          this.head = previousNode1;
  }

Test program:

public class Lab5Test 
{
	public static void main(String[] args) 
	{
		DList myList = new DList();
		DList myList2 = new DList();
		
		myList.addFirst(new DNode("A", null, null));
		myList.addLast(new DNode("B", null, null));
		
		myList2.addFirst(new DNode("D", null, null));
		myList2.addLast(new DNode("E", null, null));
		myList2.addLast(new DNode("F", null, null));
		
		System.out.println("myList: " + myList.toString() + "\n");
		System.out.println("myList2: " + myList2.toString() + "\n");
		
		myList.reverse();
		
		System.out.println(myList);
		
	}

}

output / error messages:

myList: [A,B]

myList2: [D,E,F]

Exception in thread "main" java.lang.NullPointerException
	at DList.toString(DList.java:202)
	at java.lang.String.valueOf(Unknown Source)
	at java.io.PrintStream.println(Unknown Source)
	at Lab5Test.main(Lab5Test.java:23)

what is causing these errors?

[Dogstopper]

Why aren't you using the tail pointer? You know that head and tail ALWAYS exist in a LinkedList (unless head is null), however, you cannot guarantee that the next and previous nodes are...You should directly use the head and tail pointers when making the swap.

[<3DIC]

Dogstopper: do you mean change some part of my existing code? It sounds to me like your suggesting i try doing it like i did before:

public void reverse() 
  {
	  DNode temp = head;
	  
	  head = tail;
	  
	  tail = temp;
	     
  } // end reverse 

this code also throws a null pointer exception though.

[pbl]

<3DIC, on 03 March 2011 - 09:54 AM, said:

Dogstopper: do you mean change some part of my existing code? It sounds to me like your suggesting i try doing it like i did before:

public void reverse() 
  {
	  DNode temp = head;
	  
	  head = tail;
	  
	  tail = temp;
	     
  } // end reverse 

this code also throws a null pointer exception though.

NO !!
You have to do this in everynode
Since you are now an expert, after 30 replies, in how swapping nodes why don't you use your swap method to reverse form 0 to middle with last to middle ? I am still wondering if you understand the whole concept of previous/next

This post has been edited by pbl: 03 March 2011 - 04:18 PM

[macosxnerd101]

macosxnerd101, on 28 February 2011 - 11:49 AM, said:

Looks good to me. The only other thing to be careful about is the placement of the next and prev Nodes in your Node class. When you reverse, treat the previous pointers as next, and vice versa. Perhaps your LinkedList class should manage this boolean, inverting it when you reverse.

Re-read this post. Rather than swapping every Node, just use a boolean instance variable to tell your List which direction to go in. If true, previous points backwards and next forward. If false, then the List is reversed and previous points forward, and next backwards. This is an O(1) solution vs. the O(n) solution swapping all the Nodes.

[<3DIC]

macosxnerd101: im not quite sure what you mean.

pbl: i re-wrote my method i know its not complete but i think this is a good starting point. But i dont know what to do next. (this code has no errors but it does not reverse the entire list)

public void reverse()
  {
       DNode temp1 = head.getNext();
       DNode temp2 = tail.getPrev();
       
       swap(temp1, temp2);
       
  

}

[macosxnerd101]

Think of a doubly-linked list as a two-way road. You can either go to the store, or away from it. All the boolean does is tell you which direction you are going: toward the head/home, or towards the store/tail. If you are going towards the head, then you start at the tail and move through the previous Nodes (ie., the list is reversed). Otherwise, you start at home and go to the store. You are just describing what direction to travel rather than modifying the structure of the list.

[<3DIC]

Why does it matter which way i traverse the list?

not sure what condition i would even check to accomplish this

[macosxnerd101]

Because if you traverse the list in reverse order, that's easier than reversing the list. Like I said, just manage a boolean instance variable. When the reverse() method is invoked, just invert it. Based on the boolean, that should tell you the starting point for the List.