如何将林纳斯·托瓦兹的「良好品味」理念应用于Fortran链表？

Great question! Linus's pointer-to-pointer trick from that TED talk is such an elegant way to cut out redundant if checks when working with linked lists, and it absolutely translates to Fortran—even though Fortran's pointer model is a bit different from C's. Let's walk through how to implement this clean, branch-free logic in Fortran.

First, Define the Linked List Type #

Just like in C, we start with a derived type for our list nodes. We'll initialize the next pointer to null() by default to avoid dangling pointers:

type :: list_entry
    integer :: val
    type(list_entry), pointer :: next => null()
end type list_entry

Implement the Branch-Free Insert Subroutine #

The core of Linus's trick is using a pointer that tracks the address of the next pointer (instead of the node itself) as we traverse the list. In Fortran, we can replicate this by using a pointer that associates with the next pointer of each node (starting with the head pointer itself):

subroutine list_insert(head, val)
    type(list_entry), pointer, intent(inout) :: head
    integer, intent(in) :: val
    type(list_entry), pointer :: current_ptr

    ! Start by pointing to the head pointer (equivalent to &head in C)
    current_ptr => head

    ! Traverse until we hit a null pointer (the end of the list)
    do while (associated(current_ptr))
        current_ptr => current_ptr%next
    end do

    ! Allocate the new node directly to this pointer position
    allocate(current_ptr)
    current_ptr%val = val
    ! The next pointer is already null by default, so no extra setup needed
end subroutine list_insert

How This Works #

• current_ptr starts out associated with the head pointer. If the list is empty, head is null, so we skip the loop and allocate directly to head.
• For non-empty lists, we keep moving current_ptr to point to each node's next pointer until we reach the end (where current_ptr is null). Allocating at this spot adds the new node to the end of the list automatically.
• No if (head == null) checks needed—this single logic handles all cases, just like Linus's C implementation.

Test It Out #

Here's a quick main program to demonstrate inserting values and traversing the list:

program test_linked_list
    type(list_entry), pointer :: my_list => null()
    type(list_entry), pointer :: temp

    ! Insert some sample values
    call list_insert(my_list, 10)
    call list_insert(my_list, 20)
    call list_insert(my_list, 30)

    ! Traverse and print the list
    temp => my_list
    do while (associated(temp))
        print *, temp%val
        temp => temp%next
    end do

    ! Clean up memory (always a good practice!)
    do while (associated(my_list))
        temp => my_list%next
        deallocate(my_list)
        my_list => temp
    end do
end program test_linked_list

Key Takeaway #

Fortran's pointer association model works differently than C's raw pointer addresses, but the core idea of Linus's "good taste" code remains the same: by focusing on manipulating the pointers that link nodes (instead of the nodes themselves), we eliminate redundant conditional checks and keep our code clean and maintainable.

内容的提问来源于stack exchange，提问作者ptb