如何检查链表是否为空

Question

我是C语言的新手，有一个问题。

如何检查链表是否为空？

我有一个结构体_node。

typedef struct _node{
    int data;
    struct _node *next;
}node;

如果我已经初始化了node *list，但没有对它做任何操作（即没有给list->data赋值），我该如何检查它是否为空？

我尝试了if (node == NULL){break}，但不起作用。

谢谢帮忙！

- help_needed

---

通常情况下，在插入数据之前，你会将list = NULL。在这一点上，你会分配一个节点，将list指向该内存，设置数据成员并将下一个成员设置为NULL。同样，当删除列表时，在移除最后一条数据后，你需要将list设置为NULL。 - enhzflep

Answer 1

简介：

通常有两种使用链表的方式：带根元素和不带根元素。

没有根元素时，当列表为空时，您的列表指针为NULL:

node *list;
...
if (list == NULL) { /* empty list */ }

有了root，就总是有一个元素。但它可以用两种方式：

一种是仅用于提供指向第一个元素的指针。

node *root;
...
if (root->next == NULL) { /* empty list */ }

或者让最后一个元素链接回根元素以形成循环。这个概念的优点是“下一个”元素永远不会是NULL，因此您不需要检查它。在这种情况下，如果根指向自身，则列表为空。

node *root;
...
if (root->next == root) { /* empty list */ }

---

答案：

根据您的描述，您已经分配了一个节点。这意味着您要使用“root”方法（第二或第三个示例）。但是，如果您想使用第一种变体，则不应分配节点，因为它不包含数据。

对于“root”方法，确实有一个（且仅有一个）不包含数据的节点。但是对于简单的链表，所有节点都必须包含数据。

- DarkDust

Answer 2

我会简单地表达。

检查头指针 - 如果为NULL，则列表中没有条目。

int isEmpty( node * list )
 {
   if( !list )
      return 1;
   return 0;
 }

- notnull

---

会做同样的事情，或者 return list == NULL ? 1 : 0; ;) - pzaenger

或者更简短一些：return !list; :-) - DarkDust

@pzaenger，@DarkDust：同意，但是再加两行会让它对于C语言新手更加易懂 ;) - notnull

Answer 3

有时候在创建变量时，C会自动将所有数据清零。在其他情况下，变量将包含垃圾值。你需要学习规则来控制这个问题，但是作为一个初学者，你应该始终明确地初始化你的变量。

在链表中，当你向列表添加一个节点时，你应该始终确保将NULL设置到next指针中，以便正确地终止列表。

你的链表应该有一个“头”指针。如果head被设置为NULL，则表示你有一个长度为零的链表；如果head具有除NULL以外的任何值，则你至少必须有一个节点在链表中，因此链表的长度必须至少为1。

因此，只要你小心地初始化了head指针为NULL，你就可以轻松地通过检查head指针是否为NULL来判断列表是否为空。

但是你的问题实际上是关于 data 成员变量的。它总会有某种值存在。就像我说的，有时候 C 语言会为你将其设置为零，但有时候它会是不可预测的垃圾值（任何整数值都有可能）。在分配新节点时，你需要将其初始化为一个合理的默认值。例如，data 的有效值可能都大于零，因此你可以将 data 设置为零，以表示它当前为空。

你可以编写一个简单的循环来遍历你的链表并检查每个 data 成员，如果发现任何非零的 data（或任何特殊值标志着它未使用），则返回 true。如果只找到默认的 data 或者链表长度为零，则应返回 false。

- steveha

Answer 4

在构建链表时最好有一个头节点，然后您可以添加节点来构建列表。让该列表变量成为您的头节点。然后要检查链表是否为空，请使用以下代码：

typedef struct _node{
    int data;
    struct _node *next;
}*node;

然后实例化

node list;

要检查链表是否为空，请使用以下方法：

if((list->next)==null)
{
         break;
}

- SoulRayder

---

嗯，如果您不打算使用根/头节点的“循环”概念，那么使用头节点与仅使用变量相比有何优势？我在我的答案中列出了这个变体，但我看不出它的用例/优点。因此，您能解释一下没有循环的头节点相对于直接使用变量的优势是什么吗？ - DarkDust

头结点可用于存储重要数据，包括链表中节点的数量，在非常长的链表或链表数组等复杂情况下可能会很有用。 - SoulRayder