C++ でリンク リストが空かどうかを確認する
- ルート要素を使用して C++ でリンク リストが空かどうかを確認する
- C++ でルート要素を使用せずにリンク リストが空かどうかを確認する
- C++ でルート ポイントを使用してリンク リストが空かどうかを確認する
リンク リストは配列として機能し、その実装にはポインターを使用します。 これは、配列内の任意のポイントから拡大および縮小できる動的データ構造の最も単純な例です。
リンク リストには、値とポインタを含む複数の動的に割り当てられたノードがあります。 このチュートリアルでは、リンクされたリストが C++ で空かどうかを確認する 3つの方法を説明します。
ルート要素を使用して C++ でリンク リストが空かどうかを確認する
リンクされたリストのルートは、リストが空の場合でも常に存在する要素として機能します。 リンクされたリストにルートを持つ別の用途は、最後の要素をルートにリンクしてサイクルを形成することです。
C++ では、リンクされたリストが空かどうかを確認する主な方法が 2つあります。リストの最初の要素へのポインターを提供する方法です (例: if (root->next == NULL) { /* empty list */ }) またはリンクされたリストのリスト要素をそのルートにリンクバックして循環を形成する (if (root->next == root) { /*empty list */ })。 ルート要素を使用してリンク リストが空かどうかを確認するには、データを保持しないリンク リスト ノードが少なくとも 1つ必要です。
コード例:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *next;
Node() {
data = 0;
next = NULL;
}
};
class linked_list {
Node *root;
public:
linked_list() { root = NULL; }
Node *getRoot() { return root; }
void add_node(int n) {
Node *temp = new Node();
temp->data = n;
temp->next = NULL;
if (root == NULL) {
root = temp;
root->next = root;
} else {
Node *last = root;
while (last->next != root) {
last = last->next;
}
temp->next = root;
last->next = temp;
}
}
void printList() {
Node *temp = root;
if (temp != NULL) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != root);
}
}
bool isEmpty() {
if (root->next == root && root->data == 0) return true;
return false;
}
};
int main() {
linked_list l1;
l1.add_node(5);
l1.add_node(10);
l1.add_node(15);
if (l1.isEmpty())
cout << "The list is empty!\n";
else {
cout << "The list is not empty! List contains:\n";
l1.printList();
}
return 0;
}
出力：
The list is not empty! List contains:
5 10 15
head または root ノードは、リンクされたリスト内の開始位置を表します。 root では、常に 1つの要素があります。
C++ でルート要素を使用せずにリンク リストが空かどうかを確認する
root がない場合、リンクされたリストが空の場合、リスト ポインターは NULL になります。 このアプローチでリンクされたリストが空かどうかをチェックする複雑さは、root 要素、つまり O(1) の場合と同じです。
新しいノードを割り当てるときに、適切なデフォルト値を変数に初期化する必要があります。これにより、長さゼロのデータ メンバーを簡単に識別して、その NULL 動作を識別できるようになります。
コード例:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
};
void push(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
bool isEmpty(Node** list) {
if ((*list) == NULL) return true;
return false;
}
void printList(Node* node) {
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
int main() {
Node* list = NULL;
if (isEmpty(&list))
cout << "List is Empty" << endl;
else {
cout << "List is not empty! List contains:"
<< " ";
printList(list);
}
// Inserting some elements in the list
push(&list, 8);
push(&list, 4);
if (isEmpty(&list))
cout << "The List is Empty" << endl;
else {
cout << "The list is not empty! The list contains:"
<< " ";
printList(list);
}
return 0;
}
出力：
The List is Empty
The list is not empty! The list contains: 4 8
リンクされたリストは、ノードの next ポインターが NULL に設定されている場合にのみ適切に終了します。 リンク リストの head ポインターが NULL に設定されている場合、それは長さ 0 のリンク リストと呼ばれ、長さ 0 のリンク リストは NULL リード を表すため、空のリストでもあります。 ポインター。
C++ でルート ポイントを使用してリンク リストが空かどうかを確認する
リンク リストの最後の要素を root にリンクしてサイクルを形成すると、空のリンク リストを識別するのに役立ちます。 ルート ポイントを利用すると、次の要素として NULL を持たないなど、さまざまな利点があります。 したがって、プログラマーはこれをチェックする必要がなくなりました。
リンクされたリストの root または head がそれ自体に戻るリンクを指す場合、それは空のリンクされたリストを表すなど、いくつかのユニークなケースを提供します。 if (root->next == root) { /* 空のリスト */ } が true の場合、連結リストは空です。
疑似コード:
node *root;
... // process code (exp.)
if (root -> next == root) { /* empty list */ }
// check the head pointer - if it is NULL, there's no entry in the list.
int isEmpty( node * list )
{
if( !list )
return 1;
return 0; // otherwise in case false check
}
C++ で変数を作成したり、ガベージ値を割り当てたりすると、データが無効化またはゼロ化される可能性があります。 変数を明示的に初期化し、それらに一意の値を割り当て、それを管理する規則を学ぶ必要があります。
Hassan is a Software Engineer with a well-developed set of programming skills. He uses his knowledge and writing capabilities to produce interesting-to-read technical articles.
GitHub