find the sum of two Doubly Linked Lists

[MaceMan]

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.

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.

[Norm]

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?

[MaceMan]

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?

[Norm]

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.

[MaceMan]

I have Tail, I'll see if I can work something out like that, and post it if it has some problems.

[MaceMan]

Here is what I have come up with so far:

	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.

[MaceMan]

This is just a stupid doubly post >:(

[Norm]

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.