home
Naukri Code 360
expand-more
Library
expand-more
Large number arithmetic using doubly linked list
Table of contents
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.
Frequently Asked Questions
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

Author Ashish Sharma
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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.

  

Doubly linked list

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 

// addition function
  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;
// Doubly Linked List structure
struct Node
{
    int info;
    struct Node* nextnode;
    struct Node* prevnode;
// constructor
    Node(int val)
    {
    info = val;
    nextnode = prevnode = NULL;
}
};


class hugeIntegerlinkedlist
{
public:
    hugeIntegerlinkedlist()
    {
    front = end = NULL;
    size = 0;
    }
    ~hugeIntegerlinkedlist();
  
    //  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;
    }

    void mul(hugeIntegerlinkedlist*, hugeIntegerlinkedlist*);
    void dif(hugeIntegerlinkedlist*, hugeIntegerlinkedlist*);
    void add(hugeIntegerlinkedlist*, hugeIntegerlinkedlist*);
    int cmp(hugeIntegerlinkedlist*, hugeIntegerlinkedlist*);
    void quo(hugeIntegerlinkedlist*, hugeIntegerlinkedlist*);
    Node* end;
    Node* front;
    int size;
};
  
//  function to add the numbers
void hugeIntegerlinkedlist::add(hugeIntegerlinkedlist* a, hugeIntegerlinkedlist* b)
{
    int c = 0, s;
    hugeIntegerlinkedlist* a1 = new hugeIntegerlinkedlist(*a);
    hugeIntegerlinkedlist* b1 = new hugeIntegerlinkedlist(*b);
  
    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 
void hugeIntegerlinkedlist::dif(hugeIntegerlinkedlist* a, hugeIntegerlinkedlist* b)
{
    int c = 0, s;
    hugeIntegerlinkedlist* a1 = new hugeIntegerlinkedlist(*a);
    hugeIntegerlinkedlist* b1 = new hugeIntegerlinkedlist(*b);
  
    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
int hugeIntegerlinkedlist::cmp(hugeIntegerlinkedlist* a, hugeIntegerlinkedlist* b)
{
    if (a->size != b->size)
        return ((a->size > b->size) ? 1 : 0);
  
    hugeIntegerlinkedlist* a1 = new hugeIntegerlinkedlist(*a);
    hugeIntegerlinkedlist* b1 = new hugeIntegerlinkedlist(*b);
    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
void hugeIntegerlinkedlist::quo(hugeIntegerlinkedlist* a, hugeIntegerlinkedlist* b)
{
    hugeIntegerlinkedlist* a1 = new hugeIntegerlinkedlist(*a);
    hugeIntegerlinkedlist* b1 = new hugeIntegerlinkedlist(*b);
    hugeIntegerlinkedlist* ex = new hugeIntegerlinkedlist();
    hugeIntegerlinkedlist* mp = new hugeIntegerlinkedlist();
    hugeIntegerlinkedlist* pr = new hugeIntegerlinkedlist();
    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++)
    {
        hugeIntegerlinkedlist* b2 = new hugeIntegerlinkedlist(*b);
        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++)
        {
            hugeIntegerlinkedlist* b2 = new hugeIntegerlinkedlist(*b);
            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
void hugeIntegerlinkedlist::mul(hugeIntegerlinkedlist* a, hugeIntegerlinkedlist* b)
{
    int k = 0, i;
    hugeIntegerlinkedlist* tpro = new hugeIntegerlinkedlist();
    while (b->end != NULL)
    {
        int c = 0, s = 0;
        hugeIntegerlinkedlist* temp = new hugeIntegerlinkedlist(*a);
        hugeIntegerlinkedlist* pro = new hugeIntegerlinkedlist();
        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);
  
        add(this, pro);
        k++;
        b->end = b->end->prevnode;
        pro->front = pro->end = NULL;
        pro->size = 0;
    }
}
  
// main function
int main()
{
    hugeIntegerlinkedlist* m = new hugeIntegerlinkedlist();
    hugeIntegerlinkedlist* n = new hugeIntegerlinkedlist();
    hugeIntegerlinkedlist* s = new hugeIntegerlinkedlist();
    hugeIntegerlinkedlist* p = new hugeIntegerlinkedlist();
    hugeIntegerlinkedlist* d = new hugeIntegerlinkedlist();
    hugeIntegerlinkedlist* q = new hugeIntegerlinkedlist();
  
     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');
  
    hugeIntegerlinkedlist* m1 = new hugeIntegerlinkedlist(*m);
    hugeIntegerlinkedlist* n1 = new hugeIntegerlinkedlist(*n);
    hugeIntegerlinkedlist* m2 = new hugeIntegerlinkedlist(*m);
    hugeIntegerlinkedlist* n2 = new hugeIntegerlinkedlist(*n);
    hugeIntegerlinkedlist* m3 = new hugeIntegerlinkedlist(*m);
    hugeIntegerlinkedlist* n3 = new hugeIntegerlinkedlist(*n);
  
    cout << "Product : ";
    s->mul(m, n);
    s->displaydata();
    cout << endl;
  
    cout << "Sum : ";
    p->add(m1, n1);
    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;
}
You can also try this code with Online C++ Compiler
Run Code

 

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.

Frequently Asked Questions

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:

  1. Find pair with the given sum in a doubly-linked list
  2. Reverse a doubly-linked list
  3. Quick sort on a doubly linked list
  4. Deletion in a doubly-linked list
  5. Flattening A Linked List

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System 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 problems, interview 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
author
Switch to top management roles with Online MBA
by Coding Ninjas
20 Jan, 2025
11:30 AM
discord 83+ registered
author
Transition to SDE Career with Online PG Certification by IIT
by Coding Ninjas
20 Jan, 2025
03:30 PM
discord 282+ registered
author
Transition to data career with Online PG Certification by IIT
by Coding Ninjas
21 Jan, 2025
01:30 PM
discord 36+ registered
author
Switch to top management roles with Online MBA
by Coding Ninjas
20 Jan, 2025
11:30 AM
discord 83+ registered
author
Transition to SDE Career with Online PG Certification by IIT
by Coding Ninjas
20 Jan, 2025
03:30 PM
discord 282+ registered
View more events