迹忆客 专注技术分享

链表的功能类似于数组，并使用指针来实现。 这是动态数据结构的最简单示例，可以从数组中的任意点增长和收缩。

链表具有多个动态分配的节点，其中包含一个值和一个指针。 本教程将教您三种在 C++ 中检查链表是否为空的方法。

C++ 中使用根元素检查链表是否为空

链表中的根充当一个元素，即使链表为空，该元素也始终存在。 在链表中拥有根的另一个用途是将最后一个元素链接回根，形成一个循环。

在 C++ 中，有两种主要方法可以通过提供指向列表第一个元素的指针来检查链表是否为空（例如： if (root->next == NULL) { /* empty list */ }）或者将链表的列表元素链接回其根以形成循环（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

头节点或根节点表示其在链表中的起始位置。 对于根来说，总是有一个元素。

在 C++ 中不使用根元素检查链表是否为空

如果没有根，当链表为空时，链表指针为 NULL。 这种方法检查链表是否为空的复杂度与检查根元素相同，即 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

仅当节点的下一个指针设置为 NULL 时，链表才能正确终止。 如果链表的头指针设置为NULL，那么它将被称为零长度链表，零长度链表也是一个空列表，因为它代表一个NULL头指针。

C++中使用根点检查链表是否为空

可以将链表的最后一个元素链接到根，形成一个循环，这样可以帮助识别空链表。 利用根点有很多好处，包括永远不会将 NULL 作为下一个元素； 因此，程序员不再需要检查它。

它提供了一些独特的情况，例如如果链表的根点或头点链接回自身，则它代表一个空链表。 如果 if (root->next == root) { /* empyty list */ } 为 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++ 中创建变量或为其分配一些垃圾值，您的数据可能会被中和或清零。 您必须学习显式初始化变量、为它们分配唯一值，并了解管理它的规则。