C语言实现无头单链表详解

什么是无头单链表？

单链表是一种非常常见的数据结构，它由一个个结点组成，每个结点包含两部分：数据部分和next指针部分。数据部分可以存放任何类型的数据，next指针则用于连接下一个结点。

而无头单链表与单链表类似，只是它没有头结点。头结点一般来说用于存放链表的长度、头指针等信息，而无头单链表只有一个指向第一个结点的指针，也就是没有这些额外的信息。

如何实现无头单链表？

下面我们来介绍如何用C语言实现无头单链表。

首先，定义一个结构体来表示单链表的结点：

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

其中，data表示结点中存放的数据，next表示指向下一个结点的指针。

接下来，定义一个指向第一个结点的指针：

Node *head = NULL;

表示空链表。

插入结点

下面是向链表中插入一个新结点的代码：

Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = head;
head = newNode;

其中，先创建一个新结点newNode，并将其data域赋值为新插入的数据，next域赋值为head。然后将新的头结点指针head指向newNode。

这段代码的作用是将新结点插入到链表的最前面。

删除结点

下面是删除链表中第一个出现的某个元素的代码：

Node *current = head;
Node *previous = NULL;
while (current != NULL && current->data != data) {
    previous = current;
    current = current->next;
}
if (current != NULL) {
    if (previous == NULL) {
        head = current->next;
    } else {
        previous->next = current->next;
    }
    free(current);
}

其中，current表示要删除的结点，previous表示current前面的结点。遍历链表找到要删除的结点后，如果previous为空，表示要删除的是头结点，需要将head指向当前结点的next域。否则，将previous的next指针指向current的next指针，即为删除操作。

示例说明

我们来看一个简单的示例，创建一个空的链表，插入三个结点，然后删除第二个结点：

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    Node *head = NULL;
    int data[] = {1, 2, 3};
    int i;

    // 插入结点
    for (i = 0; i < 3; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data[i];
        newNode->next = head;
        head = newNode;
    }

    // 遍历链表
    Node *current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");

    // 删除结点
    Node *previous = NULL;
    current = head;
    while (current != NULL && current->data != 2) {
        previous = current;
        current = current->next;
    }
    if (current != NULL) {
        if (previous == NULL) {
            head = current->next;
        } else {
            previous->next = current->next;
        }
        free(current);
    }

    // 遍历链表
    current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");

    return 0;
}

输出结果为：

3 2 1 
3 1 

这个示例展示了如何创建一个无头单链表，向链表中插入元素，并删除其中的一项，最后输出结果。

再看一个示例，把链表逆序输出：

#include <stdio.h>
#include <stdlib.h>

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

Node *reverse(Node *head) {
    Node *newHead = NULL;
    while (head != NULL) {
        Node *next = head->next;
        head->next = newHead;
        newHead = head;
        head = next;
    }
    return newHead;
}

int main() {
    Node *head = NULL;
    int data[] = {1, 2, 3, 4, 5};
    int i;

    // 插入结点
    for (i = 0; i < 5; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data[i];
        newNode->next = head;
        head = newNode;
    }

    // 反转链表
    Node *newHead = reverse(head);

    // 遍历链表
    Node *current = newHead;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");

    return 0;
}

这个示例演示了如何把无头单链表逆序输出，在reverse函数中，不断将head指向的结点插入到newHead之前，从而实现链表逆序。

输出结果为：

5 4 3 2 1 

总结

本文介绍了如何用C语言实现无头单链表，包括插入结点、删除结点、遍历链表、逆序输出链表等操作。使用无头单链表时需要注意，它没有头结点，需要特别处理链表是否为空的情况。同时，无头单链表是一种简单而有效的数据结构，用于存储大小不确定的数据，应用广泛。