fortranリンクリスト（挿入する型が一種類のみの場合）

はじめに

プログラム実行中に要素数が大きく増減するデータ構造があり、データの追加と削除で負荷を小さくしたい事があります。
つまり、fortranにリンクリストが欲しい！ということで機能追加しました。
ここからcloneできます

当初はPythonと同じように、リストの各要素が異なる型であっても良いようなリスト
を目指して無限多層性class(*)を使ってライブラリを作りましたが、利用しているうちに、挿入する型は一つだけの方が多い という状態になりました。そこで、もっと簡単にデータの取り回しをしたいと考え、m_linkedlist_sametypeモジュールを追加しました。

使用例(gfortran11.4.0, ubuntu22.04)

まずは利用例です。
挿入するデータ型node_int_tは、m_linkedlist_sametypeで定義されたnode_tをm_mylistモジュールでextendしています。mylistは、m_linkedlist_sametypeで定義されたlist_tをextendすることで、
call list%get_ptr(3,node_int_ptr)のように添え字で直接自分の定義した型node_int_tのポインタを取得できるようにしています。

program main
    !use m_linkedlist_sametype !今回追加したライブラリ
    use m_mylist              !リストに追加するデータ構造を定義したモジュール
    implicit none
    integer :: i
    type(mylist) :: list          !ダブルリンクリスト
    type(node_int_t) :: node_int  !挿入するデータ型
    type(node_int_t),pointer :: node_int_ptr  !リストからデータ参照用のポインタを取り出す場合に利用

    print *,"!=== LINKEDLIST TEST =================="
    ! サンプルデータの用意
    do i=1,10
      node_int%i8=i*1
      node_int%i16=i*10
      node_int%i32=i*100
      node_int%i64=i*1000
      call list%append(node_int)
    end do

    ! データの削除、挿入テスト
    call list%remove(3)          ! delete 3rd node 
    call list%insert(3,node_int) ! insert node to 3rd position
    call list%insert(1,node_int) ! insert node to head
    print *,"Entries number in the list:",list%entries()
    
    ! リスト要素を指すポインタを取得
    do i=1,list%entries()
      call list%get_ptr(i,node_int_ptr)
      print*,i,":",&
          node_int_ptr%i8,node_int_ptr%i16,&
          node_int_ptr%i32,node_int_ptr%i64
    end do
    
    !データを全部削除
    call list%clear()
    print*,"After clearing list, Entries number in the list is:",list%entries()
end program main

実行結果は下記の通り。

 !=== LINKEDLIST TEST ==================
 Entries number in the list:          11
           1 :   10    100        1000                10000
           2 :    1     10         100                 1000
           3 :    2     20         200                 2000
           4 :   10    100        1000                10000
           5 :    4     40         400                 4000
           6 :    5     50         500                 5000
           7 :    6     60         600                 6000
           8 :    7     70         700                 7000
           9 :    8     80         800                 8000
          10 :    9     90         900                 9000
          11 :   10    100        1000                10000
 After clearing list, Entries number in the list is:           0

拡張型の定義

m_linkedlist_sametypeで定義されたnode_tとlist_tはabstract typeなので、自前で拡張する必要があります。上記のテストコードでuseしているm_mylistは下記の通りです。

module m_mylist
    use m_linkedlist_sametype
    implicit none

    type,extends(list_t) :: mylist
        contains
        procedure,public :: get_ptr => list_get_mynode
    end type

    type,extends(node_t) :: node_int_t
        !ここに、リスト要素のひとかたまり(node)として加えたいデータを好きなだけ追記する。
        integer(int8) :: i8 =1
        integer(int16) :: i16 =1
        integer(int32) :: i32 =1
        integer(int64) :: i64 =1
    end type
  
    contains

    subroutine list_get_mynode(self,loc,ptr)
        !! type(node_int_t)のポインタを返値とするための関数
        !! ここで一度定義してしまえば、リストから取り出すときにいちいち
        !! `select type`しなくてすむ。
        class(mylist),intent(inout) :: self
        integer,intent(in) :: loc
        class(node_t),pointer :: node_t_ptr
        type(node_int_t),pointer :: ptr
        ptr => null()
        call self%get_nodeclass(loc,node_t_ptr)
        select type(node_t_ptr)
        class is(node_int_t)
          ptr => node_t_ptr
        end select
        if(.not.associated(ptr))then
          error stop
        endif
    end subroutine
end module

おわりに

データの追加が簡単かつ早い（はず）ですが、添え字でデータ参照をする際には時間がかかります。追加処理が終了し要素数が確定したら、自分で配列に変換する¹とランダムアクセスが早くなります。
用法、用量に気を付けていただければと思います。

その他のfortranリンクリストライブラリ

fortranのスタンダードライブラリ（stdlib）にはまだリンクリストがありませんが、プルリクには候補があるのでいつか導入されるかもしれません。

パッケージマネージャで導入できるリンクリストとしては、ほかにflistがあります。

1. list要素数分allocate()して、do文でget_ptrを使って要素ごとにコピーを作るなど。 ↩