C++で実装する双方向循環リンクリスト：アルゴリズムとサンプルコード徹底解説

循環リンクリストとは

循環リンクリスト（Circular Linked List）は、リンクリストの変形版であり、最初の要素が最後の要素を指し、最後の要素が最初の要素を指す構造を持つデータ構造です。片方向リンクリスト（Singly Linked List）でも双方向リンクリスト（Doubly Linked List）でも、循環リンクリストとして実装することができます。

双方向リンクリストの場合、末尾ノードのnextポインタが先頭ノードを指し、先頭ノードのprevポインタが末尾ノードを指すことで、両方向に循環する構造になります。

上図のように、押さえておくべき重要なポイントは以下の2点です。

• 双方向リンクリストでは、末尾リンクのnextがリストの先頭リンクを指します。
• 先頭リンクのprevが、双方向リンクリストの末尾を指します。

アルゴリズム

双方向循環リンクリストに対する主な操作（表示・挿入・削除）の擬似コードは以下の通りです。

displayForward()（先頭から末尾へ表示）：
Begin
    ptr := head
    while ptr != null, do
        print ptr->key, ptr->data
        ptr := ptr->next
    done
End
displayBackward()（末尾から先頭へ表示）：
Begin
    ptr := last
    while ptr != null, do
        print ptr->key, ptr->data
        ptr := ptr->prev
    done
End
insertFirst(key, data)（先頭に挿入）：
Begin
    keyとdataを持つ新しいノードを作成
    if リストが空ならば
        last := node
    else
        head->prev := node
    end if
    node->next := head
    head := node
End
insertLast(key, data)（末尾に挿入）：
Begin
    keyとdataを持つ新しいノードを作成
    if リストが空ならば
        last := node
    else
        last->next := node
        node->prev := last
    end if
    last := node
End
insertAfter(key, newKey, data)（指定キーの直後に挿入）：
Begin
    current := head
    if headがnullならば falseを返す
    while currentのkeyがkeyと一致しない間、do
        if current->nextがnullならば
            falseを返す
        else
            current := currentのnext
        end if
    done
    newKeyとdataを持つ新しいノードを作成
    if current = lastならば
        nodeのnext := null
        last := node
    else
        nodeのnext := currentのnext
        currentのnextのprev := node
    end if
    nodeのprev := current
    currentのnext := node
    trueを返す
End
deleteFirst()（先頭を削除）：
Begin
    tempNode := head
    if headのnextがnullならば
        last := null
    else
        headのnextのprev := null
    end if
    head := headのnext
    tempNodeを返す
End
deleteLast()（末尾を削除）：
Begin
    tempNode := last
    if headのnextがnullならば
        head := null
    else
        lastのprevのnext := null
    end if
    last := lastのprev
    tempNodeを返す
End
deleteNode(key)（指定キーのノードを削除）：
Begin
    curr := head、prev := null
    if headがnullならば
        nullを返す
    end if
    while currのkeyがkeyと異なる間、do
        if currのnextがnullならば
            nullを返す
        else
            prev := curr
            curr := currのnext
        end if
    done
    if currがheadならば head := headのnext、そうでなければ currのprevのnext = currのnext
    if currがlastならば last := currのprev、そうでなければ currのnextのprev = currのprev
    currを返す
End

C++での実装例

それでは、上記のアルゴリズムを実際のC++コードで確認してみましょう。以下のサンプルでは、ノードの定義から各操作の実装、そしてmain関数での動作検証までを一通り示しています。

