双方向リストの実装例 (C言語)
次は双方向リストの実装例について記載していきます。
ノード構造定義
struct LinkedNode
{
int value; // 値(任意のデータ)
LinkedNode* pNext; // 次のノードへのポインタ(リンク)
LinkedNode* pPrev; // 前のノードへのポインタ(リンク)
};
双方向リストのノードも任意のデータとリンク情報を持ちます。
ノードの基本処理
LinkedNode* pHead = NULL; // 先頭ノード
LinkedNode* pTail = NULL; // 末尾ノード<
// ノードの追加
void AddNode(LinkedNode* pNode)
{
// ノードがない場合は先頭=末尾のノードとなる
if (pHead == NULL)
{
pHead = pTail = pNode;
return;
}
// 現在の末尾の次のノードとして登録する
pTail->pNext = pNode;
// 末尾を追加したノードの手前のノードとして登録する
pNode->pPrev = pTail;
// 追加されたノードを末尾にする
pTail = pNode;
}
// ノードの削除
void RemoveNode(LinkedNode* pNode)
{
// 手前にノードがある場合は次のノードとリンクさせる
if (pNode->pPrev) pNode->pPrev->pNext = pNode->pNext;
// 次のノードがある場合は手前のノードとリンクさせる
if (pNode->pNext) pNode->pNext->pPrev = pNode->pPrev;
// 先頭ノードが削除される場合は先頭ノードを次のノードに差し替える
if (pNode == pHead) pHead = pNode->pNext;
// 末尾のノードが削除される場合は手前のノードに差し替える
if (pNode == pTail) pTail = pNode->pPrev;
// メモリを解放する
free(pNode);
}
// ノードの作成
LinkedNode* CreateNode(int value)
{
// ノードのメモリを確保する
LinkedNode* pNode = (LinkedNode*)malloc(sizeof(LinkedNode));
// ノードの値を設定して前後のノードを初期化
pNode->value = value;
pNode->pNext = NULL;
pNode->pPrev = NULL;
return pNode;
}
// ノードの削除
void DeleteAll(void)
{
// ノードが無くなるまで削除し続ける
while(pHead)
{
RemoveNode(pHead);
}
}
双方向リストは前後のリンクを持っているの削除処理の際にノードの検索が不要になります。
今回の例では大きな違いは削除処理だけですが、実際に使う用途に応じてどちらのリストが都合がいいかは変わってきます。
実際に使う際には配列とリストのどちらが都合がいいのか？
片方向と双方向のどちらのリストがいいのか？
それぞれの利点に合わせて設計をしましょう。