Add two numbers in a single linked list
Introduction to Single Linked List:
A singly linked list is a fundamental data structure in computer science used to organize and store a sequence of elements called nodes. In a single linked list, each node contains two components: data and a reference (or link) to the next node in the sequence. The last node in the list typically has a null reference, indicating the end of the list.
Key aspects of a singly linked list are:
 Node Structure:
 Each node in a singly linked list contains two fields:
data
to store the actual value or payload, andnext
to store the reference (link) to the next node in the sequence.
 Each node in a singly linked list contains two fields:
 Head:
 The first node in the linked list is called the head. It serves as the starting point for traversing the list.
 Traversal:
 To traverse a singly linked list, you start at the head and follow the
next
references until you reach the end of the list (wherenext
is null).
 To traverse a singly linked list, you start at the head and follow the
 Dynamic Size:
 Unlike arrays, linked lists can dynamically grow or shrink in size. Nodes can be easily added or removed from anywhere in the list.
 Insertion and Deletion:
 Inserting a new node involves updating the
next
reference of an existing node to point to the new node. Similarly, deleting a node involves updating thenext
reference of the preceding node to bypass the node being removed.
 Inserting a new node involves updating the
 Random Access:
 Unlike arrays, singly linked lists do not support direct access to elements by index. To access an element, you need to traverse the list from the head.
 Memory Efficiency:
 Singly linked lists can be more memoryefficient than arrays for certain operations, especially in scenarios where the size of the data structure changes frequently.
 Applications:
 Singly linked lists are used in various applications, such as implementing dynamic data structures like stacks, queues, and symbol tables. They are also employed in scenarios where frequent insertions and deletions are expected.
Understanding Adding two numbers in a single linked list through an Example:
Example to illustrate how to add two numbers represented as single linked lists.
Example:
Note: Each node in the linked list contains a digit of the number, and the linked list is used to represent a multidigit number in reverse order.
Suppose we want to add the numbers:
Number 1: (2 → 4 → 3) (represents 342)
Number 2: (5 → 6 → 4) (represents 465)
Execution:

Initialize Linked Lists:

Convert the given numbers into linked lists:
Number 1: 2 > 4 > 3 Number 2: 5 > 6 > 4


Addition Process:

Start iterating through both linked lists, node by node.

At each step, add the corresponding digits along with any carry from the previous step.
Explain Iteration 1:  Digits: 2 + 5 = 7 (no carry)  Result: 7 > None Iteration 2:  Digits: 4 + 6 = 10 (carry 1)  Result: 7 > 0 > None Iteration 3:  Digits: 3 + 4 + 1 (carry from previous step) = 8 (no carry)  Result: 7 > 0 > 8 > None


Final Result:
 The final result linked list is (7 → 0 → 8), which represents the number 807.
