如何在Fortran中仅用Allocatable而非指针实现链表？

（更新：经过多方建议，文末新增了几种解决方案。看起来完全避开指针是可行的，但仍不够理想……）

之前有结论认为实现链表必须使用指针，但这个结论仅适用于双向链表。对于单向链表（或树），节点定义里其实不需要指针——可以用可分配的节点类型来定义next字段。但新的问题来了：链表的访问例程似乎还是得在局部用指针。

那真正的问题是：能不能完全避开指针？如果Fortran做不到，Rust这类语言可以吗？

示例代码 #

program List     ! 可在在线编译器编译运行
    implicit none
    type node
      integer                  :: data 
      type(node), allocatable  :: next
    end type
    
    type(node), allocatable  :: test
    integer                  :: inew

    do
      print *, "List =";   call prt(test)
      read *, inew;     call insert(test, inew)
    end do
    
  contains

    subroutine prt(list)
      type(node), allocatable, target  :: list
      type(node), pointer              :: p
      
      if(.not.allocated(list)) return
      p => list
      do  ! 没法用if(allocated(p))做前置检查？！
        print *, p%data
        if(.not.allocated(p%next)) exit
        p => p%next
      end do
    end

    subroutine insert(list, n)            ! 按顺序插入
      type(node), allocatable, target  :: list
      integer, intent(in)              :: n
      type(node), pointer              :: p
      type(node), allocatable          :: new

      allocate( new ); new% data=n        ! 创建新节点

      if(.not. allocated(list)) then      ! 链表尚未创建
        call move_alloc(new, list)
      elseif(n <= list% data) then        ! 插入到表头
        call move_alloc(list, new% next)
        call move_alloc(new, list)
      else
        p => list            ! 没法用allocated(p)判断？！
        do
          if(.not.allocated(p%next)) then
            call move_alloc(new, p%next)
            return
          elseif( n <= p%next%data ) then
            call move_alloc(p%next, new%next)
            call move_alloc(new, p%next)
            return
          endif
          p => p%next
        end do
      endif
    end 
  end program

迫使访问例程用指针的核心原因不是插入操作，而是链表遍历。不用指针的话，依然可以实现表头或表头后一位的插入：

subroutine insert0(list, n)          ! 插入到表头
    integer, intent(in)      :: n
    type(node), allocatable  :: list, new

    allocate( new );  new%data=n       ! 创建新节点

    call move_alloc(list, new%next)
    call move_alloc(new, list)
end


subroutine insert1(list, n)          ! 插入到表头后一位
    integer, intent(in)      :: n
    type(node), allocatable  :: list, new
    
    if(.not. allocated(list)) stop "空链表无法执行此操作"
    allocate( new );  new%data=n       ! 创建新节点
 
    call move_alloc(list%next, new%next)
    call move_alloc(new, list%next)
end

使用指针还有个麻烦：把指针指向节点p => list后，不能用allocated(p)判断目标是否已分配，但却可以用allocated(p%next)。这逼得遍历必须用前瞻式逻辑，要额外处理边界情况。这到底是语言Bug还是设计如此？（为什么不能先解引用p再处理变量？）

（更新：根据相关建议，新增几种解决方案）

• 针对访问例程用指针时无法用allocated(p)判断的问题，可以改用associated(p)。如果指针p指向未分配的可分配对象，那么指针状态是“未关联”的——这是语言标准保证的吗？

• 完全避开指针（代码中不出现pointer或target关键字）的方法是用递归访问例程。但递归会带来内存开销，遍历链表时栈里会隐式生成返回地址的临时列表……不过这能写出目前最短的链表示例：

program List
  implicit none
  type node
    integer                  :: data 
    type(node), allocatable  :: next
  end type

  type(node), allocatable    :: test
  integer                    :: inew
  do
    print *, "List =";   call prt(test)
    read *, inew;       call insert(test, inew)
  end do
  
contains
  recursive subroutine prt(list)
    type(node), allocatable   :: list
    if(.not.allocated(list)) return
    print *, list%data;  call prt(list%next)
  end

  recursive subroutine insert(list, n)  ! 按顺序插入
    integer, intent(in)       :: n
    type(node), allocatable   :: list, new
    if(.not. allocated(list)) then      ! 链表尚未创建
      allocate( list ); list% data=n    
    elseif(n <= list% data) then        ! 在此位置插入新节点
      allocate( new ); new% data=n    
      call move_alloc(list, new% next)
      call move_alloc(new, list)
    else                       
      call insert(list%next, n)         ! 递归处理下一个节点
    endif
  end 
end program

• 当然也可以用“自制指针”的方式避开内置指针：用整数索引指向预定义大数组里的元素。但这会增加额外工作量，而且依然存在内存泄漏和悬垂引用的问题……

内容的提问来源于Stack Exchange，提问作者Jos Bergervoet