今天要分享的是数据结构中的链表。对于新手来说，链表确实不好学，也确实难,下面是一些链表知识点的总结，请听我一 一道来：
分享之前，和大家分享一下今天阅读的时候读到伟大诗人说的一句话：
诗人辛波斯卡说：一个人可以爬上山丘，屏住呼吸，却无法像玫瑰一样生出枝叶，长成树丛，因为“只有玫瑰才能盛开如玫瑰”。同样，每个人都只能按自己的方式绽放人生。
---共勉
链表？链表是什么？我也不晓得啊，所以我去百度搜了一下结果如下：
链表 (linked list)：是一种物理存储结构上非连续 存储结构 ，数据元素的逻辑顺序是通过链表中的引用链接次序实现的. 链表由一系列 结点 （ 链表中每一个元素称为结点 ）组成，结点可以在运行时动态生成。
说实话我刚开始学我也看不懂：下面给出比较容易理解的方式：
链表就是由一系列节点，用箭头把这些节点给连接起来，如下图：
先来讲一下数组的顺序存储和链表的链式存储，加以区别，更好的理解链表：
数组—顺序存储
数组作为一个顺序储存方式(数组中的每一个元素的地址都是连续的，比如1234，这一串数字就是连续的)的数据结构，可是有大作为的，它的灵活使用为我们的程序设计带来了大量的便利；
但是，数组最大的缺点就是我们的插入和删除时需要移动大量的元素，所以呢，大量的消耗时间，以及冗余度使得我们难以接受。
以C语言数组插入一个元素为例，当我们需要在一个数组{1,2,3,4}的第1个元素后的位置插入一个’A’时，我们需要做的有：
第一步：将第1个元素后的整体元素后移，形成新的数组{1,2,2,3,4}。
第二步：再将第2个元素位置的元素替换为我们所需要的元素'A'。
第三步：最终形成我们的预期，这需要很多重复操作。
上图可以看出，使用数组都有这两大缺点：
1.插入删除操作所需要移动的元素很多，浪费算力。
2.必须为数组开足够的空间，否则有溢出风险
链表—链式存储
由于数组的这些缺点，自然而然的就产生链表的思想了。
链表通过不连续的储存方式，自适应内存大小，以及指针的灵活使用，巧妙的简化了上述的内容。
链表的基本思维是，利用结构体的设置，额外开辟出一份内存空间去作指针，它总是指向下一个结点，一个个结点通过NEXT指针相互串联，就形成了链表。
其中DATA为自定义的数据类型，NEXT为指向下一个链表结点的指针，通过访问NEXT，可以引导我们去访问链表的下一个结点。
对于一连串的结点而言，就形成了链表如下图：
上文所说的插入删除操作只需要修改指针所指向的区域就可以了，不需要进行大量的数据移动操作。如下图：
相比起数组，链表解决了数组不方便移动，插入，删除元素的弊端，但相应的，链表付出了更加大的内存牺牲换来的这些功能的实现。
一.链表概述：
包含单链表，双链表，循环单链表，实际应用中的功能不同，但实现方式都差不多。
单链表就像接力棒，一个一个往下传；
双链表就像传球一样，你传球给我，我传球给你。
循环链表就像是一队人，从一号一个个传到尾号然后尾号再传给一号，形成一个循环。
我们今天只介绍一下单链表，这个懂了，其他就容易理解了：
1.单链表概念和简单的设计：
单链表是一种链式存取的数据结构，链表中的数据是以结点来表示的，每个结点由元素和指针构成。
元素表示数据元素的映象，就是存储数据的存储单元；指针指示出后继元素存储位置，就是连接每个结点的地址数据。
以结点的序列表示的线性表称作线性链表，也就是单链表，单链表是链式存取的结构。
对于链表的每一个结点，我们使用结构体进行设计，其主要内容有：
其中，DATA数据元素，可以为你想要储存的任何数据格式，可以是数组，可以是int，甚至可以是结构体（这就是传说中的结构体套结构体）
NEXT为一个指针，其代表了一个可以指向的区域，通常是用来指向下一个结点，链表的尾部NEXT指向NULL（空），因为尾部没有任何可以指向的空间了。
故，对于一个单链表的结点定义，可以代码描述成：
typedef struct Node { int data; //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型 struct Node* next; //单链表的指针域 } Node, * LinkedList; //Node表示结点的类型，LinkedList表示指向Node结点类型的指针类型
2.链表的初始化：
初始化主要完成以下工作：
- 创建一个单链表的动态前置节点并向后逐步添加节点，一般指的是申请结点的空间，（注意这里动态分配就是为了区分数组和链表的存储方式，在定义数组时，操作系统会提前一次性分配给一块足够用户使用的内存，这块内存是连续的，然而链表是不需要这样做的，链表所占用的内存是不需要提前分配的，链表可根据自身情况进行分配。）
- 对头结点的指针域赋空值(NULL)，因为不给指针赋值可能会造成野指针等不可预测的危害。
其代码可以表示为：
LinkedList listinit() { Node *L; L=(Node*)malloc(sizeof(Node)); //开辟空间 if(L==NULL) { //判断是否开辟空间失败，这一步很有必要 printf("申请空间失败"); //exit(0); //开辟空间失败可以考虑直接结束程序 } L->next=NULL; //指针指向空 }
注意：一定要判断是否开辟空间失败，否则生产中由于未知的情况造成空间开辟失败，仍然在继续执行代码，后果将不堪设想啦，因此养成这样的判断是很有必要的。
下面创建链表的两种方式很重要，值得大家反复琢磨：
3.头插法创建单链表：
利用指针指向下一个结点元素的方式进行逐个创建，使用头插法最终得到的结果是逆序的。
如图所示：
从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
代码实现如下：
//头插法建立单链表 LinkedList LinkedListCreatH() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 int x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF) { Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->NULL L->next = p; } return L; }
4.尾插法创建单链表：
如图所示为尾插法的创建过程。
头插法生成的链表中，结点的次序和输入数据的顺序不一致。若希望两者次序一致，则需要尾插法。
该方法是将新结点逐个插入到当前链表的表尾上，为此必须增加一个尾指针tail, 使其始终指向当前链表的尾结点，代码如下：
//尾插法建立单链表 LinkedList LinkedListCreatT() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 Node *tail; tail = L; //tail始终指向终端结点，开始时指向头结点 int x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF) { Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 tail->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL tail = p; } tail->next = NULL; return L; }
5.遍历/打印/修改单链表：
遍历的定义：从链表的头开始，逐步向后进行每一个元素的访问，称为遍历。
对于遍历操作，我们可以衍生出很多常用的数据操作，比如增加元素，删除元素，修改元素个数，查询整个链表数据（俗称增删改查）等等操作。
进行遍历的思路不难，只需要建立一个指向链表L的结点，然后沿着链表L逐个向后搜索即可，代码如下：
//遍历输出单链表 void printList(LinkedList L） { Node *p=L->next; int i=0; while(p) { printf("第%d个元素的值为:%d\n",++i,p->data); p=p->next; } }
对于元素修改操作，以下是代码实现：
//链表内容的修改，在链表中修改值为x的元素变为为y。 LinkedList LinkedListReplace(LinkedList L,int x,int y) { Node *p=L->next; int i=0; while(p) { if(p->data==x) { p->data=y; } p=p->next; } return L; }
注意：简单的遍历设计的函数只需要void无参即可，而当涉及到元素操作时，可以设计一个LinkedList类型的函数，使其返回一个操作后的新链表。
6.元素插入操作：
链表的插入操作主要分为查找到第i个位置，将该位置的next指针修改为指向我们新插入的结点，而新插入的结点next指针指向我们i+1个位置的结点。
其操作方式可以设置一个前驱结点，利用循环找到第i个位置，再进行插入。
如图，在DATA1和DATA2数据结点之中插入一个NEW_DATA数据结点：
从原来的链表状态：
插入后链表的状态：
代码实现如下：
//单链表的插入，在链表的第i个位置插入x的元素 LinkedList LinkedListInsert(LinkedList L,int i,int x) { Node *pre; //pre为前驱结点 pre = L; int tempi = 0; for (tempi = 1; tempi < i; tempi++) { pre = pre->next; //查找第i个位置的前驱结点 } Node *p; //插入的结点为p p = (Node *)malloc(sizeof(Node)); p->data = x; p->next = pre->next; pre->next = p; return L; }
7.元素删除操作
删除元素要建立一个前驱结点和一个当前结点，当找到了我们需要删除的数据时，直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点，再将原有的结点通过free函数释放掉。如图所示：
代码如下：
//单链表的删除，在链表中删除值为x的元素 LinkedList LinkedListDelete(LinkedList L,int x) { Node *p,*pre; //pre为前驱结点，p为查找的结点。 p = L->next; while(p->data != x) //查找值为x的元素 { pre = p; p = p->next; } pre->next = p->next; //删除操作，将其前驱next指向其后继。 free(p); return L; }
二.总结：
链表确实不好理解，准确来说数据结构这门课都很难很抽象很不好理解，但它非常重要。
建议学习链表之前先复习一下指针，结构体，数组，深入理解一下指针，结构体。
本人虽然可以基本上实现这些基本操作，但是自身还是有很多不足之处，有些东西似懂非懂，仍然需要不断学习，以上如有错误请指教，谢谢各位。
借用《钢铁是怎样炼成的》扉页中的一句话分享给大家：一个人的人生应该这样度过，当你回首往事的时候，不因碌碌无为而悔恨，不因虚度年华而羞耻。
14:00写到现在，再次抬头天已经快暗了：寒假目标励志学完数据结构，加油加油加油！！！
2023.01.07
From：努力进大厂的新青年
