LAB05: Addition using doubly linked list Solution

1. Introduction

In this lab, we use Doubly Linked Lists to store positive integers and perform addition

operations.

 

2. Objectives

The purpose of this assignment is to help you

     Enhance your understanding of doubly linked lists 

     Practice how to perform operations on doubly linked lists

 

Note: Before you start, if you are not familiar with DoublyLinkedLists you are recommended to review

the sample codes we covered in lecture first.  

 

3. Background

 

The purpose of this assignment is to input two positive integers, store each number in a doubly linked list (where each digit is data in a node), and perform addition on them by implementing various operations of doubly linked list. 

 

For example, the first two doubly linked lists below represent 1234, and 99 respectively. The

addition of these two numbers: 1333, is represented as the third doubly linked list.

Head


Tail

 

dll1

None


 

1                       2                       3                       4


None

 

 

 

 

 

First number  = 1234

Second number =   99

Total         = 1333


 

dll2

None


 

None

9                       9

Head


Tail

 

Head                                                                    Tail

 

sum

 

None


 

 

1                       3                       3                       3


None

4. Assignment

In the skeleton zip file, you can find a skeleton code. All you need to do is to complete the

skeleton code based on the following instructions and submit the to Mimir.  

 

4.1 class DoubyLinkedNumber

This class has two methods – 

 

•     tolinkednumber(self, string) : In this method, each digit in the input string is added as data in a node in the doubly linked list. A for loop is used to iterate over the entire string. Each character in the string is added to the last of the doubly linked list.

 

•         str    (self) : This method returns the string representation of the object. Each node is

converted to string by traversing through the entire doubly linked list. An example:

n = DoublyLinkedList()

n.tolinkednumber(‘1234’)  

 

Head                                                                    Tail


 

 

 

None

None

 

 


1                       2                       3                       4

4.2 sumlinkednumbers(dll1, dll2)

This function performs the addition of the two doubly linked lists and stores the sum in a third

doubly linked list. This function returns the sum.

1.   The first step in addition is to start from the unit’s place. Therefore, in our case, we must start from the tail of the two doubly linked lists. To do this we use cur1 and cur2 which point to the tail of the first and second doubly linked list respectively. In each iteration, they are updated to point to the previous node. We must also ensure that we account

for the carry that will be generated during this process.  

 

 

 

 

 

 

 

 

 

 

 

 

 



cu
 
Head                                                                    Tail     r1

dll1


 

Carry = 1


Carry = 0


 

 

None

None

 

 

 

 

 


1                       2                       3                       4

 



c
 
Head                Tail dll2


 

 

 

ur2


 

 

 

 

 

None

None


9                       9

 

 



N
 
Head Tail

 

sum

None                 3


one

 

 

2.   The next step is to perform the actual addition. While cur1 and cur2 still point to a node,

we add the digits in those nodes along with the carry. We must next calculate the new

value of carry. Finally, the values of cur1 and cur2 are updated to the previous node.

Head dll1


 

 

Carry = 1


cur1



y =
 
Carr      1


Tail



y =
 
Carr      0


 

 

 

 

None

 

None

 

 

 

 

 

 


1                       2                       3                       4

cur2 dll2

9                       9


 

 

 

 

 

 

 

 

None

None


 

Head sum


 

 

Tail

 



e
 
Non                  3


3                None

 

 

 

 

3.   There are two more cases that we have to account for. Either the first number could have more digits than the second (in which case, cur2 would have reached the end of the list while cur1 would still point to a valid node) or vice versa. In this case, we simply

add the carry and valid node to generate the sum. We then calculate the new value of

carry and update cur1 (or cur2) to point to the previous node.

 



cu
 
Head    r1

Carry = 0

 

dll1


 

 

 

Carry = 1


 

 

 

Carry = 1


 

Tail

Carry = 0


 

 

 

 

None

 

None

 

 


1                       2                       3                       4



c
 
Head


ur2


Tail

 

dll2

None


None

9                       9



m
 
Head                                                                      Tail su

 



e
 
Non                  1                       3                       3


3                None

 

 

You routput should look like this:

 

The first number:

1234

The second number:

99

1234 + 99 = 1333

 

5. Submit your work to Mimir

Submit doublylinkednumber.py to Mimir after you complete your code. The Mimir will automatically grade your submission based on different unit tests. You can submit your code to Mimir up to 30 times to refresh your existing score before the submission deadline.

 

 

7. Getting help

Start your project early, because you will probably not be able to get timely help in the last few

hours before the assignment is due.

     Go to the office hours of instructors and TAs.

o Prof. Wei Wei: Mon. 2:30 - 3:15pm, Wed. 2:30 - 3:15pm, Thurs. 2:30 - 3:15pm, Fri. 2:30 - 3:15pm @ITE258

o Jenny Blessing: Fri. 12pm - 2pm @ITE140

o Param Bidja: Tues. 2pm - 3pm @ITE140

o Yamuna Rajan: Tues. 11am - 12pm, Wed. 9:30am – 10:30am @ITE140

o Zigeng Wang: Mon. 3pm - 4pm @ITE140

     Post your questions on Piazza. TAs and many of your classmates may answer your

questions. 

     Search the answer of your unknown questions on the Internet. Many questions asked by

you might have been asked and answered many times online already.