1.
Introduction
1.1.
Problem statement
1.2.
Sample Examples
2.
Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.2.1.
Complexity analysis
3.
3.1.
Why is deleting faster from a doubly-linked list?
3.2.
What is the significance of the forward and backward pointers in a doubly-linked list?
3.3.
What are the limits of a doubly-linked list?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Large number arithmetic using doubly linked list

Ashish Sharma
0 upvote

## Introduction

In this article, we will understand the Doubly Linked List with the example, and perform large arithmetic operations using the doubly linked list.  A doubly linked list is a data structure containing a set of sequentially linked data called nodes. Each node is divided into two link fields(points to the next or previously linked nodes) and one data field.

### Problem statement

We are given two very large numbers in the form of strings and we have to use different arithmetic operators on these strings using a doubly-linked list.

### Sample Examples

Input

``M: 1234``

``N: 23456``

Output

``````Product: 289564320
Sum: 35801
Difference(m-n): 88889
Modulus: 12345
Quotient: 0``````

Input

``M: 897``

``N:  876``

Output

``````Product: 785772
Sum: 1773
Difference(m-n): 021
Modulus: 021
Quotient: 1``````

In the above examples, we are finding the arithmetic values using a doubly-linked list.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

## Approach

In the given problem, we will first insert the large numeric value in the form of a string. Then we will make a doubly linked list by extracting the char at each index. After we have formed the doubly linked list, we will pass the list to different functions like addition, subtraction, multiplication, and division in which we are doing the operations respectively.

After that when all the operations are done then we will simply print the addition, subtraction, multiplication, division, etc. of the strings s1 and s2.

### Pseudocode

``````// a is the first string and b is the second string

while (a1->end != NULL || b1->end != NULL)
{
if (a1->end != NULL && b1->end == NULL)
{
s = ((a1->end->info) + c) % 10;
c = ((a1->end->info) + c) / 10;
a1->end = a1->end->prevnode;
}
else if (a1->end == NULL && b1->end != NULL)
{
s = ((b1->end->info) + c) % 10;
c = ((b1->end->info) + c) / 10;
b1->end = b1->end->prevnode;
}
else if (a1->end != NULL && b1->end != NULL)
{
s = ((a1->end->info) + (b1->end->info) + c) % 10;
c = ((a1->end->info) + (b1->end->info) + c) / 10;
a1->end = a1->end->prevnode;
b1->end = b1->end->prevnode;
}
}
// subtraction function
while (a1->end != NULL || b1->end != NULL)
{
if (a1->end != NULL && b1->end != NULL)
{
if ((a1->end->info) + c < (b1->end->info))
{
s = ((a1->end->info) + c + 10 - (b1->end->info));
c = -1;
}
else if((a1->end->info) + c >=(b1->end->info))
{
s = ((a1->end->info) + c - (b1->end->info));
c = 0;
}
a1->end = a1->end->prevnode;
b1->end = b1->end->prevnode;
}
else if (a1->end != NULL && b1->end == NULL)
{
if (a1->end->info < 1)
{
if (c = 0)
{
s = a1->end->info;
}
else{
s = ((a1->end->info) + 10 + c);
c = -1;
}
}
else if(a1->end->info>=1)
{
s = ((a1->end->info) + c);
c = 0;
}
a1->end = a1->end->prevnode;
}
}
we can perform division, addition, multiplication and subtraction in this way.``````

### Implementation in C++

``````#include <iostream>
#include<cstdio>
using namespace std;
struct Node
{
int info;
struct Node* nextnode;
struct Node* prevnode;
// constructor
Node(int val)
{
info = val;
nextnode = prevnode = NULL;
}
};

{
public:
{
front = end = NULL;
size = 0;
}

//  insertion of a digit in front of a doubly linked list
void insertioninfront(int data)
{
Node* temp = new Node(data);

if (front != NULL)
{   front->prevnode = temp;
temp->nextnode = front;
front = temp;
}
else
{
front = end = temp;
}
size++;
}

// insertion of a digit in the end of a doubly linked list
void insertioninend(int data)
{
Node* temp = new Node(data);

if (end!= NULL)
{ end->nextnode = temp;
temp->prevnode = end;
end = temp;
}
else
{
front = end = temp;

}
size++;
}

// printing the doubly linked list  data
void displaydata()
{
Node* temp = front;

while (temp != NULL)
{
cout << temp->info;
temp = temp->nextnode;
}
}

int length()
{
return size;
}

Node* end;
Node* front;
int size;
};

//  function to add the numbers
{
int c = 0, s;

this->front = NULL;
this->end = NULL;
this->size = 0;

while (a1->end != NULL || b1->end != NULL)
{
if (a1->end != NULL && b1->end == NULL)
{
s = ((a1->end->info) + c) % 10;
c = ((a1->end->info) + c) / 10;
a1->end = a1->end->prevnode;
}
else if (a1->end == NULL && b1->end != NULL)
{
s = ((b1->end->info) + c) % 10;
c = ((b1->end->info) + c) / 10;
b1->end = b1->end->prevnode;
}
else if (a1->end != NULL && b1->end != NULL)
{
s = ((a1->end->info) + (b1->end->info) + c) % 10;
c = ((a1->end->info) + (b1->end->info) + c) / 10;
a1->end = a1->end->prevnode;
b1->end = b1->end->prevnode;
}

insertioninfront(s);
}

if (c != 0)
insertioninfront(c);
}

