数据结构--链表（单向链表--有头链表、无头链表）链表的插入、删除、修改、查找

什么是链表？

链表是一种基本的数据结构，用于存储一组数据元素。与数组不同，链表的元素在内存中并不连续存储。链表由一系列节点组成，每个节点包含以下两个主要部分：

1. 数据部分：存储节点所包含的数据。
2. 指针部分：存储指向下一个节点的指针（对于单向链表），或者存储指向前一个节点和下一个节点的指针（对于双向链表）。

链表的主要特点是：
- 动态大小：链表的大小可以根据需要动态增加或减少，而数组的大小在创建时是固定的。
- 插入和删除操作效率高：在链表中进行插入和删除操作时，只需改变指针即可，时间复杂度为 O(1)，而在数组中可能需要移动大量元素，时间复杂度为 O(n)。

常见的链表类型包括：
- 单向链表：每个节点只指向下一个节点。
- 双向链表：每个节点指向下一个节点和前一个节点。
- 循环链表：最后一个节点指向头节点，形成一个环。

链表广泛用于实现各种数据结构，如栈、队列等，以及在需要频繁插入和删除操作的场景中。

图上可以看到，链表其实就是由一个个的结构体连接而成，用next的指针去指向下一个结构体。

最终指向的为NULL，这就是一个有头的单项链表的表示

代码部分（如果需要源码可以私信我）

一、链表的创建

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

Node *Link_init(){
    Node *head = (Node *)malloc(sizeof(Node));
    if(NULL == head){
        printf("malloc is failed!\n");
    }
    head->data = -1;
    head->next = NULL;
    return head;
}

这里定义了一个名为 node 的结构体，用于表示链

该结构体包含两个成员：

int data;：用于存储节点的数据，类型为整数。
struct node *next;：指向下一个节点的指针，类型为指向 node 结构体的指针。

这个函数的返回类型是 Node *，即返回一个指向链表头节点的指针。

Node *head = (Node *)malloc(sizeof(Node))：使用 malloc 函数动态分配内存，为一个 Node 类型的节点分配空间，并将其指针赋值给 head 变量。

if(NULL == head) printf("malloc is failed!\n") ：检查内存分配是否成功。如果 head 为 NULL，则表示内存分配失败，输出错误信息。

head->data = -1：初始化链表头节点的数据，将其设置为 -1。

head->next = NULL：将链表头节点的 next 指针初始化为 NULL，表示当前节点后面没有其他节点。

return head：返回指向链表头节点的指针。

二、链表的插入

void Link_insert_head(Node *head,int num){
    Node *new = (Node *)malloc(sizeof(Node));
    if(NULL == new){
        printf("new_node malloc is failed!\n");
    }
    new->data = num;
    new->next = NULL;
    //insert
    new->next = head->next;
    head->next = new;
}

当我们插入数据时，首先要定义一个节点（前面提到过链表就是由一个个节点连接而成），还是和前面一样先判断开辟的堆区malloc是否申请成功，初始化new的值new->data就是我们需要插入的数据num，next同样也是指向NULL，最后这两步是整个代码的关键部分，首先我们需要将head->next 赋值给new->next,然后将new赋值给head->next，这样就完成了插入（头插法）。

三、链表的删除

int Linklist_len(Node *head){
    int count = 0;
    Node *p = head->next;
    while(p != NULL){
        count++;
        p = p->next;
    }
    return count;
}

void Linklist_del_num(Node *head,int num){
    if(NULL == head){
        printf("Linklist is error\n");
    }

    Node *p = head;
    Node *q = p->next;
    
    int len = Linklist_len(head);
    for(int i=0;i<len;i++){
        if(q->data == num){
            p->next = q->next;     
        }
         p = p->next;
         q = p->next;
        if(p->next == NULL){
            break;
        }
        
    }
    free(q);
    q = NULL;
}

Linklist_len(Node *head):
- 该函数计算并返回链表的长度。它接收一个指向链表头节点的指针 head。
- 从 head->next 开始遍历链表（假设头节点不存储有效数据），并统计节点数量。每次遇到一个节点就增加计数 count，直到到达链表尾（即 p 为 NULL）。最终返回计数值 count。
Linklist_del_num(Node *head, int num):
- 此函数用于删除链表中所有值为 num 的节点。
- 首先检查链表是否为 NULL，若是则输出错误信息。
- 定义两个指针 p 和 q，p 初始化为 head，q 初始化为 p->next。
- 通过 Linklist_len 获取链表的长度。在遍历过程中，如果发现节点 q 的数据等于 num，则通过更新指针 p->next 来跳过该节点，从而实现删除。
- 然而，在代码中存在一些问题：
  - 释放节点 q 的语句不适用于发布已经遍历的节点，因为删除节点后 q 可能带有未定义值（释放已被删除的节点，可能导致错误）。
  - 遍历逻辑可能会导致某些符合条件的节点无法删除，特别是在指针更新后没有正确检查是否到达链表尾的情况。

四、链表修改

void Linklist_change_num(Node *head,int num,int change_num){
    if(NULL == head){
        printf("Linklist is error\n");
    }
    Node *p = head->next;
    for(int i=0;i<Linklist_len(head);i++){
        if(p->data == num){
            p->data = change_num;
        }
        p = p->next;
    }
    
}

该函数 Linklist_change_num 用于遍历一个链表 (head)，查找所有值为 num 的节点，并将其数据值更改为 change_num。如果链表为空，函数会打印错误信息。尽管代码包含了逻辑错误（例如，如果 head 为空时会继续执行），并且未考虑链表的头节点的处理。

五、链表查询

void Linklist_search_num(Node *head,int num){
    if(NULL == head){
        printf("Linklist is error\n");
    }
    Node *p = head->next;
    for(int i=0;i<Linklist_len(head);i++){
        if(p->data == num){
            printf("search num is :%d\n",p->data);
        }
        if(p->next != NULL){
             p = p->next;
        }
    } 

}

该函数 `Linklist_search_num` 用于在链表中查找值为 `num` 的节点。如果链表为空，函数会打印错误信息。遍历链表时，如果找到 `data` 等于 `num` 的节点，就打印该数据值。函数还确保在遍历时不会访问空指针，但有逻辑错误，可能导致每个节点都被检查。具体来说，在循环中，`p` 的更新条件可能导致最后一个节点不会被检查。

标签：Node,head,--,有头,next,链表,num,节点
From： https://blog.csdn.net/fzxznb/article/details/141438255