猿创征文 | 内存管理实现单链表的插入和删除

内存管理实现单链表的插入和删除

1.收获

进一步理解动态内存，指针，和结构体

2. 什么是单链表？

在数据结构中，存储结构有一种是链式存储结构。单链表就是链式存储的一种实现方式。

​​ ​​它与顺序结构存储不同，顺序结构在内存中开辟的空间一定是连续的，例如我们的数组就是顺序存储。

单链表中每个节点（矩形）在内存中的地址不一定是连续的，通过指针来找到下一个节点。
每一个节点中存放两个内容，一个是数据，一个是指针。指针是用来找到下一个节点。
也就是说，下一个节点，只能通过它上一个节点去访问它。

这里介绍单链表的头插入和头删除

这里讲的动态内存函数是malloc和free
简单介绍一下这两个函数。
malloc()
向堆区申请一块空间，返回值是地址，地址的类型是void*因此在接收这个地址的时候，需要强制类型转换。
()内部是你需要申请多大的空间单位是字节。
一般可以这样malloc( sizeof( 类型 )*常数 )使用 。
int * p = (int * ) malloc ( sizeof(int) * 10);
free()
释放在堆区开辟的空间，即释放malloc,realloc,calloc开辟的空间
()内部是 要释放空间的起始地址。

3.节点的创建

typedefstructNode{int data;//存数据structNode* next;//指向下一个节点（存地址）}Node_t;//将类型 struct Node 重命名为 Node_t

这里要注意的是，typedef重命名结构体类型名，修改后名字的位置在’ ; '的前面，即Node_t == struct Node

4.主函数的实现

intmain(){//头节点
    Node_t* head =AollocNode(0);//该函数用来申请空间，和存数据int i =0;printf("头插入...\n");for(i =1; i <10; i++){//插入节点//我们需要知道地址才能插入，所以要传入头节点。//i 表示我们插入的数据。HeadInsertNode(head, i);//展示插入的效果ShowNode(head);}printf("头删除...\n");for(i =1; i <10; i++){//同样的我们要删除节点需要知道位置HeadDeleteNode(head);//展示删除的效果ShowNode(head);}//堆区申请的空间需要释放回去//避免内存泄露free(head);//避免野指针，将指针置为NULL
    head =NULL;return0;}

​

头节点就相当于火车头，其他节点相当于车厢。头节点是链表的起始部位，(给你一个地址）要通过头节点才能对单链表进行操作。

5.子函数的实现

5.1 AollocNode的实现

功能：在堆区开辟空间，存储数据（赋值）
在初始化的时候一般默认下一个节点指向NULL（避免野指针）

Node_t*AollocNode(int x){
    Node_t* newnode =(Node_t*)malloc(sizeof(Node_t));
    newnode->data = x;//存数据
    newnode->next =NULL;//指向下一个节点(最后一个节点指向NULL)return newnode;}

5.2 HeadInsertNode的实现

如何做到头插入？一定是改变指针的指向来实现的，看图理解。

第一次头插入

第二次头插入

第三次头插入

看了这三张图，相信你一定有所发现。头插入，是通过头节点和新节点的指向来达到能够连续访问节点的目的。
我们来看代码：

voidHeadInsertNode(Node_t* head,int x){
    Node_t* new =AollocNode(x);//新增节点,x为存储的数据。
    new->next = head->next;
    head->next = new;}

5.3 ShowNode的实现

功能：打印节点中存放的数据。

ShowNode(Node_t* head){
    Node_t* p = head->next;//指向第一节点while(p)//直到指向NULL循环结束{printf("%d->", p->data);//打印数据Sleep(1000);//停屏1s 看打印效果 图片看不出打印效果，可以自行尝试，更加理解头插入是什么样的。
        
        p = p->next;//指向下一个节点}printf("NULL\n");//为了更了解单链表的样子才如此设计。}

运行结果：

5.4 HeadDeleteNode的实现

这个头删除是最简单的。只要将头节点指向的第一个节点释放，并且头节点指向第二个节点，就完成了删除。

为什么可以这么做呢？我们使用的是内存管理的函数，开辟的空间，是可以free。释放之后就把原有所属的空间归还给操作系统了。

我们来看看图。

假设插入三次。

先看原图

第一次头删除

第二次头删除

第三次头删除

voidHeadDeleteNode(Node_t* head){
    Node_t* p = head->next;//新增指针p指向头节点指向的第一个节点

    head->next = p->next;//改变头节点的指向，指向第一个节点的下一个节点//即头节点指向第二个节点free(p);//p已经指向了第一个节点的起始地址，free(p)就是释放第一个节点}

运行结果：

6.源代码

#include<stdio.h>#include<stdlib.h>#include<Windows.h>typedefstructNode{int data;structNode* next;}Node_t;//将类型 struct Node 重命名为 Node_t//向堆区开辟空间给节点，并赋值
Node_t*AollocNode(int x){
    Node_t* newnode =(Node_t*)malloc(sizeof(Node_t));
    newnode->data = x;//存数据
    newnode->next =NULL;//指向下一个节点(最后一个节点指向NULL)return newnode;}voidHeadInsertNode(Node_t* head,int x){
    Node_t* new =AollocNode(x);//新增节点,x为存储的数据。
    new->next = head->next;
    head->next = new;}ShowNode(Node_t* head){
    Node_t* p = head->next;while(p){printf("%d->", p->data);Sleep(100);
        p = p->next;}printf("NULL\n");}voidHeadDeleteNode(Node_t* head){
    Node_t* p = head->next;//新增指针p指向头节点指向的第一个节点

    head->next = p->next;//改变头节点的指向，指向第一个节点的下一个节点//即头节点指向第二个节点free(p);//p已经指向了第一个节点的起始地址，free(p)就是释放第一个节点}intmain(){//头节点（第一个节点）
    Node_t* head =AollocNode(0);//int i =0;printf("头插入...\n");for(i =1; i <10; i++){//插入节点//我们需要知道地址才能插入，所以要传头节点。//i 表示我们插入的数据。HeadInsertNode(head, i);//展示插入的效果ShowNode(head);}printf("头删除...\n");for(i =1; i <10; i++){//同样的我们要删除节点需要知道位置HeadDeleteNode(head);//展示插入的效果ShowNode(head);}//堆区申请的空间需要释放回去//避免内存泄露free(head);//避免野指针，将指针置为NULL
    head =NULL;return0;}

7.结束语

可以自己尝试去写写，图片也自己画画，加深印象。
希望对你有所帮助。