//  subtraction function
{
int c = 0, s;

this->front = NULL;
this->end = NULL;
this->size = 0;

while (a1->end != NULL || b1->end != NULL)
{
if (a1->end != NULL && b1->end != NULL)
{
if ((a1->end->info) + c < (b1->end->info))
{
s = ((a1->end->info) + c + 10 - (b1->end->info));
c = -1;
}
else if((a1->end->info) + c >=(b1->end->info))
{
s = ((a1->end->info) + c - (b1->end->info));
c = 0;
}
a1->end = a1->end->prevnode;
b1->end = b1->end->prevnode;
}
else if (a1->end != NULL && b1->end == NULL)
{
if (a1->end->info < 1)
{
if (c = 0)
{
s = a1->end->info;
}
else
s = ((a1->end->info) + 10 + c);
c = -1;
}
else if(a1->end->info>=1)
{
s = ((a1->end->info) + c);
c = 0;
}
a1->end = a1->end->prevnode;
}
insertioninfront(s);
}
}

// compares two numbers and then return 1
{
if (a->size != b->size)
return ((a->size > b->size) ? 1 : 0);

while (a1->front != NULL && b1->front != NULL)
{

if (a1->front->info < b1->front->info)
return 0;
else if (a1->front->info > b1->front->info)
return 1;
else
{
a1->front = a1->front->nextnode;
b1->front = b1->front->nextnode;
}
}
return 2;
}

// Returns the quotient by doing the division of two numbers
{
int i = 0;
for (i = 0; i < b1->size; i++)
{
ex->insertioninend(a1->front->info);
a1->front = a1->front->nextnode;
}

for (i = 0; i < 10; i++)
{
mp->insertioninend(i);
pr->mul(b2, mp);
if (!cmp(ex, pr))
break;
mp->front = mp->end = NULL;
pr->front = pr->end = NULL;
mp->size = pr->size = 0;
}

mp->front = mp->end = NULL;
pr->front = pr->end = NULL;
mp->size = pr->size = 0;

mp->insertioninend(i - 1);
pr->mul(b1, mp);
ex->dif(ex, pr);
insertioninend(i - 1);
mp->front = mp->end = NULL;
pr->front = pr->end = NULL;
mp->size = pr->size = 0;

while (a1->front != NULL)
{
ex->insertioninend(a1->front->info);
while (ex->front->info == 0)
{
ex->front = ex->front->nextnode;
ex->size--;
}
for (i = 0; i < 10; i++)
{
mp->insertioninend(i);
pr->mul(b2, mp);
if (!cmp(ex, pr))
break;
mp->front = mp->end = NULL;
pr->front = pr->end = NULL;
mp->size = pr->size = 0;
}

mp->front = mp->end = NULL;
pr->front = pr->end = NULL;
mp->size = pr->size = 0;

mp->insertioninend(i - 1);
pr->mul(b1, mp);
ex->dif(ex, pr);

insertioninend(i - 1);

mp->front = mp->end = NULL;
pr->front = pr->end = NULL;
mp->size = pr->size = 0;

a1->front = a1->front->nextnode;
}

cout<< "\nModulus : ";
ex->displaydata();
}

// multiplication function
{
int k = 0, i;
while (b->end != NULL)
{
int c = 0, s = 0;
while (temp->end != NULL)
{
s = ((temp->end->info) * (b->end->info) + c) % 10;
c = ((temp->end->info) * (b->end->info) + c) / 10;
pro->insertioninfront(s);
temp->end = temp->end->prevnode;
}
if (c != 0)
pro->insertioninfront(c);

for (i = 0; i < k; i++)
pro->insertioninend(0);

k++;
b->end = b->end->prevnode;
pro->front = pro->end = NULL;
pro->size = 0;
}
}

// main function
int main()
{

string s1,s2;
cout<<"enter the string s1 ";
getline (cin, s1);
cout<<"enter the string s2 ";
getline (cin,s2);

for (int i = 0; i < s1.length(); i++)
m->insertioninend(s1.at(i) - '0');

for (int i = 0; i < s2.length(); i++)
n->insertioninend(s2.at(i) - '0');

cout << "Product : ";
s->mul(m, n);
s->displaydata();
cout << endl;

cout << "Sum : ";
p->displaydata();
cout << endl;

cout << "Difference (m-n) : m>n: ";

d->dif(m2, n2);
d->displaydata();
q->quo(m3, n3);
cout << endl;

cout << "Quotient : ";
q->displaydata();
return 0;
}``````

Output

#### Complexity analysis

Time complexity

Since we are using one for loop to traverse the linked list of N nodes multiple times therefore the time complexity would be O(N).

Space complexity

O(1), will be the space complexity as we have not used any extra space.

### Why is deleting faster from a doubly-linked list?

A doubly-linked list allows you to delete it at O ​​(1) while a singly linked list will require O (n) time. because the size of the linked list is equal to the number of nodes present in the linked list.

### What is the significance of the forward and backward pointers in a doubly-linked list?

Since the Double Linked List has both the next and previous pointers, this allows us to traverse in both directions from the given Node. We can go to the previous node by following the previous pointer, and similarly, go to the next node by following the next pointers.

### What are the limits of a doubly-linked list?

It consumes more memory space compared to a single linked list because of the previous pointers. It is not possible to access the list items randomly because they are stored in random locations, and we can access them only in sequence.

## Conclusion

In this article, we have discussed the problem to perform large arithmetic operations using a doubly-linked list, we have discussed sample examples to give a clear idea about what the question is asking us to do, and we have also seen the implementation of the problem in C++.

After reading about the problem, are you not feeling excited to read/explore more articles on the topic of file systems? Don't worry; Coding Ninjas has you covered.

If you want to practice the questions on the doubly linked list then you can refer to these questions:

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass