C++ の循環二重リンクリスト
胡金庫
2023年10月12日
この記事では、C++ で循環二重リンクリストを実装する方法を示します。
C++ の最初からの循環二重リンクリストデータ構造
二重リンクリストは、各ノードが次のノードと前のノードの両方へのポインタを格納するデータ構造です。これにより、std::deque のようなコンテナを実装するのが最適な選択になります。最後のノードの next メンバーがリストの先頭を指し、最初のノードも前のノードと同じように最後のノードを指すように、二重にリンクされたリストを循環させることをお勧めします。
最初に、リストの作成に使用される ListNode という名前の struct を宣言する必要があります。次に、タイプ ListNode の 2つのデータメンバーと 3つのメンバー関数を持つ CircularList クラスを定義します。
string 値を受け入れて最初のノードを初期化するコンストラクターを 1つだけ含めることにしましたが、この部分はプログラマーが適切と考えるように変更できることに注意してください。2つのデータメンバー（head と end）は、最初と最後のノードを格納します。リストの両側に要素を追加するための個別の関数もあります。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
struct ListNode *prev = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->prev = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
ListNode *insertNodeHead(string data);
void printNodes();
~CircularList();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = head;
new_node->prev = end;
new_node->data = std::move(data);
head->prev = new_node;
end->next = new_node;
end = end->next;
return end;
}
ListNode *CircularList::insertNodeHead(string data) {
auto new_node = new ListNode;
new_node->next = head;
new_node->prev = end;
new_node->data = std::move(data);
head->prev = new_node;
end->next = new_node;
head = new_node;
return head;
}
CircularList::~CircularList() {
while (head != end) {
auto tmp = head;
head = head->next;
delete tmp;
}
delete head;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
CircularList clist("Xenial");
clist.insertNodeHead("Saucy");
clist.insertNodeEnd("Quantal");
clist.printNodes();
cout << " ----------------------------------- " << endl;
clist.insertNodeHead("Bionic");
clist.printNodes();
return EXIT_SUCCESS;
}
出力：
node 0 - data: Saucy
node 1 - data: Xenial
node 2 - data: Quantal
-----------------------------------
node 0 - data: Bionic
node 1 - data: Saucy
node 2 - data: Xenial
node 3 - data: Quantal
要素挿入の一般的なアルゴリズムでは、新しい ListNode オブジェクトを割り当て、対応するノードポインターをそのメンバーに割り当て、必要に応じて head/end メンバーを変更します。また、コードの正確さを検査する必要がある場合があるため、リストの内容を表示するための printNodes 関数も含まれています。リストオブジェクトがスコープ外になった後は、すべてのメモリの割り当てを解除することを忘れてはならないことに注意してください。後者の関数はデストラクタとして実装されます。
著者： 胡金庫
