# find the sum of two Doubly Linked Lists

• 11-03-2011, 05:24 PM
MaceMan
find the sum of two Doubly Linked Lists
Hi guys, I have searched the entire web:(whew): 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.

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. :frusty:
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.
• 11-03-2011, 06:57 PM
Norm
Re: find the sum of two Doubly Linked Lists
Quote:

* 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?
• 11-03-2011, 08:53 PM
MaceMan
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?
• 11-03-2011, 09:21 PM
Norm
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.
• 11-04-2011, 02:14 AM
MaceMan
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.
• 11-04-2011, 03:07 AM
MaceMan
Re: find the sum of two Doubly Linked Lists
Here is what I have come up with so far:

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.
• 11-04-2011, 03:10 AM
MaceMan
Re: find the sum of two Doubly Linked Lists
This is just a stupid doubly post >:(
• 11-04-2011, 03:17 AM
Norm
Re: find the sum of two Doubly Linked Lists
Quote:

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.

Quote:

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.