C++で双方向リンクリストを実装する方法【サンプルコードと解説付き】

双方向リンクリスト（Doubly Linked List）とは

双方向リンクリストは、自己参照構造体を用いて作成されたノードから構成されるデータ構造の一種です。各ノードは「データ」「次のノードへのポインタ」「前のノードへのポインタ」という3つの要素を持っています。

リンクリスト全体へアクセスするには、先頭ノードへの参照が1つあれば十分です。この先頭ノードは「ヘッド（head）」と呼ばれます。リストの末尾ノードは次のノードを持たないため、nextポインタにはNULLが格納されます。また、各ノードが前後両方のノードを指しているため、双方向リンクリストは前方向にも後方向にも走査（トラバース）できるのが大きな特徴です。

以下に、双方向リンクリストを実装するC++プログラムを示します。

実装例

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
    struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
    newnode->data = newdata;
    newnode->prev = NULL;
    newnode->next = head;
    if(head != NULL)
        head->prev = newnode;
    head = newnode;
}
void display() {
    struct Node* ptr;
    ptr = head;
    while(ptr != NULL) {
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
}
int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout << "双方向リンクリスト: ";
    display();
    return 0;
}

出力結果

双方向リンクリスト: 9 2 7 1 3

コードの解説

1. ノードを表す構造体Node

上記のプログラムでは、構造体Nodeが双方向リンクリストの1つのノードを表しています。この構造体は、int型のデータと、前後のノードを指す2つのポインタprev・nextで構成されます。

struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
};

2. insert()関数：先頭への挿入

insert()関数は、双方向リンクリストの先頭に新しいデータを挿入します。まずmalloc()で新しいノード（newnode）のメモリを確保し、データフィールドに値を格納します。先頭に挿入されるため、newnodeのprevポインタはNULLを指し、nextポインタは現在のヘッドを指します。ヘッドがNULLでない（リストが空でない）場合は、既存のヘッドのprevポインタをnewnodeに向けてリンクを双方向に接続します。最後にヘッドをnewnodeへ更新することで、リストは新しいノードから始まることになります。

void insert(int newdata) {
    struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
    newnode->data = newdata;
    newnode->prev = NULL;
    newnode->next = head;
    if(head != NULL)
        head->prev = newnode;
    head = newnode;
}

3. display()関数：リストの表示

display()関数は、双方向リンクリスト全体を順番に表示します。まずポインタptrをヘッドに設定し、ptrがNULLになるまで（＝末尾に到達するまで）nextポインタをたどりながら、各ノードのデータを出力していきます。

void display() {
    struct Node* ptr;
    ptr = head;
    while(ptr != NULL) {
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
}

4. main()関数：プログラムの実行

main()関数では、まずinsert()を5回呼び出して、値3・1・7・2・9をこの順にリストへ挿入します。insert()は常に先頭に挿入するため、最後に挿入した9が先頭に配置されます。その後、display()を呼び出してリスト全体を表示します。

int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout << "双方向リンクリスト: ";
    display();
    return 0;
}

補足：よりC++らしい実装にするには

本サンプルではC言語由来のmalloc()を使用していますが、C++ではnew演算子でメモリを確保するのが一般的です。また、プログラム終了時に各ノードのメモリをdeleteで解放すれば、メモリリークを防ぐことができます。さらに、末尾への挿入、特定の値の削除、逆方向の走査などを実装すれば、双方向リンクリストへの理解がより深まります。計算量としては、先頭への挿入はO(1)、リスト全体の走査はO(n)で行えます。