How to reverse a linked list in Julia

Linked lists are fundamental data structures that play a vital role in programming. Reversing a linked list is a common problem. Julia, a high-performance programming language, offers various approaches to tackle this task efficiently. Reversing a linked list proves helpful in various scenarios. For example, imagine wanting to quickly revisit recently viewed websites by displaying them in reverse order. It’s also handy for efficiently managing a long to-do list, allowing for swift deletion of the last few tasks without extensive scrolling.

We’ll explore two methods to reverse a linked list in Julia and highlight their advantages and use cases.

Linked list reversal approaches

Let’s discuss iterative and recursive approaches to reverse the linked list.

Iterative reversal

The iterative reversal approach involves traversing the linked list while changing the direction of the links. The following illustration offers a better understanding of the solution:

mutable struct Node
    data
    next::Union{Node, Nothing}
end
function reverse_list_iterative(head::Node)
    prev = nothing
    current = head
    while current !== nothing
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    end
    return prev
end
# Function to print the linked list
function print_linked_list(head::Node)
    current = head
    while current !== nothing
        println(current.data)
        current = current.next
    end
end
# Function to create a linked list with specific numbers
function create_linked_list(numbers::Vector)
    if isempty(numbers)
        return nothing
    end
    nodes = [Node(numbers[1], nothing)]
    for i in 2:length(numbers)
        nodes[end].next = Node(numbers[i], nothing)
        push!(nodes, nodes[end].next)
    end
    return nodes[1]
end
# Example usage
numbers_in_list = [5, 9, 2, 7]
original_linked_list = create_linked_list(numbers_in_list)
# Original linked list
println("Original Linked List:")
print_linked_list(original_linked_list)
# Reversing using iterative approach
reversed_iterative = reverse_list_iterative(original_linked_list)
println("\nReversed Linked List (Iterative):")
print_linked_list(reversed_iterative)

Code explanation

Lines 1–4: We define a mutable struct named Node. This structure represents a node in a linked list. It has two fields: data, which can hold any type of data, and next, which is a reference to the next node in the linked list. The next field is of type Union{Node, Nothing}, indicating that it can either point to another node or be nothing to denote the end of the list.
Lines 6–18: We define a function reverse_list_iterative that takes the head of a linked list (head::Node) as an argument. The function reverses the linked list in place using an iterative approach. It uses three pointers (prev, current, and next_node) to traverse the list and modify the next pointers accordingly.
Lines 21–27: Here, we have a function named print_linked_list that takes the head of a linked list (head::Node) as an argument. The function iterates through the linked list, printing the data of each node. The loop continues until it reaches the end of the list where current becomes nothing.
Lines 30–43: We define a function create_linked_list that takes a vector of numbers as an argument (numbers::Vector). It creates a linked list with nodes containing the provided numbers. The function handles the case where the input vector is empty. It uses a loop to iterate through the numbers, creating nodes and linking them together to form a linked list.
Lines 46–56: We have an example usage of the defined functions. It creates a linked list using the create_linked_list function with a vector of numbers. Then, it prints the original linked list and its reversed version using the print_linked_list function.

Recursive reversal

We recursively visit each node in the provided linked list until we reach the last node in order to return the head of the new list. The last node in the list then takes over as the new head. Every node adds itself to the end of the partially reversed list on the return path.

Note: Detailed explanation about recursion can be found here.

In Julia, recursion can be a concise and elegant solution.

mutable struct Node
    data
    next::Union{Node, Nothing}
end
# Recursive reversal
function reverse_list_recursive(node::Union{Node, Nothing})
    if node === nothing || node.next === nothing
        return node
    end
    
    rem = reverse_list_recursive(node.next)
    node.next.next = node
    node.next = nothing
    return rem
end
# Function to print the linked list
function print_linked_list(head::Node)
    current = head
    while current !== nothing
        println(current.data)
        current = current.next
    end
end
# Function to create a linked list with specific numbers
function create_linked_list(numbers::Vector)
    if isempty(numbers)
        return nothing
    end
    nodes = [Node(numbers[1], nothing)]
    for i in 2:length(numbers)
        nodes[end].next = Node(numbers[i], nothing)
        push!(nodes, nodes[end].next)
    end
    return nodes[1]
end
# Example usage
numbers_in_list = [5, 9, 2, 7]
original_linked_list = create_linked_list(numbers_in_list)
# Original linked list
println("Original Linked List:")
print_linked_list(original_linked_list)
# Reversing using recursive approach
reversed_recursive = reverse_list_recursive(original_linked_list)
println("\nReversed Linked List (Recursive):")
print_linked_list(reversed_recursive)

Code explanation

Lines 7–16: The reverse_list_recursive function is designed to reverse a linked list using recursion. It operates by traversing the list recursively until it reaches the end. At each step, it reverses the pointers to gradually reverse the list. The function first checks if the current node or its next node is nothing, indicating the end of the list. If so, it returns the current node. Otherwise, it recursively calls itself with the next node. After the recursive call returns, it adjusts the pointers to reverse the link between nodes. Finally, it returns the head of the reversed list (rem).

Choosing the right approach

The choice between iterative and recursive approaches depends on factors like performance, readability, and memory usage. Iterative solutions are generally more memory-efficient. In iterative solutions, memory usage is constant because the variables used (e.g., pointers) are reused in each iteration, and there’s no additional memory overhead from function call stacks. This is in contrast to recursive solutions where each function call consumes space on the call stack. For large inputs, recursive solutions can exhaust the stack, leading to stack overflow errors, while iterative solutions remain memory-efficient due to their fixed space usage. Time complexity remains the same for both approaches. On the other hand, recursive solutions are good for readability.

Conclusion

In the realm of programming, the task of reversing a linked list is a frequently encountered challenge, and Julia presents diverse approaches to tackle this problem. Both iterative and recursive strategies in Julia provide efficient solutions for reversing linked lists, and the selection between them should be influenced by the unique requirements of our individual projects. Mastery of these techniques and their application in Julia not only sharpens our problem-solving abilities but also elevates us as more adept programmers.

Free Resources