単連結リストの整列 #76 見た目は単連結、中身は双方向連結
タイトルから外れる気もするが、intlistの実装を双方向連結リストに変更してみる。
インタフェイスは変更しないので利用する側からは今までと全く変わらない扱いができるはずだ。
双方向連結リストのデータ構造にはバリエーションがある。
とりあえず、リストの先頭と末尾にダミー要素を置き、実要素をその間に追加していく形にした。
図の上がリストの初期状態、下のリストは3個の要素を持っている。
したがって、インタフェイスintlist.hで名前が宣言されている二つの構造体、
リストの管理情報をまとめたtag_intlist構造体と、各要素の情報を収めたtag_intelem構造体は、
struct tag_intlist { intelem_t head; intelem_t tail; unsigned long compare_counts; unsigned long swap_counts; }; struct tag_intelem { int val; intelem_t next; intelem_t prev; };
のような感じになるだろうか。