7 Replies - 423 Views - Last Post: 26 October 2012 - 07:05 AM Rate Topic: -----

#1 DanteHunt  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 18
  • Joined: 11-January 12

behavior of a singly-linked-list of nodes within a loop

Posted 23 October 2012 - 04:34 AM

Hi all,

Just getting this out the way so we can get down to whats what. Yes I am a student. My question is relate to the curriculum I am currently learning. This WAS a homework assignment but the current code is far from what I turned in, hence now only being a side project of my own now. I was instructed (for homework) to merge two lists without creating new objects; thus I was required to implement the two finger method. My homework was the merge method. Which means the main method was not part of the homework.

Now, my question focuses on the main method. Correct me if I am wrong: Considering that a node linked-list connects objects by an "invisible thread"; being that first we have an object then the next pointer pointing to either null (specifying the end) or the next item of the linked-list. And that its creation follows stack principles F.I.L.O. And lets say that I wanted to create a list of numbers in acceding order. This can be done in two ways.

1) *how I learned in class* have a first pointer created with the very first object, and a temp pointer that will go through the process of the list creation.

2) *another way that occurred to me* have an array of integers in ascending order, create the pointer List with the very last element in the array and the 'next' point to null. Then, descend through the array's index and store each element in the linked-list of nodes.

in the main method I used #1, please understand I just put all this with the hopes of being corrected so I can improve my understanding
Also, I am aware that those two actions are preferably preformed within a loop but this is not the behavior I am mainly questioning

**********The problem.
-because the programs merge method can deals with equal size and unparalleled size of linked-lists, there are two cases to be tested.
-to avoid the tedious task of clicking the run button every time in order to test the probable out comes, I put ,(mostly everything), in the main method within a do-while loop so that at the end I am given the option to continue or not. Hence not needed to press run every time I want to test each case.

-The initial run: Everything seems to run fine. I input the size of both linked-lists to be of paralleled size and I print out the two lists first then the merged list. This is to show the merged list is a product of the two.
-I am prompt to continue: choose to continue to test the unparalleled size of linked-lists. Everything goes smoothly until the program calls on the merge method. It seems I encounter an infinite loop.

*my first thought is that the unparalleled size has something to do with it. I re-run the program but this time start with the unparalleled size. There is no problem, the program performs as it should.
-I am prompt to continue: I choose to continue to then see what is the problem. I input the size of each linked-list to be parallel. I encounter the same problem.

*******My attempts to solve
-because I have the initial two lists to print out first, I see the problem doesn't happen there. I place printLines to see where exactly my problem starts. It then narrows down to when the merge method is called. I then continue with the printLines within the merge method, and see that within the loop that merges the two linked-lists I encounter an infinite loop. There is a printLine there that shows me the values of each list as it's being merged and see that the incrementation of the linked-list's index is skipped. It would be understandable if it is because the pointer next is indicating to null which then the index is not incremented. But that is not it. If you see, the values are stuck around the beginning of the list.

*I would continue with my other attempts but my head is going all over the place with this explanation.

*The code of the merge method and the main method, including of the separate node class will be posted. This is so the project can be seen as a whole. Please feel free to "rip me a new one" if you have to. Any clarification (if needed) regarding the behavior of anything written above is appreciated.


Node Class
package ClassWork3;

public class NodeOfInt {
	public int data;
	public NodeOfInt next;
	
	public NodeOfInt(int dat, NodeOfInt nex) {
		this.data = dat;
		this.next = nex;
	}
}



Main method and merge
package ClassWork3;

import ClassWork3.NodeOfInt;
import java.util.Scanner;

