前言

1. 什么是链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。与顺序表不同，链表的存储数据在内存是随机分布的。

2. 链表的分类

链表的种类多种多样，其中最常见的有八种，它们大致可以分为三类：

1 单向和双向

2 带头和不带头

3 循环和不循环

本章将对单向不带头不循环链表进行详细讲解

单向不带头不循环链表

1. 单链表的功能 


单链表的主要功能有以下几个：

1. 打印单链表
2. 头插
3. 头删
4. 尾插
5. 尾删
6. 查找

7. 在指定节点之前插入数据

8. 在指定节点之后插入数据
9. 删除指定节点数据
10. 删除指定节点之后的数据
11. 销毁单链表

2. 单链表的定义

一个结构体中包含两个成员。一个是存储数据，一个存放下一个结点的地址（当下一个节点为空时保存的地址为NULL)

typedef int SLTDataType;//将int类型命名为SLTDataType，便于后续更改
typedef struct SListNode
{
	SLTDataType data; //存储数据
	struct SListNode* next; //存储下一个节点地址
}SListNode;

3. 单链表功能实现

创建新节点

缩减代码，避免代码冗余

SLTNode* BuyNode(SLTDataType x) {
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    //如果创建失败
    if (node == NULL) {
        perror("malloc fail!\n");
        exit(1);
    }
    node->data = x;
    node->next = NULL;
    return node;//返回该节点
}

1. 打印单链表

void SLTPrint(SLTNode* phead) {
    SLTNode* cur = phead;
    while (cur) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}


2. 头插

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* node = BuyNode(x);//创建新节点
    node->next = *pphead;//头插
    *pphead = node;//将头插进来的节点作为头节点
}


3. 头删

void SLTPopFront(SLTNode** pphead) {
    assert(pphead);
    assert(*pphead);//链表不为空
    SLTNode* first = *pphead;
    *pphead = (*pphead)->next;//头删
    free(first);//释放头节点
    first = NULL;
}


4. 尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
    assert(pphead);//pphead不为空
    SLTNode* node = BuyNode(x);//创建新节点
    //如果链表为空
    if (*pphead == NULL) {
        *pphead = node;//新节点为头节点
        return;
    }
    //找尾
    SLTNode* cur = *pphead;
    while (cur->next) {
        cur = cur->next;
    }
    cur->next = node;//将新节点进行尾插
}


5. 尾删

void SLTPopBack(SLTNode** pphead) {
    assert(pphead);
    assert(*pphead);//链表不为空
    //如果链表只有一个节点
    if ((*pphead)->next == NULL) {
        free(*pphead);//释放头节点
        *pphead = NULL;//将头节点位置置为空
        return;
    }
    //找尾
//    SLTNode *cur = *pphead;
//    SLTNode *prev = NULL;
//    while(cur->next){
//        prev = cur;
//        cur = cur->next;
//    }
//    prev->next = NULL;
//    free(cur);
//    cur = NULL;
    SLTNode* tail = *pphead;
    //寻找尾节点的前一个节点
    while (tail->next->next) {
        tail = tail->next;
    }
    free(tail->next);//释放尾节点
    tail->next = NULL;
}


6. 查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
    assert(phead);
    SLTNode* cur = phead;
    while (cur) {
        //如果找到该节点，返回该节点
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;//否则返回空
}

7. 在指定节点之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead);
    assert(pos);//检测pos节点不为空，如果pos节点不为空，那么该链表也不为空
    SLTNode* node = BuyNode(x);
    //如果pos==头节点
    if (*pphead == pos) {
        //        node->next = pos;
        //        *pphead = node;
        SLTPushFront(pphead, x);//头插
        return;
    }
    //找pos的前一个节点
    SLTNode* prev = *pphead;
    while (prev->next) {
        if (prev->next == pos) {
            break;
        }
        prev = prev->next;
    }
    //插入pos节点之前
    node->next = pos;
    prev->next = node;
}

8. 在指定节点之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
    assert(pos);
    SLTNode* node = BuyNode(x);//创建新节点
    //插入pos节点之后
    node->next = pos->next;
    pos->next = node;
}


9. 删除指定节点数据

void SLTErase(SLTNode** pphead, SLTNode* pos) {
    assert(pphead);
    assert(pos);//检测pos节点不为空，如果pos节点不为空，那么该链表也不为空
    //如果pos==头节点
    if (*pphead == pos) {
        //        SLTNode *del = *pphead;
        //        *pphead = (*pphead)->next;
        //        free(del);
        //        del = NULL;
        SLTPopFront(pphead);//头删
        return;
    }
    //找pos的前一个节点
    SLTNode* prev = *pphead;
    while (prev->next) {
        if (prev->next == pos) {
            break;
        }
        prev = prev->next;
    }
    prev->next = pos->next;//删除pos节点
    free(pos);//释放pos节点
    //    pos = NULL;//没有存在的必要
}


10. 删除指定节点之后的数据

void SLTEraseAfter(SLTNode* pos) {
    assert(pos);
    assert(pos->next);
    //删除pos之后的节点
    SLTNode* del = pos->next;
    pos->next = del->next;
    free(del);//释放该节点
    del = NULL;
}


11. 销毁单链表

void SListDesTroy(SLTNode** pphead) {
    SLTNode* pointer = NULL;
    while (*pphead) {
        pointer = *pphead;
        *pphead = (*pphead)->next;
        free(pointer);
        pointer = NULL;
    }
}

4. 完整代码

1. SList.h


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType val;
	struct SListNode* next;
}SLTNode;

//打印链表
void SLTPrint(SLTNode* phead);

//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

2. SList.c


