单链表

单链表,不是挨个顺序存储的数据,是互相相连的数据,按照逻辑顺序存放地数据
在这里插入图片描述
这里重点要明白的是其中的逻辑规律,会有点绕口.

单链表

typedef int LDataType;        //别名声明 
typedef struct listNode{         //结构体用来存放数据和下一个地址
    LDataType _data;    
    struct listNode* _next;    //下一个存放地址
}listNode;
typedef struct list{         //存储头结点的位置,也就是图中的第一个方框
    //存放第一个节点的位置
    listNode* _head;
}list;

他就是按照这种连线形式进行存放的,注意理解

接口声明

从接口这里我开始详细的讲:

//1.接口初始化
void listInit(list* lst);
//2.创建空间
listNode* creatNode(LDataType val);
//3.尾插
void listPushBack(list* lst,LDataType val);
//4.尾删
void listPopBack(list* lst);
//5.头插
void listPushFront(list* lst,LDataType val);
//6.头删
void listPopFront(list* lst);
//7.中间插入
void listInsertAfter(listNode* cur, LDataType val);
//8.删除节点
void listEraseAfter(listNode* cur);
//9.查找
listNode* listFind(list* lst, LDataType val);
//10.销毁
void listDestory(list* lst);

接口实现

1.接口初始化

对于这里的接口初始化没有太多要说的,就是将头结点创建出来,等于空就可以了

void listInit(list* lst){ 
    if (lst == NULL)    //如果为空指针,直接返回
        return;
    //初始化为空的链表
    lst->_head = NULL;    
}

2.创建空间

因为单链表这个东西,我们需要一个一个的进行创建比较麻烦,所以我们直接把他封装成一个接口,每次需要的时候直接调用就可以了,比较方便,也容易操作.

listNode* creatNode(LDataType val){ 
    listNode* node = (listNode*)malloc(sizeof(listNode));    //动态开辟一块空间
    node->_data = val;    //将开辟的值进行赋予
    node->_next = NULL;    //next为空,表示为最后一个元素
    return node;        //返回
}

3.尾插

在这里插入图片描述

void listPushBack(list* lst,LDataType val){ 
    if (lst == NULL)        //为空判断
        return; 
    if (lst->_head == NULL){     //如果为空
        lst->_head=creatNode(val);        //直接将这个元素创建在头结点后面
    }
    else{                                     //不为空
        listNode* tail = lst->_head;        //创建一个tail指向头结点
        while (tail->_next != NULL){         //从头进行遍历,直到找到为NULL的最后一个元素
            tail = tail->_next;                //遍历
        }
        tail->_next = creatNode(val);        //寻找到最后一个后,将其进行元素插入,这里是调用了2的操作
    }
}

4.尾删

在这里插入图片描述

void listPopBack(list* lst){ 
    if (lst== NULL||lst->_head==NULL)        //判断是否为空
        return;
    struct listNode* tail = lst->_head;        //让tail指向头结点
    struct listNode* prev = NULL;            
    while (tail->_next != NULL){             //进行遍历
        prev = tail;                        //tail值赋予,也就是找到了倒数第二的位置
        tail = tail->_next;                    //循环
    }
    free(tail);            //释放空间
    if (prev == NULL)        //如果为空,就说明只存在一个数据,将数据删除,就只剩下头结点
        lst->_head = NULL;    //只能让存在的头结点为空
    else                    //如果不为空,则存在元素倒数第二的next指向NULL即可
        prev->_next = NULL; 
}

5.头插

在这里插入图片描述

void listPushFront(list* lst,LDataType val){ 
    if (lst == NULL)        //判空
        return;
    if (lst->_head == NULL)        //如果只有一个头节点
        lst->_head = creatNode(val);    //则直接创建一个新的即可
    else{                         //如果有其他元素
        listNode* node = creatNode(val);    //先创建
        listNode* next = lst->_head;        //让next指向头结点,也就是原来第一个元素的头
        lst->_head = node;        //头结点指向新创建的元素
        node->_next = next;        //新创建元素的next指向原来第一个元素的头
    }
}

要点:!!!

这里主要理解的是你要理解,最开始头结点和指向了原来的第一个元素,这两个地址可以理解成是一样的,所以最后一句node->_next = next;这里的后面的next就是红色三角形这里的地址!!!

6.头删

在这里插入图片描述

void listPopFront(list* lst){ 
    if (lst == NULL||lst->_head==NULL)        //判空
        return;
    struct listNode* next = lst->_head->_next;  //创建一个next指向原来头结点指向的第一个元素
                                                //的next,也就是第二个元素的首地址,连线的地址可以类似于一样
    free(lst->_head);    //释放头结点
    lst->_head = next;    //头结点指向我们上面整理好的第二个元素的头
}

多理解我的话,多画图思考

7.中间插入

在这里插入图片描述

void listInsertAfter(listNode* cur, LDataType val){ 
    listNode* node = creatNode(val);    //创建新元素
    listNode* next = cur->_next;        //创建next指向原来位置的next也就是下一个元素的头(连线地址相等)
    cur->_next = node;                    //上一个元素的next指向新创建的元素
    node->_next = next;                    //创建元素的next指向下一个元素
}

8.删除节点(删除要删除的下一个元素)

在这里插入图片描述

void listEraseAfter(listNode* cur){ 
    listNode* next = cur->_next;    //创建next指向要cur的next
    if (next == NULL)                //判空
        return;
    struct listNode* nextnext = next->_next;    //创建cur的下一个元素的next,也就是最后一个元素的头
    free(next);            //释放空间
    cur->_next = nextnext;        //连接
}

9.查找

listNode* listFind(list* lst, LDataType val){ 
    if (lst == NULL||lst->_head==NULL)        //判空
        return NULL;
    //从头开始遍历
    struct listNode* cur = lst->_head;    //cur指向头结点
    while (cur){         //循环
        if (cur->_data == val)        //当寻找到相等的,直接返回其位置
            return cur;
        cur = cur->_next;        //循环进行
    }
    return NULL;        //找不到返回空
}

简单,理解就可以

10.销毁

因为释放单链表需要地址,先将下一个地址找到,再将这个进行释放,循环进行.

void listDestory(list* lst){ 
    if (lst->_head == NULL||lst==NULL)    //判空
        return;
    else{                                     //不为空向下执行
        listNode* cur = lst->_head;            //cur指向头结点
        while (cur){                         //循环
            listNode* next = cur->_next;    //指向下一个头结点
            free(cur);                        //释放这个空间
            cur = next;                        //向后移一个,继续释放
        }
    }
    lst->_head = NULL;        //最后将头结点为空操作
}