コグノスケ

ふとした疑問

初歩的な話ですが、双方向リストを表現するときってどう作ります？

双方向リストの表現方法

私は特に指定がなければ上記の形を取ります。頭一個分の領域が無駄になりますが、リストが空の時でも特別な分岐が要らず、同様に処理できるためです。

struct list_item {
  struct list_item *next, *prev;
}

struct list {
  struct list_item head;
  //other data
}

for (p = list.head.next; p != list.head; p = p->next) {
  //do_something...
}

ところが今日、こんな形の双方向リストを見かけました。形は似ていますが、最後のメンバが異なります。

謎の表現方法

絵にすると対称で綺麗ですがねえ。tailの存在にメリットがなく、無駄に見えます。

この形式にする理由があったんでしょうけど、何だろうか、全く思いつかない。そもそもtailってどう使ってたんだろうか？