public class HomeWork3 {
	public static void main(String[] args) {
	NodeOfInt L1 = new NodeOfInt(0 ,null);
	NodeOfInt L1pointer = L1;
	NodeOfInt L2 = new NodeOfInt(1 ,null);
	NodeOfInt L2pointer = L2;
	Scanner input = new Scanner(System.in);
	int size;
	
	System.out.println("******************************"
					 + "\n* THIS PROGRAM'S MAIN METHOD *"
					 + "\n* TESTS THE MERGE METHOD FOR *"
					 + "\n*     TWO ARRAYS WHOSE       *"
					 + "\n* COMBINATION IS MxN OR NxN  *"
					 + "\n******************************"
					 );  
	do {
		System.out.println("\n##############################");
		System.out.print("Please enter a size for list1: ");
		size = input.nextInt();
		for(int i = 1; i < size; i++){
			int num = i * 2;
		
			NodeOfInt temp1 = new NodeOfInt(num ,null);
		
			L1pointer.next = temp1;
			L1pointer = L1pointer.next;
		}
	
		System.out.print("Please enter a size for list2: ");
		size = input.nextInt();
		for(int i = 1; i < size; i++){
			int num = (i * 3) - 1;
		
			NodeOfInt temp2 = new NodeOfInt(num ,null);
		
			L2pointer.next = temp2;
			L2pointer = L2pointer.next;
		}
	
		System.out.println("\n********>List 1\n------------------------------");
		NodeOfInt temp1 = L1;
		size = 1;
		while(temp1 != null){
			System.out.printf("%-2d|", temp1.data);
			if(size % 10  == 0)
				System.out.println();
		
			temp1 = temp1.next;
			size++;
		}
		System.out.println();
    
    
		System.out.println("\n********>List 2\n------------------------------");
		NodeOfInt temp2 = L2;    
		size = 1;
		while(temp2 != null){
			System.out.printf("%-2d|", temp2.data);
			if(size % 10  == 0)
				System.out.println();
		
			temp2 = temp2.next;
			size++;
		}
		System.out.println();
    
		NodeOfInt Lmerged = merge(L1, L2);
		NodeOfInt temp3 = Lmerged;

		System.out.println("\n********>Merged list\n------------------------------");
		size = 1;
		while(temp3 != null){
			System.out.printf("%-2d|", temp3.data);
			if(size % 10  == 0)
				System.out.println();
		
			temp3 = temp3.next;
			size++;
		}
	
		System.out.print("\nDo you wish to to continue[y/n]: ");
	}while(input.next().toLowerCase().charAt(0) == 'y');
}
	/**
	 * The total of nodes created in this method is
	 * L1's size + L2's size.
	 * temp and MergedL are merely  pointers
	 * @param L1
	 * @param L2
	 * @return MergedL
	 */
	static NodeOfInt merge(NodeOfInt L1, NodeOfInt L2) {
		System.out.println("#%$%#");
		/**
		 *Create two pointers
		 *MergedL is the pointer to be returned
		 *temp is the pointer to create the merged list on 
		 */
		NodeOfInt MergedL, temp;

		/**
		 * This if statement checks which first
		 * node of L1 and L2 is smaller
		 */
		if(L1.data < L2.data) {
			MergedL = L1;
			temp = MergedL;
			L1 = L1.next;
		}
		/**
		 * Here if L1.data and L2.data 
		 * are equal or L1 is greater
		 * The result will be the same.
		 */
		else{
			MergedL = L2;
			temp = MergedL;
			L2 = L2.next;
		}
		/**
		 * The while loop will have the same implementation
		 * as the above if statement but here he exercise
		 * the possibility of
		 * *L1's size being smaller/larger than L2's size*
		 * or vice versa. 
		 */
		while(L1 != null || L2 != null) {

			/**
			 * This only executes if L1 and L2 both
			 * have a item.
			 */
			if(L1 != null && L2 != null)  {
							//System.out.println(L1.data + "|L1|L2|" + L2.data);
				if (L1.data < L2.data) {
					temp.next = L1;
					L1 = L1.next;
					temp = temp.next;
				}
				else {
					temp.next = L2;
					L2 = L2.next;
					temp = temp.next;
				}
			}
			/**
			 * This else runs on the possibility if 
			 * either L1 is null or L2 is null
			 */
			else {
				/**
				 * L2 is null
				 * L1 still has an item
				 */
				if(L2 == null && L1 != null) {
					//System.out.println(L1.data + "|L1|");
					temp.next = L1;
					L1 = L1.next;
					temp = temp.next;
				}
				/**
				 * L1 is null
				 * L2 still has an item
				 */
				if(L1 == null && L2 != null) {
					//System.out.println("|L2|" + L2.data);
					temp.next = L2;
					L2 = L2.next;
					temp = temp.next;
				}
				/**
				 * This if is so both are null.
				 */
				else{
					//System.out.println("|*^*|");
					break;
				}
			}	
		}
		
		/**
		 * Because we used temp to merge the two lists
		 * MergedL remains untouched, still pointing to 
		 * the first node.
		 */
		return MergedL;
	}
}




