C++에서 연결된 목록이 비어 있는지 확인
- 루트 요소를 사용하여 C++에서 연결된 목록이 비어 있는지 확인
- C++에서 루트 요소를 사용하지 않고 연결된 목록이 비어 있는지 확인
- 루트 포인트를 사용하여 C++에서 연결된 목록이 비어 있는지 확인
연결된 목록은 배열로 작동하며 구현을 위해 포인터를 사용합니다. 배열의 모든 지점에서 확장 및 축소할 수 있는 동적 데이터 구조의 가장 간단한 예입니다.
연결된 목록에는 값과 포인터를 포함하는 동적으로 할당된 여러 노드가 있습니다. 이 튜토리얼에서는 C++에서 연결된 목록이 비어 있는지 확인하는 세 가지 방법을 알려줍니다.
루트 요소를 사용하여 C++에서 연결된 목록이 비어 있는지 확인
연결된 목록의 루트는 목록이 비어 있어도 항상 존재하는 요소 역할을 합니다. 연결된 목록에 루트가 있는 다른 용도는 마지막 요소를 다시 루트에 연결하여 순환을 형성하는 것입니다.
C++에는 목록의 첫 번째 요소에 대한 포인터를 제공하여 연결 목록이 비어 있는지 확인하는 두 가지 기본 방법이 있습니다(예: if (root->next == NULL) { /* 빈 목록 * / }) 또는 링크된 목록의 목록 요소를 루트에 다시 연결하여 순환을 형성합니다(if (root->next == root) { /*empty list */ }). 루트 요소를 사용하여 연결 목록이 비어 있는지 확인하려면 데이터를 보유하지 않는 연결 목록 노드가 하나 이상 필요합니다.
코드 예:
#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에는 항상 하나의 요소가 있습니다.
C++에서 루트 요소를 사용하지 않고 연결된 목록이 비어 있는지 확인
루트가 없으면 연결된 목록이 비어 있을 때 목록 포인터는 NULL입니다. 이 접근 방식에서 연결된 목록이 비어 있는지 여부를 확인하는 복잡성은 root 요소, 즉 O(1)과 동일합니다.
NULL 동작을 식별하기 위해 길이가 0인 데이터 멤버를 쉽게 식별할 수 있도록 새 노드를 할당할 때 합리적인 기본값을 변수로 초기화해야 합니다.
코드 예:
#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
연결된 목록은 노드의 다음 포인터가 NULL로 설정된 경우에만 적절하게 종료됩니다. 연결된 목록의 head 포인터가 NULL로 설정되면 길이가 0인 연결 목록이라고 하며 길이가 0인 연결 목록도 NULL 리드를 나타내므로 빈 목록입니다. 바늘.
루트 포인트를 사용하여 C++에서 연결된 목록이 비어 있는지 확인
연결된 목록의 마지막 요소를 루트에 연결하여 빈 연결 목록을 식별하는 데 도움이 되도록 순환을 형성할 수 있습니다. 루트 포인트를 활용하면 다음 요소로 NULL을 사용하지 않는 등 다양한 이점이 있습니다. 따라서 프로그래머는 더 이상 이를 확인할 필요가 없습니다.
연결된 목록의 루트 또는 헤드 지점이 자신에게 다시 연결되는 경우 빈 연결 목록을 나타내는 것과 같은 몇 가지 고유한 경우를 제공합니다. if (root->next == root) { /* 빈 목록 */ }이 참이면 연결된 목록이 비어 있습니다.
의사 코드:
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++에서 일부 가비지 값을 할당하면 데이터가 무효화되거나 0이 될 수 있습니다. 변수를 명시적으로 초기화하고, 고유한 값을 할당하고, 변수를 관리하는 규칙을 배워야 합니다.
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