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

# はじめに

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

当初は`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`のポインタを取得できるようにしています。

```fortran
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`は下記の通りです。

```fortran
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
```

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

# その他のfortranリンクリストライブラリ
fortranのスタンダードライブラリ[（stdlib）](https://stdlib.fortran-lang.org/)にはまだリンクリストがありませんが、プルリクには候補があるのでいつか導入されるかもしれません。

パッケージマネージャで導入できるリンクリストとしては、ほかに[flist](https://github.com/jacobwilliams/flist)があります。

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