Is This A Good Question/Topic? 0
  • +

Replies To: behavior of a singly-linked-list of nodes within a loop

#2 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2204
  • View blog
  • Posts: 5,236
  • Joined: 10-September 10

Re: behavior of a singly-linked-list of nodes within a loop

Posted 23 October 2012 - 06:05 AM

Now that you've gotten that off your chest . . .

Those who try to help here are pretty gentle. There's little "ripping new ones." Even so, there are limits - whether due to patience, available time and resources, or a combination - to the effort one will expend to figure out what the poster is asking for help with. Most blog posts are shorter than what you've posted. Can you cut to the chase? Or maybe there are multiple questions (even though there are no question marks, only threats that there will be). Instead of asking all 30 in one post, start with one, the most important one, and let's work from there.
Was This Post Helpful? 0
  • +
  • -

#3 DanteHunt  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 18
  • Joined: 11-January 12

Re: behavior of a singly-linked-list of nodes within a loop

Posted 23 October 2012 - 01:12 PM

View PostGregBrannon, on 23 October 2012 - 06:05 AM, said:

Now that you've gotten that off your chest . . .

Those who try to help here are pretty gentle. There's little "ripping new ones." Even so, there are limits - whether due to patience, available time and resources, or a combination - to the effort one will expend to figure out what the poster is asking for help with. Most blog posts are shorter than what you've posted. Can you cut to the chase? Or maybe there are multiple questions (even though there are no question marks, only threats that there will be). Instead of asking all 30 in one post, start with one, the most important one, and let's work from there.


Sure thing, sorry if I haven't already. I was trying to paint a picture of my thought process during the coding. By then if there is an error there, one would correct me.

My questions are stated on the problem section. But its no issue, I'll specify them again.

1) If you take a look at the main method; There is a major loop, and miner loops within it. From what I can tell the minor loops work fine because the print out of the lists seem to work just the same. From what I could evaluate my problem occurs on line 73
       NodeOfInt Lmerged = merge(L1, L2);



but please keep in mind this problem only shows up after my initial test (no matter which test I initiate with).

************My main question is why does this happen?

if my question is still unclear, I strongly advice to the code. Put which ever input you wish in the initial run. Once that happens you will be shown L1 and L2 with the mergedL. Then you are prompt to continue: Enter y. Enter any input you wish for the list's size. By then you will encounter my problem thus producing my question.

Again, sorry from earlier. I was trying to be as thorough as possible.
Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

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

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: behavior of a singly-linked-list of nodes within a loop

Posted 23 October 2012 - 01:19 PM

I can't beleive how complicated you made it :)
To merge simply loop on the first node until its forward pointer is null
assign to that null forward pointer the other Node. No need to test if it is null or not

Node merge = node1;
if(merge == null) {
   merge = node2;
   return;
}
while(merge.forward != null)
    merge.forward = merge.forward.forward;
merger.forward = node2;


Was This Post Helpful? 0
  • +
  • -

#5 DanteHunt  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 18
  • Joined: 11-January 12

Re: behavior of a singly-linked-list of nodes within a loop

Posted 24 October 2012 - 05:57 AM

View Postpbl, on 23 October 2012 - 01:19 PM, said:

I can't beleive how complicated you made it :)
To merge simply loop on the first node until its forward pointer is null
assign to that null forward pointer the other Node. No need to test if it is null or not

Node merge = node1;
if(merge == null) {
   merge = node2;
   return;
}
while(merge.forward != null)
    merge.forward = merge.forward.forward;
merger.forward = node2;



Ahhh, I see where you are going at, but from what I can tell it only merges the two lists. Which is fine but the assignment required of me to merge them in ascending order. Such that L1 and L2 would have any amount & variation of numbers in ascending order. Lets say for example L1 first element is 100, and L2 first element is 1. I can't simply put 1, 100 in the merge list. I must check that if any further elements have a lesser/greater value than 100.

A better way to show this: L1's first element is 100, L2 first element is 1. L1 > L2, thus mergedL = 1. Incriment L2's index. L2's new current element is 200. There is where one must have all those complicated conditions to assure the elements will be stored in ascending order.
Was This Post Helpful? 0
  • +
  • -

