Results 1 to 8 of 8
 11032011, 05:24 PM #1Member
 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 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; } }
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; 11042011 at 03:07 AM.
When in doubt, use a lightsaber
 11032011, 06:57 PM #2
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.
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?
 11032011, 08:53 PM #3Member
 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?When in doubt, use a lightsaber
 11032011, 09:21 PM #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.
 11042011, 02:14 AM #5Member
 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.
When in doubt, use a lightsaber
 11042011, 03:07 AM #6Member
 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) { 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; }
Thanks guys for any help.When in doubt, use a lightsaber
 11042011, 03:10 AM #7Member
 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 >:(
When in doubt, use a lightsaber
 11042011, 03:17 AM #8
Re: find the sum of two Doubly Linked Lists
now do I set the tail of both lists
how would I move the tail to the next value?
Similar Threads

DoublyLinked list
By swp in forum New To JavaReplies: 3Last Post: 10112011, 04:27 PM 
Doubly Linked List
By matin1234 in forum New To JavaReplies: 0Last Post: 06022010, 06:58 AM 
Doubly Linked Lists
By stevenson15 in forum New To JavaReplies: 6Last Post: 04212009, 01:35 PM 
doubly linked list insert
By ineedhelpwithjava in forum Advanced JavaReplies: 1Last Post: 03202009, 03:05 PM 
Help with Doubly linked list
By Dr Gonzo in forum New To JavaReplies: 5Last Post: 12062008, 08:45 AM
Bookmarks