Reverse a Singly Linked List in Bash

Reversing a singly linked list is a common problem in computer science.
In this example, we’ll create a simple program in the Bash scripting language to achieve this.
The program will demonstrate how to define a linked list structure, reverse the list, and
print the reversed list.

Program Structure

The program consists of the following sections:

• Defining the linked list structure
• Creating nodes for the linked list
• Function to reverse the linked list
• Function to print the linked list
• Main function to execute the program

Code

#!/bin/bash

# Define a Node structure
declare -A LinkedList

# Create a function to add nodes to the linked list
add_node() {
    local value=$1
    local index=$2

    LinkedList["value_$index"]=$value
    LinkedList["next_$index"]=$((index + 1))
}

# Reverse the linked list
reverse_linked_list() {
    local prev_index=-1
    local current_index=0

    while [ -n "${LinkedList["value_$current_index"]}" ]; do
        local next_index=${LinkedList["next_$current_index"]}
        LinkedList["next_$current_index"]=$prev_index

        prev_index=$current_index
        current_index=$next_index
    done

    # Update the start of the list
    LinkedList["start"]=$prev_index
}

# Function to print the linked list
print_linked_list() {
    local current_index=${LinkedList["start"]}
    while [ $current_index -ge 0 ]; do
        echo -n "${LinkedList["value_$current_index"]} -> "
        current_index=${LinkedList["next_$current_index"]}
    done
    echo "NULL"
}

# Main function
main() {
    # Initialize linked list with nodes
    add_node 1 0
    add_node 2 1
    add_node 3 2
    add_node 4 3
    add_node 5 4

    # Set the start of the list
    LinkedList["start"]=0

    echo "Original Linked List:"
    print_linked_list

    # Reverse the linked list
    reverse_linked_list

    echo "Reversed Linked List:"
    print_linked_list
}

# Execute the main function
main
    

Explanation

This Bash script defines a simple singly linked list using associative arrays. Here’s a breakdown of the key parts of the code:

• add_node(): This function adds a node to the linked list by storing the value and a reference to the next node. The nodes are indexed by their position.
• reverse_linked_list(): This function reverses the linked list by iterating through the list and reversing the pointers between nodes. It updates the “next” reference to point to the previous node instead of the next one.
• print_linked_list(): This function prints the linked list from the start node to the end, showing the values in order.
• main(): The main function sets up the linked list, prints the original list, reverses it, and then prints the reversed list.

Output

When you run this script, the output will look like this:

Original Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> NULL
Reversed Linked List:
5 -> 4 -> 3 -> 2 -> 1 -> NULL
    

Conclusion

This script demonstrates how to reverse a singly linked list using Bash scripting.
While Bash is not typically used for such tasks, this example showcases the flexibility of the language and how basic data structures can be implemented in Bash.