method to reverse doubly linked list

  • (2 Pages)
  • +
  • 1
  • 2

22 Replies - 7536 Views - Last Post: 03 March 2011 - 07:20 PM Rate Topic: -----

#1 <3DIC  Icon User is offline

  • D.I.C Regular


Reputation: 6
  • View blog
  • Posts: 327
  • Joined: 06-October 10

method to reverse doubly linked list

Posted 28 February 2011 - 09:37 AM

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 

Is This A Good Question/Topic? 0
  • +

Replies To: method to reverse doubly linked list

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,479
  • Joined: 27-December 08

Re: method to reverse doubly linked list

Posted 28 February 2011 - 09:38 AM

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
Was This Post Helpful? 1
  • +
  • -

#3 <3DIC  Icon User is offline

  • D.I.C Regular


Reputation: 6
  • View blog
  • Posts: 327
  • Joined: 06-October 10

Re: method to reverse doubly linked list

Posted 28 February 2011 - 09:41 AM

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
  }

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,479
  • Joined: 27-December 08

Re: method to reverse doubly linked list

Posted 28 February 2011 - 09:43 AM

You aren't creating a new Node (there is no new Node() syntax), just using a variable to reference an existing Node.
Was This Post Helpful? 1
  • +
  • -

#5 <3DIC  Icon User is offline

  • D.I.C Regular


Reputation: 6
  • View blog
  • Posts: 327
  • Joined: 06-October 10

Re: method to reverse doubly linked list

Posted 28 February 2011 - 09:48 AM

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

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,479
  • Joined: 27-December 08

Re: method to reverse doubly linked list

Posted 28 February 2011 - 09:49 AM

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.
Was This Post Helpful? 1
  • +
  • -

#7 <3DIC  Icon User is offline

  • D.I.C Regular


Reputation: 6
  • View blog
  • Posts: 327
  • Joined: 06-October 10

Re: method to reverse doubly linked list

Posted 02 March 2011 - 10:33 PM

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?
Was This Post Helpful? 0
  • +
  • -

#8 Dogstopper  Icon User is online

  • The Ninjaducky
  • member icon



Reputation: 2870
  • View blog
  • Posts: 11,023
  • Joined: 15-July 08

Re: method to reverse doubly linked list

Posted 03 March 2011 - 03:18 AM

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.
Was This Post Helpful? 1
  • +
  • -

#9 <3DIC  Icon User is offline

  • D.I.C Regular


Reputation: 6
  • View blog
  • Posts: 327
  • Joined: 06-October 10

Re: method to reverse doubly linked list

Posted 03 March 2011 - 07:54 AM

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.
Was This Post Helpful? 0
  • +
  • -

#10 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8325
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: method to reverse doubly linked list

Posted 03 March 2011 - 04:17 PM

View Post<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

Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,479
  • Joined: 27-December 08

Re: method to reverse doubly linked list

Posted 03 March 2011 - 05:13 PM

View Postmacosxnerd101, 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.
Was This Post Helpful? 0
  • +
  • -

#12 <3DIC  Icon User is offline

  • D.I.C Regular


Reputation: 6
  • View blog
  • Posts: 327
  • Joined: 06-October 10

Re: method to reverse doubly linked list

Posted 03 March 2011 - 06:12 PM

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);
       
  
}
Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,479
  • Joined: 27-December 08

Re: method to reverse doubly linked list

Posted 03 March 2011 - 06:14 PM

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.
Was This Post Helpful? 0
  • +
  • -

#14 <3DIC  Icon User is offline

  • D.I.C Regular


Reputation: 6
  • View blog
  • Posts: 327
  • Joined: 06-October 10

Re: method to reverse doubly linked list

Posted 03 March 2011 - 06:35 PM

Why does it matter which way i traverse the list?

not sure what condition i would even check to accomplish this
Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,479
  • Joined: 27-December 08

Re: method to reverse doubly linked list

Posted 03 March 2011 - 06:37 PM

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.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2