#6 karabasf  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 202
  • View blog
  • Posts: 417
  • Joined: 29-August 10

Re: behavior of a singly-linked-list of nodes within a loop

Posted 25 October 2012 - 02:17 AM

I read your question and it caught my interest. Taking your last post into account it seems that you want a MergeSort procedure on linked lists (or in this case, two of them).

I dug up my Algorithms book and there it proposes:
// S1 and S2 are two SORTED linked lists
// S is the sorted linked list after merge
while S1 is not empty and S2 is not empty
	// We want to have an ascending list , so this condition checks which value is lower and inserts it in the list S
	if (S1.first().element <= S2.first().element)
		// Remove the head of S1 and place it at the tail of the new linked list
		S.addLast(S1.removeHead()) 
	else // Apparently the first element of S2 is smaller 
		S.addLast(S2.removeHead())
	
	// Move the remaining elements of S1 and S2 
	while S1 is not empty
		S.addLast(S1.removeHead())
	
	while S2 is not empty
		S.addLast(S2.removeHead())



Note that for this algorithm it is important that the linked lists you input are sorted or it won't work for the last two steps (as it can happen that the size of S1 and S2 are not equal)
Another thing is that this destroys the original data which was contained by the lists S1 and S2, because you remove the head. If you want to keep the data, you should make a copy of the original list.
Was This Post Helpful? 0
  • +
  • -

#7 DanteHunt  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 18
  • Joined: 11-January 12

Re: behavior of a singly-linked-list of nodes within a loop

Posted 26 October 2012 - 05:33 AM

View Postkarabasf, on 25 October 2012 - 02:17 AM, said:

I read your question and it caught my interest. Taking your last post into account it seems that you want a MergeSort procedure on linked lists (or in this case, two of them).

I dug up my Algorithms book and there it proposes:
// S1 and S2 are two SORTED linked lists
// S is the sorted linked list after merge
while S1 is not empty and S2 is not empty
	// We want to have an ascending list , so this condition checks which value is lower and inserts it in the list S
	if (S1.first().element <= S2.first().element)
		// Remove the head of S1 and place it at the tail of the new linked list
		S.addLast(S1.removeHead()) 
	else // Apparently the first element of S2 is smaller 
		S.addLast(S2.removeHead())
	
	// Move the remaining elements of S1 and S2 
	while S1 is not empty
		S.addLast(S1.removeHead())
	
	while S2 is not empty
		S.addLast(S2.removeHead())



Note that for this algorithm it is important that the linked lists you input are sorted or it won't work for the last two steps (as it can happen that the size of S1 and S2 are not equal)
Another thing is that this destroys the original data which was contained by the lists S1 and S2, because you remove the head. If you want to keep the data, you should make a copy of the original list.

Perfect! Now, lets say we would want to implement the call that method within a loop, that gives a user multiple chances to test various probabilities for S1 and S2.

I suppose my question corresponds to syntax and process. If you would take a look at my very first post; I have the main method there. Is my process when creating S1 and S2 correct(They are really L1 and L2)? Also would it help if I made a separate method for the creation of the strings; hence, avoiding local variable issues. This also makes me wander if it would assure that the previous linked-list gets destroyed as it should, on the second time around in that loop.
Was This Post Helpful? 0
  • +
  • -

#8 DanteHunt  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 18
  • Joined: 11-January 12

Re: behavior of a singly-linked-list of nodes within a loop

Posted 26 October 2012 - 07:05 AM

Ha! I fixed it, the problem was too much reference to each linked-list within the main method. I applied the separation of process to each reference within the main method into little methods. =) my hunch was right, the pointers were fumbling with the nodes. Think of it this way: having the nodes play a fast paste game of egg toss.

For those of you curious, here is the code.
Thank you for the help

package ClassWork3;

import ClassWork3.NodeOfInt;
import java.util.Scanner;


public class HomeWork3 {
	
	static NodeOfInt createList() {
		Scanner input = new Scanner(System.in);
		NodeOfInt L = new NodeOfInt(0 ,null);
		NodeOfInt Lpointer = L;
		int size;
		
		size = input.nextInt();
		for(int i = 1; i < size; i++){
			int num = i * ((int)(Math.random()) + 1);
		
			NodeOfInt temp1 = new NodeOfInt(num ,null);
		
			Lpointer.next = temp1;
			Lpointer = Lpointer.next;
		}
		return L;
	}
	
