Adding Two Numbers Represented by Linked Lists in Bash

This Bash program simulates adding two numbers where each number is represented by a linked list. Each node in the list represents a single digit. The digits are stored in arrays, with the least significant digit at the start of the array (representing the head of the list).

Program Code

#!/bin/bash

# Function to add two numbers represented as reversed arrays
add_linked_lists() {
    local -n list1=$1
    local -n list2=$2
    local carry=0
    local -a result=()

    local max_length=$(( ${#list1[@]} > ${#list2[@]} ? ${#list1[@]} : ${#list2[@]} ))

    for (( i=0; i<$max_length || carry; i++ )); do
        local sum=$(( ${list1[i]:-0} + ${list2[i]:-0} + carry ))
        result[i]=$(( sum % 10 ))
        carry=$(( sum / 10 ))
    done

    echo ${result[@]}
}

# Example usage:
# Represent numbers 243 (3->4->2) and 564 (4->6->5) by arrays
list1=(3 4 2)
list2=(4 6 5)

# Add the numbers
result=$(add_linked_lists list1 list2)
echo "Result: $result"

Explanation of the Code

The Bash script defines a function add_linked_lists that takes two arrays (list1 and list2) as input. Each array contains the digits of a number in reverse order (least significant digit first). The function calculates the sum of these two numbers assuming each digit is a node in a linked list.

The max_length determines the length of the longer array to iterate over all digits. The loop sums corresponding digits of both numbers and handles the carry for digits exceeding 9. If there is a carry left after the last digit, it is added to the result. The function returns the sum as an array with digits in reverse order, representing the resulting linked list.

Use Case and Output

When adding 243 and 564 represented as linked lists, the script outputs the digits of the result (807) as a linked list in reverse order (7 0 8), which corresponds to the number 807.