Results 1 to 8 of 8
  1. #1
    MaceMan is offline Member
    Join Date
    Mar 2011
    Posts
    45
    Rep Power
    0

    Default find the sum of two Doubly Linked Lists

    Hi guys, I have searched the entire web and I finally made my way back here. My problem is: I have a doubly linked list that stores digits, called HugeNumber, which has an inner class Digit. All my other methods for this problem I have completed(more or less successfully), but am totally stuck on one.The method I can complete is an add method, which takes my hugenumber, and addes it to another hugenumber. It doesn't matter right now where I get my other hugenumber, it can be from the user, or it can be initialzed.

    Java Code:
    public HugeNumber(HugeNumber newVal)
    	{
    		// Traverse the input HugeNumber, copying each node to a new list
    		DigitNode current = newVal.head;
    		DigitNode temp;  // Copy of current node
    		DigitNode prev;  // Previous node for the copy so we can set up the double link
    		
    		temp = new DigitNode(current.digit, null, tail);
    		prev = temp;
    		current = current.getNext();
    		while (current != null)
    		{
    			prev.next = new DigitNode(current.digit, null, tail);
    			prev = prev.next;
    			current = current.next;
    		}
    				
    	}
    
    	/**
    	* Adds a input HugeNumber to this HugeNumber.  It traverses the linked lists,
    	* adding each digit starting from the least significant digit and working
    	* up to the most significant digit.
    	*
    	* @param otherNum target HugeNumber to add
    	* @return HugeNumber HugeNumber that represents the sum of the two HugeNumbers
    	*/ 
    	public HugeNumber add(HugeNumber otherNum)
    	{	 
    		HugeNumber newNum = new HugeNumber();	// Create new number
    
    
                             //HERE IS WHERE I DON'T KNOW WHAT TO DO                          
    	}
    
    	/**
    	* addDigit adds a new digit, d, as a new most significant
    	* digit for the list.
    	* @param d new digit to add as the MSD
    	*/
    	public void addDigit(int d)
    	{
    		DigitNode newHead = new DigitNode(d, null, head);
    		if (head != null)
    		{
    			head.prev = newHead;
    		}
    		head = newHead;
    	}
    
    	/**
    	* Resets the HugeNumber to a null, empty value
    	*/
    	public void resetValue()
    	{
    		head = null;
    		tail = null;
    	}
    
    	/**
    	* @return String The HugeNumber converted to a string
    	*/
    	public String toString()
    	{   
    		String strVal ="";
    		DigitNode position = head;
    		while (position != null)
    		{
    			strVal = strVal + position.getDigit( ) + "\n"; 
    			position = position.getNext( );
    		}
    		return strVal;
    		
    	}
    }
    (my inner class Digit is pretty stright forward, no problems there, I think, so I didn't post it).

    So my problems are with the method, public HugeNumber add(HugeNumber otherNum)
    This is what I think I have to do to get the sum, but have no clue how to do it:
    1). I have to get the recursive of the two DLL's, and add them that way, (this is correct, right?), but I don't know how to do that.

    And if that's the way I do it, how to I:
    2). Carry over to the next digit?

    My textbook, of course, gives absolutely nothing to help me on this problem.
    I'm trying to learn JAVA, so if you guys can give me the basic code outline, I'll try and work with that and get back with what I came up with. Thanks a trillion.
    Last edited by MaceMan; 11-04-2011 at 02:07 AM.
    When in doubt, use a lightsaber

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    16,589
    Rep Power
    23

    Default Re: find the sum of two Doubly Linked Lists

    It traverses the linked lists,
    * adding each digit starting from the least significant digit and working
    * up to the most significant digit.
    If you were to do this with paper an pencil, how would you do it?
    Start with the right most digits, add them. If an overflow, carry that to the next pair of digits to the left.
    Can you get to the rightmost digits?
    Can you get to the next digit to the left?

  3. #3
    MaceMan is offline Member
    Join Date
    Mar 2011
    Posts
    45
    Rep Power
    0

    Default Re: find the sum of two Doubly Linked Lists

    Ah, I see what you mean Norm. So if I reverse the D links, I simply add them normally. I'm guessing I will need a temp value to hold the overflow, if any.

    Another question. After I reverse both links, the Head value would now point to the digit that used to be the Tail, right?
    When in doubt, use a lightsaber

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    16,589
    Rep Power
    23

    Default Re: find the sum of two Doubly Linked Lists

    You should not need to reverse the list.
    With your doubly linked list, do you have a pointer to the end of the list?
    If not you can scan in from the front until you find the end and then use the previous links to work back(to the left) over the leading digits.

  5. #5
    MaceMan is offline Member
    Join Date
    Mar 2011
    Posts
    45
    Rep Power
    0

    Default Re: find the sum of two Doubly Linked Lists

    I have Tail, I'll see if I can work something out like that, and post it if it has some problems.
    When in doubt, use a lightsaber

  6. #6
    MaceMan is offline Member
    Join Date
    Mar 2011
    Posts
    45
    Rep Power
    0

    Default Re: find the sum of two Doubly Linked Lists

    Here is what I have come up with so far:

    Java Code:
    	public HugeNumber add(HugeNumber otherNum)
    	{	 
    		HugeNumber newNum = new HugeNumber();	// Create new number
    		
    		HugeNumber secondNum = new HugeNumber(); //setting number to 1234
    	    for (int i = 4; i >= 1; i--)
    	    {
    	    	secondNum.addDigit(i);
    	    }
    	    
    	    otherNum.tail = ?; //I don't know what to put in for the ? mark, now do I set the tail of both lists?
    	    secondNum.tail = ?;
    	    
    	    int addedNum = 0; //The sum of the two digits added together
    	    while (tail.hasNext) // how would I move the tail to the next value? Would hasNext work?
    	    {
    	    	addedNum = otherNum.Tail + secondNum.tail;
    	    	newNum.addDigit(addedNum);
    	    }
    		
    		return newNum;
    	}
    Obviously it has some problems with it, so please refer to the comments to see my problems. I think I have the basic logic correct. I have set both numbers so there will be no exceptional cases, like having to carryover a number. Once I get the basic adding down, I'll work on that.

    Thanks guys for any help.
    When in doubt, use a lightsaber

  7. #7
    MaceMan is offline Member
    Join Date
    Mar 2011
    Posts
    45
    Rep Power
    0

    Default Re: find the sum of two Doubly Linked Lists

    This is just a stupid doubly post >:(
    When in doubt, use a lightsaber

  8. #8
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    16,589
    Rep Power
    23

    Default Re: find the sum of two Doubly Linked Lists

    now do I set the tail of both lists
    If you have a doubly linked list you should have a pointer to the last item in the list as well as the first.

    how would I move the tail to the next value?
    How do you go through a linked list in the forward direction? With a doubly linked list you also have pointers to go in the backwards direction.

Similar Threads

  1. Doubly-Linked list
    By swp in forum New To Java
    Replies: 3
    Last Post: 10-11-2011, 03:27 PM
  2. Doubly Linked List
    By matin1234 in forum New To Java
    Replies: 0
    Last Post: 06-02-2010, 05:58 AM
  3. Doubly Linked Lists
    By stevenson15 in forum New To Java
    Replies: 6
    Last Post: 04-21-2009, 12:35 PM
  4. doubly linked list insert
    By ineedhelpwithjava in forum Advanced Java
    Replies: 1
    Last Post: 03-20-2009, 02:05 PM
  5. Help with Doubly linked list
    By Dr Gonzo in forum New To Java
    Replies: 5
    Last Post: 12-06-2008, 07:45 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •