用C语言实现单链表的各种操作(一)

“用C语言实现单链表的各种操作(一)”详细介绍了如何通过C语言来实现单链表的常见操作。下面，我会结合该文章的内容，对其进行完整攻略的介绍。

文章的主要内容包括：单链表的定义、单链表的初始化、判断单链表是否为空、获取单链表中元素个数、在链表开头插入元素、在链表末尾插入元素、在链表中间插入元素、删除链表中指定元素、在链表中查找指定元素、链表的反转以及链表的销毁。下面将逐一介绍这些操作。同时，我们假设我们已经定义了如下结构体：

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

1. 单链表的定义

单链表定义为一个指向Node结构体的指针head，并且初始化为NULL。

Node *head = NULL;

2. 单链表的初始化

单链表初始化即将head指针初始化为NULL即可。

head = NULL;

3. 判断单链表是否为空

判断单链表是否为空就是判断head指针是否为NULL。

if (head == NULL)
{
    printf("Single Linked List is empty.\n");
}
else
{
    printf("Single Linked List is not empty.\n");
}

4. 获取单链表中元素个数

获取单链表中元素个数可以遍历单链表计数的方法实现，这里采用while循环实现。定义一个计数器cnt，当链表中有下一个节点时，cnt自增1，直到链表遍历完毕。

int cnt = 0;
Node *p = head;
while (p != NULL)
{
    cnt++;
    p = p->next;
}
printf("Single Linked List size is %d.\n", cnt);

5. 在链表开头插入元素

在链表开头插入元素，即在head指针指向的节点前插入元素。具体操作是：新建一个节点，并将新节点的next指向head所指向的节点，然后将head指针指向新节点。

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

6. 在链表末尾插入元素

在链表末尾插入元素，即找到最后一个节点，然后将新的节点插入到其后面。

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

if (head == NULL)
{
    head = newNode;
}
else
{
    Node *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = newNode;
}

7. 在链表中间插入元素

在链表中间插入元素，即给定某个节点，在该节点后插入新节点。具体操作是：找到该节点，将新节点插入到该节点后面。

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

Node *p = head;
while (p != NULL && p->data != insertValue)
{
    p = p->next;
}

if (p == NULL)
{
    printf("Insertion failed. Node with value %d not found.\n", insertValue);
}
else
{
    newNode->next = p->next;
    p->next = newNode;
}

8. 删除链表中指定元素

删除链表中指定元素，即找到该元素，然后将其从链表中删除。具体操作是：找到该元素所在的节点，将该节点从链表中删除。

Node *p = head;
Node *pre = NULL;

while (p != NULL && p->data != deleteValue)
{
    pre = p;
    p = p->next;
}

if (p == NULL)
{
    printf("Deletion failed. Node with value %d not found.\n", deleteValue);
}
else
{
    if (pre == NULL)
    {
        head = p->next;
    }
    else
    {
        pre->next = p->next;
    }

    free(p);
    p = NULL;
}

9. 在链表中查找指定元素

在链表中查找指定元素，即查找链表中是否存在该元素。具体操作是：遍历链表，判断元素是否在链表中。

Node *p = head;
while (p != NULL && p->data != searchValue)
{
    p = p->next;
}

if (p == NULL)
{
    printf("Node with value %d not found.\n", searchValue);
}
else
{
    printf("Node with value %d found.\n", searchValue);
}

10. 链表的反转

链表的反转，即将单链表中的元素反转过来。将head指针指向的单链表中的元素倒序排列。

Node *pre = NULL;
Node *p = head;
Node *next = NULL;
while (p != NULL)
{
    next = p->next;
    p->next = pre;
    pre = p;
    p = next;
}
head = pre;

11. 链表的销毁

链表的销毁，即释放链表中的所有元素所占用的内存空间。具体操作是：遍历单链表，逐个释放节点占用的内存空间，并将节点指针设为NULL。

Node *p = head;
Node *next = NULL;

while (p != NULL)
{
    next = p->next;
    free(p);
    p = next;
}
head = NULL;

示例1：

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

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

以上代码代码创建了两个节点，一个节点的data为1，另外一个节点的data为2，并且让head指针指向第一个节点。同时将第二个节点作为第一个节点的下一个节点。

示例2：

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

while (head != NULL)
{
    Node *p = head;
    head = head->next;
    free(p);
}

以上代码销毁了一个单链表，将节点依次释放，并且将head指针设为NULL。