Java: Linked List Help - Overclock.net

killnine · 02-08-07

Hey guys,
I know this isn't much of a programming forum, but I am working on a small java app that takes two doubly-linked lists and concatenates them. Therefore, you have list L and M, and M is smashed onto the end of the list L.

However, I cant seem to find a working way of doing this. See below:

Code:

		DNode list_L_1 = new DNode("Value 1",null,null);
		DNode list_L_2 = new DNode("Value 2",null,null);
		DNode list_L_3 = new DNode("Value 3",null,null);
		DNode list_L_4 = new DNode("Value 4",null,null);
		
		DNode list_M_1 = new DNode("Value Add 1",null,null);
		DNode list_M_2 = new DNode("Value Add 2",null,null);
		DNode list_M_3 = new DNode("Value Add 3",null,null);
		DNode list_M_4 = new DNode("Value Add 4",null,null);
		
		/* Declaring List to Call Later to Test Methods*/
		
		DList list_L = new DList();
		list_L.addFirst(list_L_1);
		list_L.addAfter(list_L_1,list_L_2);
		list_L.addAfter(list_L_2,list_L_3);
		list_L.addAfter(list_L_3,list_L_4);
		System.out.println(list_L);
		
		DList list_M = new DList();
		list_M.addFirst(list_M_1);
		list_M.addAfter(list_M_1,list_M_2);
		list_M.addAfter(list_M_2,list_M_3);
		list_M.addAfter(list_M_3,list_M_4);
		System.out.println(list_M);		
				
		/* Below I Test My Many Amazing Methods */
		testConcatenate(list_L,list_M);
	}
	
	public static void testConcatenate(DList L, DList M)
	{
		L.concatenate(M);
		System.out.println(L);
	}

So here I create some lists, called list_L and list_M. Then I call the following method to concatenate them (called "concatenate()"):

Code:

  public void concatenate(DList M)
  {
	  /*If both lists null, return null */
	  if ((this.size == 0) && (M.size == 0))
	  {
		  System.out.println("List Error: Both Lists Null, Aborting...");
	  }

	  else 
	  {
		  DList Mcopy = M;
		  		  		
		  int length = M.size;
		  for (length = M.size; length > 1; length --)
		  {
			  DNode t = M.getFirst();
			  this.addAfter(trailer.getPrev(),t);
			  M.remove(M.getFirst());
			  
		  }
		  M = Mcopy;	//Return shizzle back to normalz, yo.
		  System.out.println("Concatenation Complete");
	  }	  
	  
  }

However, all it does is print out the original list_L. When I step through this thing, it adds the node onto the end, but after "M.remove(M.getFirst());", it ALSO REMOVES IT FROM where it put it on List_L. Crazy.... help?

welfinator · 02-08-07

i'm not that good with double linked lists but don't you have to set a pointer from the object to the next and to the previous item?

killnine · 02-09-07

Yeah, that is correct. However, I have build the methods addAfter, addBefore, and addFirst to do this automatically. Actually, they were methods provided by my professor, so I know they work.

C-bro · 02-09-07

Questions first.
1) What does your Dnode class look like? Are there references for next node AND previous nodes?

2) For your node constructors, do you automatically initiliaze the next reference to null?

3) Are you trying to make a new linked list that's a concatenation of the two, or are you just trying to tack one on the end of an existing one?

4) Are you using a dummy node for your head, or does your first node contain actuall data?

This is how I'd do it. Make sure your constructor makes this.next = null. That way, you know if you ever reach a node where this.next==null, you've reached the end of your list. This way you can simply do a search and make the next reference from your last node, equal to the first node from the other list.

public void concatenate(DNode M){

DNode lastNode = this.next; // create a node to track your position

while(lastNode.next != null){
lastNode = lastNode.next;
}

//when you get out of this loop, lastNode will be pointing to your last node

lastNode.next = M;
// this adds the link from your last node in L to point to the first one in M

}

You'll have to mess around with this because I didn't have a chance to compile or check for syntax, but you get the idea of what I'm trying to do. Basically do these 2 steps:

1) find your last node in list L
2) point the next value from the last node in L to M

rabidgnome229 · 02-09-07

For the declaration i would say

Code:

DList list_L = new DList(), list_M = new DList();
for(int i = 0; i < 4; i++)
{
   list_L.addLast(new DNode("Value Add " + (i + 1), NULL, NULL)
   list_M.addLast(new DNode("Value Add " + (i + 1), NULL, NULL)
}

as for the method

Code:

public void concatenate(DList M)
{
  if(!this && !M)
     System.out.println("List Error: Both Lists Null, Aborting...");
  else
      for(int i = 0; i < M.length; i++)
          addLast(M.get(i));
}

**EDIT**
@ Cyberd
the dnode code doesn't matter since linkedlists use and return objects

**ANOTHER EDIT**
Does Dlist have the same methods as the linkedList class? If not I'll need to see the Dlist code to help you

**yet another edit**
Since this is java (OO) when you remove from list M you are also removing from Mcopy
Saying Mcopy = M does not create a copy of M - it just links Mcopy and M to the same data

		Overclock.net - Overclocking.net > Software, Programming and Coding > Coding and Programming
Java: Linked List Help

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)