はじめての C

lang

「リンクリスト 4」

次に 入る前に、大急ぎで、線形リストと 双方向リストについて ノートしてみましょう。

線形リストに 項目を 挿入するとき、2つの リンク つまり 双方の next ポインタを 書き換える 必要が あります。

n->next = item->next; /* n の next ポインタに セット */
item->next = n; /* item の next ポインタに セット */

しかし 双方向リストの 場合は、リンクの数を 2倍 用意する 必要が でてきます。

双方向リストでは、仕事が 2倍に なることを 覚えておくと、助かることに なります。

n->prev = item; /* n の prev ポインタ */
n->next = item->next; /* n の next ポインタ */
n->next->prev = n; /* n の next->prev ポインタ */
n->prev->next = n; /* n の prev->next ポインタ */

準備された これらの 4つの リンクだけで、項目は 正しく 挿入されるのです。

ただし、リンクの中に 番兵が あると、問題が 起こってきます。

そこで、双方向リストの どこであっても、正しく ノードを 挿入する コードを 書いてみましょう。

n->prev = item;
n->next = item->next;
if (n->prev != NULL)
n->prev->next = n;
if (n->next != NULL)
n->next->prev = n;

すべての リンクリストで、項目を 挿入 あるいは 削除することが できます。

実際、この tutorial のために 書いた ごく小さな リストライブラリでは、関数が 4つ 含まれているだけです。 つまり、挿入と 削除、それに 先頭項目の 検出と 末尾項目の 検出です。

そのヘッダは こうなっています ▽

#ifndef PRELIST_H
#define PRELIST_H

typedef enum {BEFORE, AFTER} Direction;
typedef struct element *Element;
typedef struct element *List;

struct element {
Element prev;
Element next;
int data;
};

Element first(Element iter);
Element last(Element iter);
List add(List list, Element iter, Element item, Direction dir);
Lisr rem(List list, Element iter);

#endif

(注 1) #ifndef は、defined 演算子を 使った 条件文の マクロを 参照。
http://d.hatena.ne.jp/sekiyo/20050221
また #ifndef で 定義した NAME は ヘッダファイル自体を 指すので、上の例だと、PRELIST_H は ヘッダファイル名が prelist.h であることを (おそらく) 表している。

(注 2) enum は 列挙子のこと。 名前付きの 定数の、集合の 範囲の 値を もつ 型 (KandR 2nd p266)。
typedef と ともに 用いる 場合が ある。
typedef enum {定数0, 定数1, ... } 列挙子名;

シンプルでしょ ?

先頭と 末尾の ポインタを 保守 - maintain - している コードでは、first と last の 関数は、まず 絶対 使うことは ありません !

ここに それを 付け加えた 理由は ただ 1つ、たいていの 場合 - 私もですが - 先頭と 末尾の 保守を ナマケてしまうからです。

しかし、この 先頭と 末尾を 普段から 使うことで、大きな リストに おいても、大きな パフォーマンスを ヒットさせる - be a big performance hit - ことが できるという、課題を 知るように なります。

でも、この tutorial では、リストは 小さいでしょうから、パフォーマンスの 問題は 受け入れられる 範囲に なっています。

On to the code !