C++ でリンクリストのノードを削除する
この記事では、リンクリスト C++ の特定のノードを削除する関数を実装する方法について説明します。
リンクリスト内の特定のノードを削除する関数を実装する
この記事では、STL のコンテナーを使用せずに、単一リンクリストを最初から実装します。したがって、リンクリスト内のノードを管理するために必要ないくつかの関数を定義する必要があります。
insertNode 要素は、新しいリンクリストを作成するために呼び出す必要のあるコア関数です。リストの先頭を格納する必要があるため、insertNode はタイプ ListNode のノードへのポインタを返します。後者は、リンクリストノードの最小限の表現です。次のノードへのポインタと文字列データオブジェクトのみが含まれます。
プログラムのテストおよびデモンストレーション中に、ユーザーコンソールにいくつかのメッセージを表示するためのいくつかのユーティリティ機能を用意することが重要です。この場合、printNodes 要素を使用して、指定されたリスト構造内のすべてのノードを出力します。さらに、動的メモリに新しいノードを割り当てるときに、freeNodes 関数を使用して、プログラム終了時にリスト内の既存のすべてのノードの割り当てを解除する必要があります。
次のコードスニペットの main 関数に示すように、任意のデータでリストを作成したら、ノード削除操作を実装する deleteNode を呼び出す準備ができています。ノードを削除するには、ノードでいくつかのコーナーケースを処理する必要があります。つまり、指定されたノードがリストの先頭と同じである場合のシナリオと、指定されたノードがリスト内の唯一のノードである場合のシナリオです。
後者のシナリオでは、ノードポインタで delete 演算子を呼び出して、関数から戻ることができます。nullptr をアドレスに割り当てることは重要ですが、これは、main 関数の同じ head 変数に新しい要素を追加するのに役立つためです。
一方、リストに他のノードがある場合にヘッドノードを削除するのは比較的注意が必要です。2 番目のノードの内容をヘッドノードにコピーし、前のノードを削除する必要があります。いずれの場合も、関数呼び出しが成功したことを示す EXIT_SUCCESS 値を返すことに注意してください。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, head);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
出力：
node 0 - data: Xenial
node 1 - data: Artful
-----------------------------------
node 0 - data: Artful
残りの関数コードは、指定されたノードがリストチェーンからフック解除され、delete 演算子を使用して割り当てが解除される通常のケースを実装します。ただし、この操作では前のノードを見つける必要があります。これは、リストの先頭を除くすべてのノードの線形時間操作です。通常、リストの終わりを一定時間削除することを保証するために、リストの終わりをリンクリスト構造に格納する必要があります。
次のコードスニペットは、ノードがリストの中央から削除される、別の main 関数のシナリオを示しています。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
auto iter = insertNode(head, "Bionic");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, iter);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
出力：
node 0 - data: Xenial
node 1 - data: Bionic
node 2 - data: Artful
-----------------------------------
node 0 - data: Xenial
node 1 - data: Artful
