アルゴリズム入門講座: 双方向連結リストc++で動的に実装する

双方向連結リストをc++で実装してみたいと思います。
まず、双方向連結リストとは何かに関してまとめます。

双方向連結リストとは

あるデータを持ったノードがあり、そのノードの前方と後方に別のノードが連結しているリストのことです。
数値をデータとして持つノードの双方向連結リストを図で表すとこんな感じです。

□→ ←□2□→ ←□4□→ ←□

□は、繋いでいるデータのメモリアドレスです。

一番最初のデータと一番最後のデータは、空のデータを表すnilを入れます。
参照しても空ということです。

双方向連結リストをc++で実装する

では、c++で双方向リストを実装してみたいと思います。

まず、ノードとなるデータを構造体で定義します。

struct Node{
    int key;
    Node *next,*prev;
};

データとして、int型を定義し、
自身を二つ定義します。
これに、連結リストとなる次のノードと前のノードを代入して、連結リストが作られていきます。

双方向リストの位置を管理する番兵を導入する

定義したノードを生成して、新しく連結リストを作っていくのに、現在の連結リストの位置を管理する必要があります。そのために、グローバル変数として、番兵を用意します。

// 番兵をグローバル変数として定義する
Node* nil;

// 番兵を生成する
void init(){
    nil = (Node*)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

新しくメモリを割り当てる関数mallocを使って、連結リストのノードを作成しています。 mallocで作成したメモリ領域は必ず、free関数で解放する必要があるので、ノードを削除する関数で、
free関数を必ず呼びましょう。

nil->next = nil
nil->prev = nil
によって、番兵の前と次の要素を自身に設定して、巡回するようにしています。

双方向連結リストに新しいノードを挿入する

位置を管理する番兵を定義したところで、新しいノードのを追加する関数を定義します。
insert関数は、連結リストの先頭にキーを持つノードを挿入する関数です。

void insert(int key){
    // 新しくnode用のメモリを作成
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    // 番兵の次に要素を追加
    node->next = nil->next;
    nil->next->prev = node;
    nil->next = node;
    node->prev = nil;
}

ここがわかりにくいと思うので、挿入していく様子を図解してみます。

ノードが挿入される要素を図解する

1.まず新しくkey3を持つノードを作成します。

□空の先頭□ □3□

2.続いて番兵の設定をして、連結リストが管理できるようにします。

番兵はinit関数により、自身を巡回させているので、下図のようになります。

       prev       next
番兵 ← □番兵□ → 番兵

続いて、挿入していく様子を図にします。

まず、新しく作成したnodeのnextに番兵を指定します。
nil->nextはnilを指していますね。

node->next = nil->next;

□3□ → □番兵□

続いて、nil->next->prev = node
ですが、最初に要素を挿入するときには、nil->next->prevはnilを指しています。
なので、nilのprevにnodeを挿入していることになります。


nil->next->prev = node

□3□ → □番兵□
　   ←

続いて、番兵のnextに作成したノードを設定します。図では、番兵が2つになっていますが、実際はもちろん一つで、表現するためにそうしています。

nil->next = node

□番兵□ → □3□ → □番兵□
　　　　　　    ←

最後に、ノードのprevに番兵を設定します。

node->prev = nil;

□番兵□ → □3□ → □番兵□
　　　   ←　　 ←

これで、一回目の挿入が終わりました。

2回目の双方向連結リストへの挿入

では、次にkey5を持つノードを新しく挿入するケースを確認したいと思います。

node->next = nil->next
現在nilのnextには、先ほど作成した3を持つノードが指定されているので、node->nextは
3のノードを指すことになります。

node->next = nil->next


□5□ → □3□ → □番兵□
　　　　 　←

nil->next->prev = node
nil->nextには、3が入っています。ということは、nil->next->prevは3のprevを指しますね。
3のprevに5のノードを代入します。

nil->next->prev = node;
□5□ → □3□ → □番兵□
　　←　 　←

nil->next = node
nil->nextに5のノードを設定します。

nil->next = node
□番兵□ → □5□ → □3□ → □番兵□
　　　              ←　 　←

node->prev = nil 現在のノードのprevに番兵を指すようにして、巡回させるようにします。

node->prev = nil;
□番兵□ → □5□ → □3□ → □番兵□
　　　   ←       ←　 　←

こんな感じで先頭に挿入することができます。
要素の先頭と最後方には番兵が入ることになり、双方向連結リストの挿入を容易にしてくれます。

双方向連結リストをキーで探索する

リストをキーで検索してみます。

insert関数で図解したように、番兵のnextに先頭の要素が、
最後方のnextに番兵が入っているので、
キーを探すには、番兵のnextから探索し、番兵が見つかれば、
キーをもつ要素が見つからなかったという判断ができそうです。

双方向連結リストをキーで探索するプログラム

それでは、双方向連結リストを探索するプログラムを見ていきます。

Node* searchList(int key){
    // 番兵の先頭から探していく
    Node* cur = nil->next;
    // 番兵でなく、キーが同じでなければ、次の要素を探索する
    while(cur != nil && cur->key != key){
        cur = cur->next;
    }
    // 見つからければ、番兵が返ることになる。
    return cur;
}

双方向連結リストのノードを削除する

続いて、ノードを削除する方法を見ていきましょう。
引数として与えられたノードを削除するプログラムを書きます。

双方向連結リストのノードを削除するプログラム

void deleteNode(Node* n){
    // 番兵のケースは何もしない
    if(n == nil) return;
    n->prev->next = n->next;
    n->next->prev = n->prev;
    free(n);
}

プログラムの様子がイメージしにくい部分があると思うので、
先ほどinsertした図を使用し、プログラムの遷移を表現してみます。

□番兵□ → □5□ → □3□ → □番兵□
　　　   ←       ←　 　←

この連結リストから5のノードを削除するケースを考えてみます。

n->prev->next = n->next
自身のprevの要素のnextが指す位置を自身の次の要素に入れ替えます。
つまり、番兵のnextが3を指すようになります。

n->prev->next = n->next

□番兵□    □5□ → □3□ → □番兵□
　　　   ←       ←　 　←
　　　　　 □番兵□ →

n->next->prev = n->prev
自身の次の要素のprevが指す位置を自身の前の要素に入れ替えます。つまり、3ノードのprevが番兵を指すようになります。

n->prev->next = n->next

□番兵□ → □3□ → □番兵□ □5□ 
　　　   ←       ←

free(n); 最後にどこにも連結しなくなった、ノード5をfree関数によって、削除します。

これで、5を削除しても連結リストが保持されていることが確認できました。

双方向連結リストの先頭のノードを削除する

番兵のnextが先頭のノードを指しているので、deleteNode関数に
nil->nextを渡せばokです。

void deleteFirst(){
    deleteNode(nil->next);
}

双方向連結リストの最後方のノードを削除する

番兵のprevは後方のノードを指しているので、deleteNode関数に
nil->prevを渡せばokです。

void deleteLast(){
    deleteNode(nil->prev);
}

双方向連結リストの特定のキーをもつノードを削除する

先ほど特定キーをもつノードを探し、返す関数を書いたので、その関数を使います。

void deleteKey(int key){
    deleteNode(searchList(key));
}

これで、双方向リストのプログラムが完成しました。

双方向連結リストの計算量を考える

双方向連結リストの計算量を考えてみます。

双方向連結リストの挿入する計算量

プログラムで示した通り、番兵のnextのpointerを繋ぎ変えるだけなので、
O(1)になります。

双方向連結リストから特定の要素を探索する計算量

双方向位連結リストは直列で結ばれているので、
先頭から末端のNまで、探索する必要があります。
なので、O(N)になります。

双方向連結リストから特定の要素を削除する計算量

先頭・最高峰の要素を削除するには、番兵があるので、O(1)の計算量で、
それ以外は、O(N)になります。

アルゴリズム入門講座

2018年12月3日月曜日

双方向連結リストc++で動的に実装する