単連結リストの整列 #53 要素の一つ前の要素

ilistやilist2、ilist3で定義している関数prevは、
与えられた要素の一つ前の要素を返す関数だが、
単連結リストであるがゆえにその時間計算量は要素数の一次オーダーになる。
この性能は純粋な単連結リストであれば緩和のしようがないと思う。
ここでの問題はそこではなく、要素の交換関数swapにある。
swapでは二つの要素が与えられ、
それぞれの要素の一つ前の要素を得るために個別にprevを呼び出している。
そのためswap一回の呼び出し当たり時間計算量のオーダーは共に要素数の一次関数だが、
一回のprevの呼び出しによる計算量の倍の計算量が平均的に必要となる。
しかし、どちらの要素も一つのリストに格納されているので、
一度に二つの要素を探索していけば、必要な比較回数は変わらないものの、
探索のためのループの準備や更新処理を減少できる可能性がある。