#include "SList.h"
//创建节点
SLTNode* BuyNode(SLTDataType x) {
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    //如果创建失败
    if (node == NULL) {
        perror("malloc fail!\n");
        exit(1);
    }
    node->data = x;
    node->next = NULL;
    return node;//返回该节点
}
//打印链表
void SLTPrint(SLTNode* phead) {
    SLTNode* cur = phead;
    while (cur) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
    assert(pphead);//pphead不为空
    SLTNode* node = BuyNode(x);//创建新节点
    //如果链表为空
    if (*pphead == NULL) {
        *pphead = node;//新节点为头节点
        return;
    }
    //找尾
    SLTNode* cur = *pphead;
    while (cur->next) {
        cur = cur->next;
    }
    cur->next = node;//将新节点进行尾插
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* node = BuyNode(x);//创建新节点
    node->next = *pphead;//头插
    *pphead = node;//将头插进来的节点作为头节点
}
//尾删
void SLTPopBack(SLTNode** pphead) {
    assert(pphead);
    assert(*pphead);//链表不为空
    //如果链表只有一个节点
    if ((*pphead)->next == NULL) {
        free(*pphead);//释放头节点
        *pphead = NULL;//将头节点位置置为空
        return;
    }
    //找尾
//    SLTNode *cur = *pphead;
//    SLTNode *prev = NULL;
//    while(cur->next){
//        prev = cur;
//        cur = cur->next;
//    }
//    prev->next = NULL;
//    free(cur);
//    cur = NULL;
    SLTNode* tail = *pphead;
    //寻找尾节点的前一个节点
    while (tail->next->next) {
        tail = tail->next;
    }
    free(tail->next);//释放尾节点
    tail->next = NULL;
}
//头删
void SLTPopFront(SLTNode** pphead) {
    assert(pphead);
    assert(*pphead);//链表不为空
    SLTNode* first = *pphead;
    *pphead = (*pphead)->next;//头删
    free(first);//释放头节点
    first = NULL;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
    assert(phead);
    SLTNode* cur = phead;
    while (cur) {
        //如果找到该节点，返回该节点
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;//否则返回空
}
/*
 * 在pos之前插入
 */
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead);
    assert(pos);//检测pos节点不为空，如果pos节点不为空，那么该链表也不为空
    SLTNode* node = BuyNode(x);
    //如果pos==头节点
    if (*pphead == pos) {
        //        node->next = pos;
        //        *pphead = node;
        SLTPushFront(pphead, x);//头插
        return;
    }
    //找pos的前一个节点
    SLTNode* prev = *pphead;
    while (prev->next) {
        if (prev->next == pos) {
            break;
        }
        prev = prev->next;
    }
    //插入pos节点之前
    node->next = pos;
    prev->next = node;
}
/*
 * 删除pos
 */
void SLTErase(SLTNode** pphead, SLTNode* pos) {
    assert(pphead);
    assert(pos);//检测pos节点不为空，如果pos节点不为空，那么该链表也不为空
    //如果pos==头节点
    if (*pphead == pos) {
        //        SLTNode *del = *pphead;
        //        *pphead = (*pphead)->next;
        //        free(del);
        //        del = NULL;
        SLTPopFront(pphead);//头删
        return;
    }
    //找pos的前一个节点
    SLTNode* prev = *pphead;
    while (prev->next) {
        if (prev->next == pos) {
            break;
        }
        prev = prev->next;
    }
    prev->next = pos->next;//删除pos节点
    free(pos);//释放pos节点
    //    pos = NULL;//没有存在的必要
}
//插入pos节点之后
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
    assert(pos);
    SLTNode* node = BuyNode(x);//创建新节点
    //插入pos节点之后
    node->next = pos->next;
    pos->next = node;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
    assert(pos);
    assert(pos->next);
    //删除pos之后的节点
    SLTNode* del = pos->next;
    pos->next = del->next;
    free(del);//释放该节点
    del = NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead) {
    SLTNode* pointer = NULL;
    while (*pphead) {
        pointer = *pphead;
        *pphead = (*pphead)->next;
        free(pointer);
        pointer = NULL;
    }
}

3. text.c

#include "SList.h"
void Relization(void) {
	SLTNode* phead = NULL;
	SLTPushBack(&phead, 5);
	SLTPushBack(&phead, 2);
	SLTPushFront(&phead, 3);
	SLTPushFront(&phead, 4);
	SLTPopBack(&phead);
	SLTPopFront(&phead);
	SLTNode* node = SLTFind(phead, 3);
	if(node) {
		printf("找到了\n");
	}
	else {
		printf("没找到\n");
	}
	SLTInsert(&phead, phead->next, 7);
	SLTInsertAfter(phead->next, 6);
	SLTErase(&phead, NULL);
	SLTEraseAfter(phead->next->next->next);
	SLTPrint(phead);
	SListDesTroy(&phead);
	SLTPrint(phead);
}
int main() {
	Relization();
	return 0;
}

# 数据结构
Logo
DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

cover

机器人的工作学习：部署期间的人机交互自主性和学习

avatar DAMO开发者矩阵
cover

不确定性是免费的：基于扩散模型的人机交互策略

avatar DAMO开发者矩阵

5G时代下边缘AI推理的机遇与挑战

随着短视频、自动驾驶、工业机器人等“实时交互型”应用爆发，传统“云端计算+4G传输”模式逐渐力不从心——4G的10ms延迟（从手机到云端再返回）会让自动驾驶“急刹车慢半拍”，云端集中计算的带宽压力更像“千军万马过独木桥”。本文将聚焦“5G+边缘AI推理”这一技术组合，从技术原理、实战案例到未来挑战，全面解析其如何解决“实时性、隐私性、带宽压力”三大痛点。本文将按照“概念解释→原理拆解→实战案例→应

avatar DAMO开发者矩阵