1.
Introduction
2.
Problem Statement
3.
Space Efficient Approach
3.1.
Algorithm
3.2.
DRY Run
3.3.
Implementation in C++
3.4.
Implementation in Java
3.5.
Implementation in Python
3.6.
Complexity Analysis
4.
4.1.
Do linked lists need pre-allocated memory like arrays?
4.2.
How to insert operations in an array is different from the insert operation in a linked list.
4.3.
4.4.
Mention a few applications on the linked list.
4.5.
What is cache locality? And which has better cache locality among arrays and linked lists?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

In the previous blogs on adding two numbers represented by linked lists, we discussed and implemented two approaches. First, we add the nodes of both the linked list one by one simultaneously by adding preceding zeroes to the shorter linked list, and in another approach, we use stacks to add two numbers represented by the linked lists.

In this blog, we will now learn about the space-efficient approach, which takes constant space to add two numbers represented by the linked lists, but before diving into the solution, let's briefly discuss the problem again.

## Problem Statement

The problem states there are two linked lists such that all the nodes of these linked lists contain numbers between 1 to 9. Now we are asked to find the sum of the numbers formed by these linked lists treating nodes as the digits of a number.

For example,

Input

Numbers of Nodes in linked list 1 and 2: 4 3

Nodes in linked list 1: 3 -> 4 -> 2 -> 6

Nodes in linked list 2: 7 -> 3 -> 2

Output

4 -> 1 -> 5->8

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Space Efficient Approach

This approach aims to add two numbers represented by the linked lists in constant space. For this, rather than storing the sum in a separate linked list, we modify the larger linked list to store the sum and return it as the resultant linked list.

We start with finding the larger linked list, then traverse through the linked lists and store the sum for each pair of nodes and the carry from the previous nodes in the nodes of the larger linked list.

We replace the value of the shorter linked list's nodes with zeroes for the addition if we have traversed through all of its nodes. And once we are done traversing the larger linked list, we check for the carry; if it is one, we add one as an extra node to the larger linked list. And return it as the resultant linked list.

### Algorithm

1. Take the user input for both linked lists.

2. Find the sizes of the linked list to find the larger linked list.

3. We reverse the linked lists so that the pointers point to the least significant digit of the number they represent.

4. Then, we add each pair of nodes corresponding to the same place value in the number, along with the carry from the previous pair. And replace the node of the larger linked list with the sum.

5. After traversing the shorter linked list, we put zero in place of the value of its node.

6. Add an extra node into the linked list if carry after the last node is 1.

7. Return the larger linked list as the resultant and reverse it.

8. Print the resultant linked list.

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

// Structure for a node in the linked list.
struct node {
int data;
struct node * next;
};

// For creating a new node for a number.
node* createnode(int value) {
node *newnode = new node();
newnode->data = value;
newnode->next = nullptr;
return newnode;
}

int carry = 0, sum;
/*
Create a temporary variable to traverse through the larger linked list.
*/

/*
*/
node *last = nullptr;

/*
Using a loop to add the numbers in the nodes of both the linked lists.

To calculate the sum of current nodes of the linked lists and
the carry from the addition of the last nodes.

Setting the carry variable to 1, if value of the sum is greater than 10.
*/

/*
If sum is greater than 10 then will take carry=sum/10 and
add the sum%10 in the resultant.
*/
while (temp != nullptr) {

carry = (sum >= 10) ? 1 : 0;

sum = sum % 10;
temp->data = sum;

last = temp;

if (temp) {
temp = temp->next;
}

}
}

/*
If we are left only with a carry in the last,
we create a new node with it and append it.
*/
if (carry > 0) {
struct node *car = createnode(carry);
last->next = car;
}

}

// Function to reverse the linked lists.
}

// Reversing the list.

/*
*/
}

// Function to push nodes into the list.
void push(struct node **headr, int newval) {
struct node *newnode = createnode(newval);
}

