method to meld doubly linked lists

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

40 Replies - 3005 Views - Last Post: 04 March 2011 - 05:48 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 meld doubly linked lists

Posted 28 February 2011 - 12:28 PM

I am trying to write a method to meld doubly linked lists. The method will accept to doubly linked lists as parameters and will return a new doubly linked list that contains elements alternately from the two given doubly linked lists. If you run out of elements in one of the lists, then append the remaining elements of the other list to the new linked list.

The way im trying to do this is convert the Linked lists to strings with the provided toString method, then just use the given setElement method to build the new linked list. I think it will work this way, but i am having trouble with the syntax.

Method:

public DList meld(DList L, DList M) 
  {
	  L.toString();
	  M.toString();
	  
	  DList L2;
	  
	  L2.setElement(L.toString().charAt(0)); // this is where i am having trouble
	     
	  return L2;
  } // end meld


how can i fix the commented line? (i will later put this in a loop so it does the work for me)
Eclipse gives me this error before i ever try to compile:

"The method setElement(char) is undefined for type DList" (DList is the class im adding my method to)

Here is the setElement method: (its in a separate class from the method that i am writing)

public void setElement(String newElem) 
  { 
	  element = newElem; 
  }



Here is the toString method: (its in the same class as the method im writing)

/** Returns a string representation of the list */
  public String toString() 
  {
    String s = "[";
    
    DNode v = head.getNext();
    
    while (v != tail) 
    {
      s += v.getElement();
      v = v.getNext();
      if (v != tail)
    	  s += ",";
    }
    
    s += "]";
    return s;
  }


Is This A Good Question/Topic? 0
  • +

Replies To: method to meld doubly linked lists

#2 japanir  Icon User is offline

  • jaVanir
  • member icon

Reputation: 1010
  • View blog
  • Posts: 3,025
  • Joined: 20-August 09

Re: method to meld doubly linked lists

Posted 28 February 2011 - 12:38 PM

No need to use toString. if it is an assignment, you will miss the point of it.
first decide which node would be the head.
then you should use 3 while loops.
the first iterates while the next node of list1 and list2 is not null.
alternately assign the current node of list2 and list1 to the next node of newList
the second loop will loop while list1 next node is not null and add it to newList.
the third loop will loop while list2 next node is not null and add it to newList.
note that only one loop of the second and third will be executed.
update the prev nodes of newlist as well.
Was This Post Helpful? 0
  • +
  • -

#3 <3DIC  Icon User is offline

  • D.I.C Regular


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

Re: method to meld doubly linked lists

Posted 03 March 2011 - 08:23 AM

I wrote the method, but when i try to test it i get some error messages:

method:

public DList meld(DList L, DList M) 
  {  
	  DList L2 = null;
	  
	  DNode next1 = null;
	  DNode next2 = null;
	 
	 next1 = L.getNext(next1);
	 next2 = M.getNext(next2);
	  
	  while (next1 != null && next2 != null)
	  {
		  // alternately assign the current node of list2 and list1 to the next node of newList
		  L2.addLast(next1);
		  L2.addLast(next2);
		  
		  while(next1 != null)
		  {
			  L2.addLast(next1);
		  }
		  
		  while(next2 != null)
		  {
			  L2.addLast(next2);
		  }
	  }
	     
	  return L2;
  } // end meld


test call:

System.out.println(meld(myList, myList2)); // eclipse gives error: "The method meld(DList, DList) is undefined for the type Lab5Test"
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,117
  • Joined: 27-December 08

Re: method to meld doubly linked lists

Posted 03 March 2011 - 08:45 AM

Where is your meld() method located?
Was This Post Helpful? 0
  • +
  • -

#5 <3DIC  Icon User is offline

  • D.I.C Regular


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

Re: method to meld doubly linked lists

Posted 03 March 2011 - 09:59 AM

Its in the DList class
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,117
  • Joined: 27-December 08

Re: method to meld doubly linked lists

Posted 03 March 2011 - 10:02 AM

