C++ で二重リンクリストを実装する
この記事では、C++ で二重リンクリストを実装する方法に関する複数の方法を示します。
C++ で struct を使用して二重リンクリストを実装する
リンクリストは、プログラミングで遭遇する可能性のある最も一般的なデータ構造の 1つと見なされています。これらの構造は、各ノードに別のノードのアドレスが含まれているという意味でリンクされています。リンクリストには、単一リンクリストと二重リンクリストの 2つのタイプがあります。単一リンクリストには、リスト内の次のノードのみを指すノードが含まれます。したがって、構造のトラバーサルが一方向になります。一方、二重にリンクされたリストは、リスト内の各ノードからの双方向アクセスを提供します。
この場合、struct コマンドを使用して二重リンクリストを実装し、そのすべてのデータメンバーを公開し、要素操作関数を個別に定義します。要素操作ルーチンといくつかの記録保持データメンバーを提供するメンバー関数を備えたオブジェクト指向バージョンを好む場合があることに注意してください。
次のサンプルコードには、基本的な使用シナリオをテストする main 関数のドライバーコードが含まれています。このシナリオでは、string ベクトル要素がリストに挿入され、リストの割り当てが解除されます。new 演算子を使用して各ノードを動的に割り当てます。その結果、freeNodes 関数はリストを繰り返し処理して、各 Node で delete を呼び出します。
ユーザーが比較的高性能のリンクリスト構造を設計したい場合、各 Node を個別に割り当てる方法は非効率的である可能性があります。新しいノードをすばやく追加し、不要な場合は同時に複数の割り当てを解除するために、メモリリソースの一括割り当てを検討する場合があります。この設計では、構造の最初のノードを表す有効な要素を使用してリストの作成を開始します。一部の実装では、ダミー要素を作成する場合があります。これは、リストの先頭を示しますが、要素データは含まれていません。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
struct Node *prev{};
string data;
};
template <typename T>
struct Node *addNewNode(struct Node *node, T &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->prev = node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodeData(struct Node *node) {
cout << "data: " << node->data << endl;
}
int main() {
struct Node *tmp, *root = nullptr;
struct Node *end = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
root = addNewNode(root, data_set.at(0));
tmp = root;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
if (it == data_set.end() - 1) end = tmp;
}
printNodeData(root);
printNodeData(end);
freeNodes(root);
return EXIT_SUCCESS;
}
出力：
data: Rocket Lake
data: Meteor Lake
リンクリストは、スタック、両端キュー、キュー、循環リストなど、より特殊なデータ構造の構成要素として利用できます。後者は本質的に二重リンクリストであり、最後のノードが次のノードとして最初の要素を指し、それに対応して最初のノードが前のノードとして最後の要素を指すため、後者は興味深いものです。次のコードスニペットは、構築されたリストの各ノードの内容を表示するための printNodes 関数を追加していることに注意してください。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
struct Node *prev{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->prev = node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct Node *tmp, *root = nullptr;
struct Node *end = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
root = addNewNode(root, data_set.at(0));
tmp = root;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
if (it == data_set.end() - 1) end = tmp;
}
printNodes(root);
freeNodes(root);
return EXIT_SUCCESS;
}
出力：
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
std::list コンテナを C++ の二重リンクリストとして使用する
あるいは、C++ STL の std::list コンテナを利用することもできます。これは通常、二重リンクリストとして実装され、さまざまな要素操作機能を提供します。さらに、std::list コンテナは、標準ライブラリに含まれる非常に強力なアルゴリズムをサポートするように実装されているため、非常に特別なパフォーマンス特性が必要ない場合でも、ユーザーは開発にかかる時間を節約できます。
#include <iostream>
#include <list>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::list;
using std::string;
template <typename T>
void printList(std::list<T> l) {
for (const auto &item : l) {
cout << item << "; ";
}
cout << endl;
}
int main() {
std::list<int> l = {1, 2, 3, 4};
l.push_back(5);
l.push_front(0);
printList(l);
auto it = std::find(l.begin(), l.end(), 3);
if (it != l.end()) {
l.insert(it, 99);
}
printList(l);
return EXIT_SUCCESS;
}
出力：
0; 1; 2; 3; 4; 5;
0; 1; 2; 99; 3; 4; 5;