Conclusion:
Adding two numbers in a single linked list involves iterating through both lists, performing digitwise addition, and considering any carry that might arise. The resulting linked list represents the sum of the two numbers.
Working Principle:
1. Initialization:
 Initialize a Dummy Head:
 Create a dummy head node to simplify the addition process. This dummy head is not part of the final result but helps in handling edge cases at the head of the resulting linked list.
 Initialize Pointers:
 Initialize pointers for the current node in the result, as well as pointers for the current nodes in the two input linked lists (
l1
andl2
).
 Initialize pointers for the current node in the result, as well as pointers for the current nodes in the two input linked lists (
2. Iterative Addition:
 Iterate Through the Linked Lists:
 Use a loop to iterate through both linked lists (
l1
andl2
) until both lists and any carry are exhausted.
 Use a loop to iterate through both linked lists (
 Extract Digits:
 Extract the values of the current nodes in both linked lists (
x
froml1
andy
froml2
). If a node isNone
, consider the value as 0.
 Extract the values of the current nodes in both linked lists (
 Perform Addition:
 Add the values of the current nodes along with any carry from the previous step.
 Calculate the sum (
total_sum
) and the carry for the next iteration.
 Create Result Node:
 Create a new node with the digit of the current sum and append it to the result linked list.
 Move to the Next Nodes:
 Move the pointers to the next nodes in both linked lists (
l1
andl2
).
 Move the pointers to the next nodes in both linked lists (
3. Finalization:
 Handle Any Remaining Carry:
 After the loop, if there is still a carry, create an additional node with the carry.
 Return Result:
 Return the next node of the dummy head, as the dummy head was used to simplify the process and is not part of the final result.
Conclusion:
The working principle involves a systematic traversal of the linked lists, digitwise addition, and careful consideration of carry at each step. The dummy head simplifies the addition process, and the result is a new linked list representing the sum of the two input numbers. The provided Python code blog encapsulates this working principle in the add_two_numbers
function.
Advantages of Addition in Single Linked List:
Advantages of Addition in Single Linked List:
 Dynamic Size:
 Single linked lists allow for dynamic sizing. Elements can be added or removed without the need to predefine the size of the data structure. This flexibility is advantageous when dealing with varying amounts of data.
 Efficient Insertion and Deletion:
 Adding elements to or removing elements from a single linked list is more efficient compared to arrays. Insertion and deletion operations involve updating references, which can be done in constant time if the position of the node is known.
 Memory Efficiency:
 Single linked lists can be more memoryefficient than arrays, especially when the size of the data structure changes frequently. This is because nodes can be allocated and deallocated individually without the need for contiguous memory blocks.
 No Preallocation of Memory:
 Unlike arrays, there's no need to preallocate memory for a single linked list. Memory is allocated onthefly as nodes are added, which is particularly beneficial when the size of the data structure is unknown or varies.
 Ease of Implementation:
 Implementing addition in a single linked list is often simpler compared to dynamic arrays or other complex data structures. The structure of a linked list allows for straightforward traversal and manipulation.
 Support for Infinite Size:
 In theory, a single linked list can support an infinite number of elements. As long as there is available memory, nodes can be added to the list, making it suitable for scenarios where the size of the data set is not known in advance.
 No Wasted Memory:
 Memory is used more efficiently in a single linked list compared to dynamic arrays, where memory needs to be preallocated. In a linked list, memory is allocated precisely for the elements that are present, reducing wasted space.
 Simplified Algorithm Design:
 Algorithms for addition or other operations on single linked lists can be simplified due to the sequential nature of the structure. There's no need to worry about shifting elements or resizing memory blocks, as is often the case with arrays.
 Ease of Rearrangement:
 Rearranging elements in a single linked list is relatively straightforward. It involves updating the
next
references, allowing for efficient reordering of elements without the need to move large chunks of memory.
 Rearranging elements in a single linked list is relatively straightforward. It involves updating the
 Adaptability to Changing Requirements:
 Single linked lists are wellsuited for scenarios where the data structure requirements may change frequently. They provide adaptability to dynamic data sets and can accommodate modifications without significant overhead.
In summary, the advantages of performing addition in a single linked list lie in its dynamic nature, efficient insertion and deletion, memory efficiency, and adaptability to varying data sizes. These characteristics make single linked lists a suitable choice for certain applications and algorithmic scenarios.
Disadvantages of Adding two numbers in Single Linked List :
 Sequential Access:
 Single linked lists require sequential access to reach a specific node. This can be inefficient when direct access to elements is needed, as it involves traversing the list from the head to the desired node.
 Memory Overhead:
 Each node in a single linked list requires additional memory to store the data and the reference to the next node. This can result in higher memory overhead compared to contiguous memory structures like arrays.
 No Random Access:
 Unlike arrays, single linked lists do not support direct access to elements by index. Accessing an element requires traversing the list from the head, which can be inefficient for certain operations.
 Increased Cache Misses:
 Due to noncontiguous memory allocation, traversing a single linked list may result in increased cache misses compared to arrays. This can impact the performance, especially in scenarios where memory access patterns are crucial.
 Traversal Overhead:
 Traversing a linked list involves following references from one node to the next. This introduces additional traversal overhead, which can impact the efficiency of algorithms, particularly when dealing with large datasets.
 Limited Parallelism:
 Operations on single linked lists may have limited parallelism, as each operation often depends on the completion of the previous one. This can be a disadvantage in scenarios where parallel processing is critical.
 Not CacheFriendly:
 The noncontiguous nature of linked lists can lead to poor cache locality, resulting in less efficient use of the CPU cache. This can adversely affect the performance of certain operations.
 Extra Storage for References:
 Storing references to the next node in addition to the actual data consumes extra storage. In scenarios with tight memory constraints, this additional overhead may be a drawback.
 Complexity in Reverse Traversal:
 Performing operations in reverse order, such as traversing the list from the tail to the head, can be less efficient and more complex than forward traversal.
 Potential for Memory Fragmentation:
 Frequent node allocation and deallocation in a linked list may lead to memory fragmentation, especially in languages without automatic memory management. This fragmentation can affect the overall system performance.
Real World Scenarios of Adding two numbers in a Single Linked List:
The addition of two numbers in a single linked list can be encountered in various realworld scenarios.
 Arbitrary Precision Arithmetic:
 In cryptography, numerical calculations, or any scenario where precision matters, addition of large numbers might be performed using linked lists. This is especially true when the numbers are too large to be stored in standard data types like integers.
 Financial Transactions:
 In financial applications, when dealing with currency or accounting, it's common to represent monetary values with linked lists. Adding transaction amounts or performing financial calculations may involve adding two numbers stored in linked lists.
 Scientific Computing:
 Scientific simulations or computations might involve working with numbers of varying precision. Linked lists can be used to represent and manipulate these numbers, and adding them may be a part of the simulation process.
 Representation of Polynomials:
 Polynomials can be represented using linked lists, where each node represents a term in the polynomial. Adding two polynomials involves adding corresponding terms, and the result can be represented as a new linked list.
 Large Data Processing:
 In data processing applications dealing with very large datasets, the use of linked lists might be more efficient due to their dynamic nature. Adding values or performing calculations on large datasets can be more manageable with linked lists.
 Network Packet Processing:
 In networking, linked lists may be used to represent and process data packets. When aggregating or combining information from multiple packets, the addition of numerical values might be necessary.
 Symbolic Mathematics:
 Systems that deal with symbolic mathematics, such as computer algebra systems, might use linked lists to represent mathematical expressions. Adding two expressions or symbolic numbers involves manipulating the linked list structure.
 Resource Management in Operating Systems:
 Operating systems often manage resources using linked data structures. When tracking resource usage or managing quotas, adding resource values in a linked list can be part of the resource management algorithms.
 Game Development:
 In game development, especially in simulations or strategy games, linked lists might be employed to manage game resources or perform calculations involving various attributes. Adding numerical values can be a common operation in such scenarios.
 GPS Navigation:
 In GPS navigation systems, coordinates and distances might be stored using linked lists. Calculations involving these geographical values, such as adding distances or finding the next location, could involve adding two numbers stored in linked lists.
Code in Python:
'''Copyrights to venkys.io
For more information, visite https://venkys.io"/
Python program to add two numbers in a linked list'''
# Stable : Yes
# Inplace : Yes
# Adaptive : Yes
# Space complexity: O(max(N,M)), where N and M are the lengths of input linked lists.
#Time Complexity: O(max(N,M)), where N and M are the lengths of input linked lists.
# Constructor method for the Node class
class Node:
def __init__(self,data):
self.data=data # Store the provided data in the 'data' attribute of the node
self.next=None # Initialize the 'next' attribute to None, as this node is not yet connected to another node.
def printLLReverse(head):
#Function to print linked list in reverse order
stack=[]
# Traverse the linked list and push each node's data onto the stack
while head:
stack.append(head.data)
head=head.next
# Pop each element from the stack and print it in reverse order
while stack:
print(stack.pop(),end="")
# Print a newline to separate the reversed data from the rest of the output
print()
'''def printLL(head):
#Function to print the linked list
while head:
print(head.data,end=">")
head=head.next
print()'''
def buildLL(arr):
#Function to build a linked list from an array
temp=Node(0)
head=temp
for i in arr:
# Create a new node with the current array element
temp.next=Node(i)
# Move the temporary pointer to the newly created node
temp=temp.next
return head.next
def addTwoNumbers(l1,l2):
#Function to add two numbers represented as linked lists
temp=Node(0)
head=temp
c=0
# loop until there are elements in either l1,;2 or there is carry.
while l1 or l2 or c:
# add corresponding digits from l1,l2 along with carry
if l1:
c+=l1.data
l1=l1.next
if l2:
c+=l2.data
l2=l2.next
#Create a new node with sum%10 and update carry
temp.next=Node(c%10)
c=c//10
temp=temp.next
return head.next
def main():
# Prompt the user to enter the first number
print("Enter first number:", end=" ")
num1 = input()
l1 = buildLL([int(x) for x in num1.split()])
# Prompt the user to enter the second number
print("Enter Second number:", end=" ")
num2 = input()
l2 = buildLL([int(x) for x in num2.split()])
# Print the reverse of the linked list representing the sum (result)
print("Sum of two numbers: ", end=" ")
ans = addTwoNumbers(l1, l2)
printLLReverse(ans)
if __name__ == "__main__":
main()
 The
Node
class is defined to create nodes for the linked list. Each node has adata
attribute representing a digit and anext
attribute pointing to the next node in the list.  The
printLLReverse
function is defined to print the linked list. It takes the head of the linked list as an argument and traverses the list in reverse order, printing each node's data.  The
buildLL
function is defined to build a linked list from an input array. It creates a dummy node, iterates through the array, and appends nodes with array elements as data to the linked list.  The
addTwoNumbers
function takes two linked lists representing two numbers and returns a new linked list representing their sum. It uses a temporary dummy node (head
) to build the result linked list.  Inside the
addTwoNumbers
function: A temporary node
temp
is initialized as the head of the result linked list.  A variable
c
is initialized to 0, representing the carry.  A while loop runs until there are elements in either of the input linked lists (
l1
orl2
) or there is a carry (c
).  Inside the loop, the code adds the corresponding digits from
l1
andl2
, along with the carry, and updatesc
and the result digit in the new linked list.  The carry is updated as the floor division of the sum by 10.
 The new digit is appended to the result linked list.
 Move to the next node in the result linked list.
 A temporary node
Code in C++:
/*Copyrights to venkys.io
For more information, visite https://venkys.io"/
C++ program to add two numbers in a linked list*/// Stable : Yes
// Inplace : Yes
// Adaptive : Yes
// Space complexity: (max(N, M)), where N and M are the lengths of the input linked lists.
//The extra space is used to store the resulting linked list.
//Time Complexity:O(max(N, M)), where N and M are the lengths of the input linked lists.
#include <iostream> // It is a standard C++ header file that includes declarations for the standard input/output stream objects like cout, cin, etc.
#include <vector> // Includes the Standard Template Library (STL) vector header for dynamic arrays.
#include <limits> // Include the header for numeric_limits
using namespace std; // Using the standard namespace for simplifying code
// Node class representing a node in a linked list
class Node {
public:
int data;
Node* next = NULL; // Pointer to the next node in the linked list, initially set to NULL
// Constructor to initialize a node with the given value
Node(int val) {
data = val;
}
};
//Function to print the linked list in reverse without arrows
void printReverse(Node* head){
// Base case: If the current node is NULL (end of the list), return
if (head==NULL){
return;
}
// Recursive call: Move to the next node in the list
printReverse(head>next);
// Print the data of the current node
cout << head>data << "";
}
/*// Function to print the linked list
void print(Node* head) {
Node* temp = head;
while (temp != NULL) {
cout << temp>data << ">";
temp = temp>next;
}
cout << endl;
}
*/
// Function to build a linked list with a single node
Node* buildSingleNode(int val) {
return new Node(val);
}
// Function to add two numbers represented as linked lists
Node* addTwoNumbers(Node* l1, Node* l2) {
// Create a temporary node to serve as the dummy head of the result linked list
Node* temp = new Node(0);
// Pointer to the head of the result linked list
Node* head = temp;
// Variable to store the carry during addition
int c = 0;
// Loop until there are elements in either l1 or l2, or there is a carry
while (l1 != NULL  l2 != NULL  c != 0) {
// Add corresponding digits from l1 and l2, along with the carry
if (l1 != NULL) {
c += l1>data;
l1 = l1>next;
}
if (l2 != NULL) {
c += l2>data;
l2 = l2>next;
}
// Create a new node with the sum % 10 and update carry
temp>next = new Node(c % 10);
c = c / 10;
temp = temp>next;
}
// Return the result linked list starting from the second node (as the first node is the dummy head)
return head>next;
}
int main() {
int num1, num2;
// Input the first number
cout << "Enter the first number: ";
cin >> num1;
// Input the second number
cout << "Enter the second number: ";
cin >> num2;
// Create linked lists with a single node for each number
Node* l1 = buildSingleNode(num1);
Node* l2 = buildSingleNode(num2);
// Add the two numbers and print the result
Node* ans = addTwoNumbers(l1, l2);
cout << "Sum of the two numbers: ";
printReverse(ans);
cout << endl;
// Cleanup: Release memory
delete l1;
delete l2;
delete ans;
return 0;
}
Code in Java:
/*Copyrights to venkys.io
For more information, visit https://venkys.io"/
Java program to add two numbers in a linked list*/
// Stable : Yes
// Inplace : Yes
// Adaptive :Yes
// Space complexity: (max(N, M)), where N and M are the lengths of the input linked lists.
//The extra space is used to store the resulting linked list.
//Time Complexity:O(max(N, M)), where N and M are the lengths of the input linked lists.
import java.util.Scanner; //Importing scanner class from java.util package for user input
//Node class representing a node in linked list
class Node{
int data;
Node next;
//Constructor to initialize a node with given data
Node(int data){
this.data=data;
}
}
public class Linkedlistsum{
// Function to print the linked list in reverse order
static void printReverse(Node head) {
// Base case: If the current node is null, return
if (head == null) {
return;
}
// Recursive call: Move to the next node and print it in reverse order
printReverse(head.next);
// Print the data of the current node
System.out.print(head.data);
}
/* This function displays the actual data order stored in linked list
static void print(Node head){
Node temp=head;
while(temp!=null){
System.out.print(temp.data+">");
temp=temp.next;
}
System.out.println();
}*/
// Function to build a linked list from an array
static Node buildll(int[] arr){
Node temp=new Node(0); // Create a dummy node to serve as the head of the linked list
Node head=temp; // Store the reference to the head of the linked list
for(int i=0;i<arr.length;i++){
temp.next=new Node(arr[i]); //Create a new node with array element and link it
temp=temp.next; // Move the temporary pointer to newly created node
}
return head.next; // Return the actual head of the linked list (skip the dummy node)
}
// Function to add two numbers represented as linked lists
static Node addTwoNumbers(Node l1,Node l2){
Node temp=new Node(0); //Create a dummy node
Node head=temp; // Keep a reference to the head of the linked list
int c=0; // Initialize the carry to 0
// Continue adding digits until both input linked lists are processed, and there is no carry left
while(l1!=null  l2!=null  c!=0){
// Add the current digits of l1, l2, and the carry
if(l1!=null){
c+=l1.data;
l1=l1.next;
}
if(l2!=null){
c+=l2.data;
l2=l2.next;
}
temp.next=new Node(c%10); //Create a new node with the digit sum and link it
c=c/10; //Update the carry for the next iteration
temp=temp.next; //Move the temporary Pointer to the newly created node
}
return head.next; //Return the head of the resulting linked list(skipping dummy node)
}
public static void main(String[] args) {
// Input for the first number
System.out.print("Enter first number:");
Scanner scanner = new Scanner(System.in);
String[] input1 = scanner.nextLine().split(" ");
int[] a1 = new int[input1.length];
for (int i = 0; i < input1.length; i++) {
a1[i] = Integer.parseInt(input1[i]);
}
// Input for the second number
System.out.print("Enter second number:");
String[] input2 = scanner.nextLine().split(" ");
int[] a2 = new int[input2.length];
for (int i = 0; i < input2.length; i++) {
a2[i] = Integer.parseInt(input2[i]);
}
// Build linked lists
Node l1=buildll(a1);
Node l2=buildll(a2);
Node ans=addTwoNumbers(l1, l2);
System.out.print("Sum of two numbers:");
printReverse(ans);
System.out.println();
// Close the scanner
scanner.close();
}
}
Sample Test Cases:
Example 1:
Input:
Enter first number: 243
Enter second number: 564
Output:
Sum of two numbers: 807
Example 2:
Input:
Enter first number: 999
Enter second number: 1
Output:
Sum of two numbers: 1000
Example 3:
Input:
Enter first number: 005
Enter second number: 005
Output:
Sum of two numbers: 10