#include <iostream>
#include <cstdio>
using namespace std;
class node {
   public:
      int data;
      int key;
      node *next;
      node *prev;
};
//このリンクは常に先頭のリンクを指す
node *head = NULL;
//このリンクは常に末尾のリンクを指す
node *last = NULL;
node *current = NULL;
//リストが空かどうかを判定
bool isEmpty() {
   return head == NULL;
}
int length() {
   int length = 0;
   node *current;
   for(current = head; current != NULL; current = current->next){
      length++;
   }
   return length;
}
//リストを先頭から末尾へ表示
void displayForward() {
   //先頭から開始
   node *ptr = head;
   //リストの終わりまで移動
   printf("\n[ ");
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}
//リストを末尾から先頭へ表示
void displayBackward() {
   //末尾から開始
   node *ptr = last;
   //リストの先頭まで移動
   printf("\n[ ");
   while(ptr != NULL) {
      //データを表示
      printf("(%d,%d) ",ptr->key,ptr->data);
      //前の項目へ移動
      ptr = ptr->prev;
   }
}
//先頭位置にリンクを挿入
void insertFirst(int key, int data) {
   //リンクを作成
   node *link = new node();
   link->key = key;
   link->data = data;
   if(isEmpty()) {
      //これを末尾のリンクにする
      last = link;
   }
   else {
      //先頭のprevリンクを更新
      head->prev = link;
   }
   //古い先頭リンクを指す
   link->next = head;
   //新しいリンクを先頭に設定
   head = link;
}
//末尾位置にリンクを挿入
void insertLast(int key, int data) {
   //リンクを作成
   node *link = new node();
   link->key = key;
   link->data = data;
   if(isEmpty()) {
      //これを末尾のリンクにする
      last = link;
   }
   else {
      //新しいリンクを末尾につなぐ
      last->next = link;
      //古い末尾ノードを新しいリンクのprevに設定
      link->prev = last;
   }
   //新しいノードを末尾に設定
   last = link;
}
//先頭の項目を削除
node* deleteFirst() {
   //先頭リンクへの参照を保存
   node *tempLink = head;
   //リンクが1つだけの場合
   if(head->next == NULL){
      last = NULL;
   }
   else {
      head->next->prev = NULL;
   }
   head = head->next;
   //削除したリンクを返す
   return tempLink;
}
//末尾位置のリンクを削除
node* deleteLast() {
   //末尾リンクへの参照を保存
   node *tempLink = last;
   //リンクが1つだけの場合
   if(head->next == NULL) {
      head = NULL;
   }
   else {
      last->prev->next = NULL;
   }
   last = last->prev;
   //削除したリンクを返す
   return tempLink;
}
//指定キーのリンクを削除
node* del(int key) {
   //先頭リンクから開始
   node* current = head;
   node* previous = NULL;
   //リストが空の場合
   if(head == NULL) {
      return NULL;
   }
   //リストを走査
   while(current->key != key) {
      //末尾ノードの場合
      if(current->next == NULL) {
         return NULL;
      }
      else {
         //現在のリンクへの参照を保存
         previous = current;
         //次のリンクへ移動
         current = current->next;
      }
   }
   //一致が見つかったのでリンクを更新
   if(current == head) {
      //先頭を次のリンクに変更
      head = head->next;
   }
   else {
      //現在のリンクをバイパス
      current->prev->next = current->next;
   }
   if(current == last) {
      //末尾を前のリンクに変更
      last = current->prev;
   }
   else {
      current->next->prev = current->prev;
   }
   return current;
}
bool insertAfter(int key, int newKey, int data) {
   //先頭リンクから開始
   node *current = head;
   //リストが空の場合
   if(head == NULL) {
      return false;
   }
   //リストを走査
   while(current->key != key) {
      //末尾ノードの場合
      if(current->next == NULL) {
         return false;
      }
      else {
         //次のリンクへ移動
         current = current->next;
      }
   }
   //リンクを作成
   node *newLink = new node();
   newLink->key = newKey;
   newLink->data = data;
   if(current == last) {
      newLink->next = NULL;
      last = newLink;
   }
   else {
      newLink->next = current->next;
      current->next->prev = newLink;
   }
   newLink->prev = current;
   current->next = newLink;
   return true;
}
int main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("\nList (First to Last): ");
   displayForward();
   printf("\n");
   printf("\nList (Last to first): ");
   displayBackward();
   printf("\nList , after deleting first record: ");
   deleteFirst();
   displayForward();
   printf("\nList , after deleting last record: ");
   deleteLast();
   displayForward();
   printf("\nList , insert after key(4) : ");
   insertAfter(4,7, 13);
   displayForward();
   printf("\nList , after delete key(4) : ");
   del(4);
   displayForward();
}

実行結果

上記のコードをコンパイルして実行すると、以下のような出力が得られます。先頭からの表示・末尾からの表示、そして各操作後のリストの状態が確認できます。

List (First to Last):
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
List (Last to first):
[ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56)
List , after deleting first record:
[ (5,40) (4,1) (3,30) (2,20) (1,10) ]
List , after deleting last record:
[ (5,40) (4,1) (3,30) (2,20) ]
List , insert after key(4) :
[ (5,40) (4,1) (7,13) (3,30) (2,20) ]
List , after delete key(4) :
[ (5,40) (7,13) (3,30) (2,20) ]