1. Member Join Date
Mar 2011
Posts
45
Rep Power
0

## 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 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
*/
{
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
*/
{
{
}
}

/**
* Resets the HugeNumber to a null, empty value
*/
public void resetValue()
{
tail = null;
}

/**
* @return String The HugeNumber converted to a string
*/
public String toString()
{
String strVal ="";
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.  Reply With Quote

2. ## Re: find the sum of two Doubly 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?  Reply With Quote

3. Member Join Date
Mar 2011
Posts
45
Rep Power
0

## 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?  Reply With Quote

4. ## 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.  Reply With Quote

5. Member Join Date
Mar 2011
Posts
45
Rep Power
0

## 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.  Reply With Quote

6. Member Join Date
Mar 2011
Posts
45
Rep Power
0

## 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--)
{
}

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?
{
}

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.  Reply With Quote

7. Member Join Date
Mar 2011
Posts
45
Rep Power
0

## Re: find the sum of two Doubly Linked Lists

This is just a stupid doubly post >:(  Reply With Quote

8. ## 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.  Reply With Quote

#### Posting Permissions

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