C言語教室 第20回 - 双方向リスト

前回、単方向リストを説明しましたが、今回は、戻ることもできる双方向リストです。

typedef struct node {
    int data;
    struct node* pPrevNode;
    struct node* pNextNode;
};

単方向リストでは「次のノード」へのポインタだけでしたが、双方リストでは「前のノード」へのポインタも持っています。これで先頭から順に辿るだけではなく、途中から戻る操作も出来るようになります。最初のノードの「前のノード」へのポインタは、最後のノードの「次のノード」へのポインタと同じように NULL を使います。

単方向リストを管理するときは必ず「先頭のノード」へのポインタを使う必要がありましたが、双方向リストでは、必ずしも「先頭のノード」ではなくても、いずれかのノードへのポインタがあれば、どのノードへのアクセスも出来ます。とはいえ双方向リストを管理するときは、せっかく逆方向にも辿れるので「先頭ノード」と「最後のノード」への２つのポインタを使って管理することが多いです。

typedef struct list {
  struct node* pTop;
  struct node* pTail;
};

これを箱を使った図で示すと、以下のようになります。

双方向リスト

単方向リストと比べれば、使うメモリが少し増えるものの、挿入や削除を行う際に書き換えるポインタにすぐにアクセスできるので、メリットは大きいです。考え方は単方向リストと全く同じなので、具体的な操作に関しては課題にしますので、箱の図を描きながらコードを書いてみてください。

連結リスト

連結リスト - Wikipedia

---

課題
・リストの最後に要素を追加する関数を書きなさい。
・リストの先頭の要素を削除する関数を書きなさい。
・n番目の要素を返す関数を書きなさい。
・要素の中に指定した値が含まれるかを返す関数を書きなさい。

次回は、双方向リストの改良版である循環リストを取り上げます。

ヘッダ画像は、以下のものを使わせて頂きました。
https://commons.wikimedia.org/wiki/File:Doubly-linked-list.svg