// Driver function.
int main() {

struct node* sumlist;
/*
Passing the largest Linkedlist as the second argument.
*/

// Reversing the resultant linked list.
sumlist = reverse(sumlist);

// Printing the resultant linked list.
cout << "Resultant Linked list: ";
while (sumlist != nullptr) {
cout << sumlist->data << " ";
sumlist = sumlist->next;
}

return 0;
}``````

Output

### Implementation in Java

``````import java.util.*;

class Node {
int data;
Node next;

// Constructor
Node(int d) {
data = d;
next = null;
}
}

// Helper function to Print
}
}

/*
*/
void insert(int x) {
Node temp = new Node(x);
else {
}
}

/*
Helper function to reverse the list
*/
public static Node reverse(Node head) {

Node prev = null;
while (curr != null) {
Node temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
}

// Function to add two lists
public static Node sum(Node l1, Node l2) {
if (l2 == null) return l1;
if (l1 == null) return l2;

/*
whose reverse is to be returned
*/
Node prev = null;
int c = 0, sum;
while (l1 != null && l2 != null) {
sum = c + l1.data + l2.data;
l1.data = sum % 10;
c = sum / 10;
prev = l1;
l1 = l1.next;
l2 = l2.next;
}

if (l1 != null || l2 != null) {
if (l2 != null) prev.next = l2;
l1 = prev.next;
while (l1 != null) {
sum = c + l1.data;
l1.data = sum % 10;
c = sum / 10;
prev = l1;
l1 = l1.next;
}
}
if (c > 0) prev.next = new Node(c);
}
}

/*
Driver Main Class
*/
class Main {
public static void main(String[] args) {
l1.insert(3);
l1.insert(4);
l1.insert(2);
l1.insert(6);

l2.insert(7);
l2.insert(3);
l2.insert(2);
}
}``````

Output

Also check out Addition of Two Numbers in Java here.

### Implementation in Python

``````#Structure for a node in the linked list.
class Node:

def __init__(self, data):

self.data = data
self.next = None

# Handle all List operations

def __init__(self):

# Method to Print list
def Print(self):

while temp:
temp = temp.next

# Method to insert data in linked list
def insert(self, data):

newNode = Node(data)

else:

# Helper function to reverse the list

prev = None

while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp

# Function to add two lists
def listSum(l1, l2):

if l1 is None:
return l1
if l2 is None:
return l2

# is to be returned This is
# where which will be final node
prev = None
c = 0
sum = 0

while l1 is not None and l2 is not None:
sum = c + l1.data + l2.data
l1.data = sum % 10
c = int(sum / 10)
prev = l1
l1 = l1.next
l2 = l2.next

if l1 is not None or l2 is not None:
if l2 is not None:
prev.next = l2
l1 = prev.next

while l1 is not None:
sum = c + l1.data
l1.data = sum % 10
c = int(sum / 10)
prev = l1
l1 = l1.next

if c > 0:
prev.next = Node(c)

# Driver code

``````

Output

### Complexity Analysis

The time complexity for this approach is - O(NL)  because the maximum number of nodes we traverse in a loop will be  NL, where Nis the number of nodes in the larger linked list.

The space complexity for this approach will be - O(1).

### Do linked lists need pre-allocated memory like arrays?

No, linked lists don't need pre-allocated memory during declaration. Rather we use dynamic memory location in the case of linked lists.

### How to insert operations in an array is different from the insert operation in a linked list.

Insert operation in an array might need to shift a few elements to make space for the new element, as the memory allocation is contiguous in arrays. In contrast, in the linked list, we can insert a new node in the linked without shifting any element.

It does not allow random access to elements, and we can not traverse through a linked list in the reverse direction.

### Mention a few applications on the linked list.

Applications of linked lists involve the implementation of stacks and queues and storing adjacency lists in case of implementation of graphs.

### What is cache locality? And which has better cache locality among arrays and linked lists?

Cache locality refers to the tendency of future operations to be available in the cache. In arrays, all elements are in contiguous memory locations. Thus it has better cache locality than linked lists.

## Conclusion

This blog discussed the space-efficient approach to adding two numbers represented by the linked lists. We have discussed the problem statement with the help of a visual demonstration. We have also implemented the problem in three coding languages.