単連結リストの整列 #30 不足っぽい点

C

整列のために必要な単連結リストの機能を関数で表現しようといている。
必要っぽいものを関数プロトタイプ宣言の形で前回書いてみた。

が、リストの情報を得る関数としてheadとnextだけでは足りなさそうな感じだ。
nextは与えられた要素から次の要素の参照を返す関数だが、
最後の要素が与えられた時にnextは何を返すのが適切だろうか？
要素の参照がポインタで実現されているようなリストの実装であれば、
正当などのアドレスも指していないことを示す値であるNULLを返すことで、
nextに与えた参照先の要素が最後の要素であるという仕様にしてもいいだろう。
しかし、具体的に参照が何でどのように実現するかは各実装に委ねられるべきであろう。
ということで、headとnext以外に、与えられた要素が最後の要素であるか否かを返す関数、
あるいは、最後の要素の参照自身を返す関数のようなものが必要になると考えられる。

また、リストを操作する関数としてswapを与えるようになっているが、
交換すべき二つの要素自身の参照だけしかswapが知ることができない場合、
各要素が次の要素の参照しか知りえない純粋な単連結リストでは、
swapを実装する場合かなり効率が悪いものしか作れなさそうな気もする。
今までの方法を踏襲すれば、
与えられた二つの要素それぞれの次要素同士を交換する仕様にすればいいのかもしれない。
しかし、そういう仕様は与えられたもの同士の交換という仕様に比べて直感的でない感じがする。
それにこれは実装がそういう純粋な単連結性を持っている場合の性能の悪化に関することで、
インタフェイスとしては単連結リストでも実装が例えば双方向リストであるなら問題はなくなるだろう。
つまり、実装次第の問題点を複雑な仕様にして対処するよりも、
とりあえず単純で直感的なインタフェイスのままにしておく方がいいとも思う。
どうすべきか悩ましいところだが。