Add two numbers in a single linked list

• Venkys.io

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:

1. Node Structure:
   • Each node in a singly linked list contains two fields: data to store the actual value or payload, and next to store the reference (link) to the next node in the sequence.
2. Head:
   • The first node in the linked list is called the head. It serves as the starting point for traversing the list.
3. 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 (where next is null).
4. 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.
5. 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 the next reference of the preceding node to bypass the node being removed.
6. 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.
7. Memory Efficiency:
   • Singly linked lists can be more memory-efficient than arrays for certain operations, especially in scenarios where the size of the data structure changes frequently.
8. 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 multi-digit 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:

1. Initialize Linked Lists:

   • Convert the given numbers into linked lists:

     Number 1: 2 -> 4 -> 3
     Number 2: 5 -> 6 -> 4
     
     

2. 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
     
     

3. 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 digit-wise 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 and l2).

2. Iterative Addition:

• Iterate Through the Linked Lists:
  • Use a loop to iterate through both linked lists (l1 and l2) until both lists and any carry are exhausted.
• Extract Digits:
  • Extract the values of the current nodes in both linked lists (x from l1 and y from l2). If a node is None, consider the value as 0.
• 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 and l2).

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, digit-wise 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:

1. 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.
2. 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.
3. Memory Efficiency:
   • Single linked lists can be more memory-efficient 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.
4. No Pre-allocation of Memory:
   • Unlike arrays, there's no need to pre-allocate memory for a single linked list. Memory is allocated on-the-fly as nodes are added, which is particularly beneficial when the size of the data structure is unknown or varies.
5. 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.
6. 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.
7. No Wasted Memory:
   • Memory is used more efficiently in a single linked list compared to dynamic arrays, where memory needs to be pre-allocated. In a linked list, memory is allocated precisely for the elements that are present, reducing wasted space.
8. 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.
9. 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.
10. Adaptability to Changing Requirements:
    • Single linked lists are well-suited 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 :

1. 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.
2. 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.
3. 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.
4. Increased Cache Misses:
   • Due to non-contiguous 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.
5. 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.
6. 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.
7. Not Cache-Friendly:
   • The non-contiguous 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.
8. 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.
9. 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.
10. 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 real-world scenarios.

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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()

1. The Node class is defined to create nodes for the linked list. Each node has a data attribute representing a digit and a next attribute pointing to the next node in the list.
2. 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.
3. 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.
4. 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.
5. 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 or l2) or there is a carry (c).
   • Inside the loop, the code adds the corresponding digits from l1 and l2, along with the carry, and updates c 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.

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