	public static void main(String[] args) {
	Scanner input = new Scanner(System.in);
	
	System.out.println("******************************"
					 + "\n* THIS PROGRAM'S MAIN METHOD *"
					 + "\n* TESTS THE MERGE METHOD FOR *"
					 + "\n*     TWO ARRAYS WHOSE       *"
					 + "\n* COMBINATION IS MxN OR NxN  *"
					 + "\n******************************"
					 );  
	do {
		System.out.println("\n##############################");
		System.out.print("Please enter a size for list1: ");
		NodeOfInt L1 = createList();
		
	
		System.out.print("Please enter a size for list2: ");
		NodeOfInt L2 = createList();
	
		System.out.println("\n********>List 1\n------------------------------");
		printList(L1);
    
		System.out.println("\n********>List 2\n------------------------------");
		printList(L2);
    
		NodeOfInt Lmerged = mergeSort(L1, L2);

		System.out.println("\n********>Merged list\n------------------------------");
		printList(Lmerged);
	
		System.out.print("\nDo you wish to to continue[y/n]: ");
	}while(input.next().toLowerCase().charAt(0) == 'y');
}
	/**
	 * The total of nodes created in this method is
	 * L1's size + L2's size.
	 * temp and MergedL are merely  pointers
	 * @param L1
	 * @param L2
	 * @return MergedL
	 */
	static NodeOfInt mergeSort(NodeOfInt L1, NodeOfInt L2) {
		//System.out.println("#%$%#");
		/**
		 *Create two pointers
		 *MergedL is the pointer to be returned
		 *temp is the pointer to create the merged list on 
		 */
		NodeOfInt MergedL, temp;

		/**
		 * This if statement checks which first
		 * node of L1 and L2 is smaller
		 */
		if(L1.data < L2.data) {
			MergedL = L1;
			temp = MergedL;
			L1 = L1.next;
		}
		/**
		 * Here if L1.data and L2.data 
		 * are equal or L1 is greater
		 * The result will be the same.
		 */
		else{
			MergedL = L2;
			temp = MergedL;
			L2 = L2.next;
		}
		/**
		 * The while loop will have the same implementation
		 * as the above if statement but here he exercise
		 * the possibility of
		 * *L1's size being smaller/larger than L2's size*
		 * or vice versa. 
		 */
		while(L1 != null || L2 != null) {

			/**
			 * This only executes if L1 and L2 both
			 * have a item.
			 */
			if(L1 != null && L2 != null)  {
							//System.out.println(L1.data + "|L1|L2|" + L2.data);
				if (L1.data < L2.data) {
					temp.next = L1;
					L1 = L1.next;
					temp = temp.next;
				}
				else {
					temp.next = L2;
					L2 = L2.next;
					temp = temp.next;
				}
			}
			/**
			 * This else runs on the possibility if 
			 * either L1 is null or L2 is null
			 */
			else {
				/**
				 * L2 is null
				 * L1 still has an item
				 */
				if(L2 == null && L1 != null) {
					//System.out.println(L1.data + "|L1|");
					temp.next = L1;
					L1 = L1.next;
					temp = temp.next;
				}
				/**
				 * L1 is null
				 * L2 still has an item
				 */
				if(L1 == null && L2 != null) {
					//System.out.println("|L2|" + L2.data);
					temp.next = L2;
					L2 = L2.next;
					temp = temp.next;
				}
				/**
				 * This if is so both are null.
				 */
				else{
					//System.out.println("|*^*|");
					break;
				}
			}	
		}
		
		/**
		 * Because we used temp to merge the two lists
		 * MergedL remains untouched, still pointing to 
		 * the first node.
		 */
		return MergedL;
	}
	
	static void printList(NodeOfInt L) {
		NodeOfInt temp = L;
		int size = 1;
		
		while(temp != null){
			System.out.printf("%-2d|", temp.data);
			if(size % 10  == 0)
				System.out.println();
		
			temp = temp.next;
			size++;
		}
		System.out.println();
	}
}



Was This Post Helpful? 0
  • +
  • -

Page 1 of 1