Your error is pretty self-descriptive then. You have to invoke the meld() method from the DList class, not the LabTest5 class.
Was This Post Helpful? 0
  • +
  • -

#7 <3DIC  Icon User is offline

  • D.I.C Regular


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

Re: method to meld doubly linked lists

Posted 03 March 2011 - 10:33 AM

So what do i need to change to be able to invoke this method from my test class?
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,117
  • Joined: 27-December 08

Re: method to meld doubly linked lists

Posted 03 March 2011 - 10:35 AM

You have to invoke it from a DList object.
Was This Post Helpful? 0
  • +
  • -

#9 <3DIC  Icon User is offline

  • D.I.C Regular


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

Re: method to meld doubly linked lists

Posted 03 March 2011 - 10:54 AM

Now i have the test class going, but when i run it, it throws a null pointer exception:

here is what the test class looks like:

public class Lab5Test 
{
	public static void main(String[] args) 
	{
		DList myList5 = new DList();
		DList myList6 = new DList();
		
		
		myList5.addFirst(new DNode("M", null, null));
		myList5.addLast(new DNode("N", null, null));
		myList5.addLast(new DNode("O", null, null));
		
		myList6.addFirst(new DNode("P", null, null));
		myList6.addLast(new DNode("Q", null, null));
		myList6.addLast(new DNode("R", null, null));
		
		System.out.println("myList5: " + myList5.toString());
		System.out.println("myList5: " + myList5.toString());
		
		myList5.meld(myList5, myList6);
		System.out.println(myList5.toString());
	}

}

Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,117
  • Joined: 27-December 08

Re: method to meld doubly linked lists

Posted 03 March 2011 - 11:08 AM

You've been around here long enough to know that we need to see your error messages in order to help. Please post them! :)
Was This Post Helpful? 1
  • +
  • -

#11 <3DIC  Icon User is offline

  • D.I.C Regular


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

Re: method to meld doubly linked lists

Posted 03 March 2011 - 11:35 AM

Sorry about that, i forgot to paste it:

myList5: [M,N,O]
myList5: [M,N,O]
Exception in thread "main" java.lang.NullPointerException
	at DList.getNext(DList.java:83)
	at DList.meld(DList.java:350)
	at Lab5Test.main(Lab5Test.java:55)

Was This Post Helpful? 0
  • +
  • -

#12 pbl  Icon User is offline

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

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

Re: method to meld doubly linked lists

Posted 03 March 2011 - 04:52 PM

public DList meld(DList L, DList M) 
  {  
	  DList L2 = null;
	  
	  DNode next1 = null;
	  DNode next2 = null;
	 
	 next1 = L.getNext(next1);
	 next2 = M.getNext(next2);
	  
	  while (next1 != null && next2 != null)
	  {
		  // alternately assign the current node of list2 and list1 to the next node of newList
		  L2.addLast(next1);
		  L2.addLast(next2);
		  
         	 next1 = L.getNext(next1);
	         next2 = M.getNext(next2);
	  }
	     
	  return L2;
  } // end meld

Then you have to continue with the list that still has element into it
Was This Post Helpful? 1
  • +
  • -

#13 <3DIC  Icon User is offline

  • D.I.C Regular


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

Re: method to meld doubly linked lists

Posted 03 March 2011 - 06:13 PM

What do you mean by this? "Then you have to continue with the list that still has element into it"

Are you saying i should implement the code above and add some code to do what you just said?
Was This Post Helpful? 0
  • +
  • -

#14 pbl  Icon User is offline

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

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

Re: method to meld doubly linked lists

Posted 03 March 2011 - 06:38 PM

Yep

If one of the list islonger than the other one you will exit the loop because next1 or next2 will be null. You will have to continue with the one that still have elements into it
Was This Post Helpful? 0
  • +
  • -

#15 <3DIC  Icon User is offline

  • D.I.C Regular


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

Re: method to meld doubly linked lists

Posted 03 March 2011 - 06:47 PM

Would it be better to do a check like this if
(L.size() > M.size())
to see which one is bigger from the start then just have a separate loop for each case?
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3