前言：
上一次我们分享了线性表中的一种结构顺序表，它存在着一些其缺点，比如：在中间位置或者头部进行元素插入或者删除的时候时间复杂度是 O ( N ) O(N)O(N)效率比较低，并且顺序表在扩容的时候也存在时间和空间上的消耗，由于我们每次都是按照二倍来扩的，那就很有可能会出现扩大了用不完导致空间浪费的现象。这些问题该如何解决呢？那就需要用到今天分享给大家的另一种线性结构 链表。
一、什么是链表？
1.1 定义
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
简单来理解就是，链表中的每一个数据元素都是独立存储的，当需要存储一个数据元素的时候就去向内存空间申请一块内存用来存储当前数据，每一个数据元素又通过地址串联在一起，因此对于链表这个结构来说，不仅需要存储当前的数据元素，还需要存储下一个元素的地址，这样才能把数据元素串联在一起，通常我们把待存储的数据元素和下一个数据的地址合起来叫做链表中的一个节点，这个节点由两部分数据组成，因此可以定义一个结构体来创建节点。
图示：
1.2 链表的分类
链表会根据是否带头结点、是否是双向链表、是否是循环链表进行分类组合。因此链表一共有八种具体的实现形式。
其中头节点是在链表的第一个节点之前附设一个类型相同的节点，我们把这个节点就称之为头节点，当然头节点和普通的节点在形式上并没有什么不同，所以头节点也分数据区域和指针区域，头结点的数据区域建议什么东西也不存储，有些地方会在头结点的顺序区域存储链表的长度，其实这是欠妥的，因为链表的长度（也就是节点个数）一定是一个int型的整型变量，只有当链表存储的全是整型数据的时候，节点的数据域是整型，此时在头结点的数据域存储链表长度是可以的，但是当链表存储的是字符型或者其他用户自定义类型的时候，那节点的数据域就不是整型了，此时再在头结点的数据域存储链表长度显然是不行的。所以，为了使我们写出来的链表更加具有普适性，这里不建议大家在头结点的数据域存储链表长度。头结点的指针域存储的则是链表中第一个节点的地址。关于链表的优点这里先留一个悬念，相信随着学习的深入小伙伴们自然就能体会到头结点的优势。
这里大家需要注意区分头节点和头指针，他俩是两回事。
头节点是一个节点，本质上是一个结构体变量，区分数据域和指针域
头指针是一个指针，本质上是一个结构体类型的指针变量，不区分数据域和指针域，它仅存储链表中第一个节点的地址。
双向链表，即一个节点中有两个指针域，一个存放当前节点前一个节点的地址，另一个存放当前节点后一个节点的地址。随着学习的深入我们就会发现双向链表的优势，这里就不过多赘述。
循环链表，即链表的最后一个节点的指针域存的是第一个节点的地址，这样一来整个链表就形成了一个环达到了循环的效果。
至此，链表的分类就给大家介绍完了，虽然根据链表的不同分类标准可以组合出八种不同结构的链表，但我们只要掌握了无头单向非循环和带头双向循环这两种结构，剩下的六种便能轻松上手。所以下面我将详细的介绍一下这两种结构。
二、无头单向非循环链表
2.1 结构
typedef int SLTDataType; typedef struct SListNode { SLTDataType data;//数据域 struct SListNode* next;//指针域 }SLTNode
无头单向非循环链表的结构就只需要数据域和一个指针域。数据域的类型是待存储数据的类型，这里为了使链表更具有普适性，这里使用了typedef对类型重命名。指针域要存放的是下一个节点的地址，因此它的类型是一个结构体类型的指针，需要注意：结构体的类型是struct SListNode一定要写全，不能漏写，也不能用SLTNode来声明指针，因为在声明指针的时候还没有对结构体类型进行重命名。为了方便起见，对结构体类型进行重命名。
链表与顺序表在结构上的区别：
从图中可以看出，链表的每一个数据是直接存储在一个结构体变量中，多个结构体变量共同组成一个链表，而顺序表则是在一个结构体变量的基础上，通过它的成员arr指向动态申请的空间，顺序表中的数据并没有直接存储在结构体变量中，而是存储在动态申请的开空间里，一个顺序表只对应一个结构体变量。结构上的差异导致pList == NULL和ps == NULL所表达的含义是不同的，pList == NULL表示当前链表是一个空链表，当然空链表也是一个链表，只不过里面没有数据罢了，而ps == NULL则说明这个顺序表根本就不存在，这里注意：ps == NULL不表示一个空顺序表，ps->size == 0才表示一个空顺序表（前提是ps非空）。
2.2 如何遍历链表数据
在知道了什么是链表以及链表的结构之后，我们需要把链表利用起来，即完成对链表的增、删、查、改等工作。在进行这些工作之前，我们首先得知道如何去遍历链表访问链表中的每一个数据，然后才能去完成前面的工作。遍历过程如下代码所示：
void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
首先形参接收到的是链表中第一个节点的地址，要遍历链表当然要从第一个结点开始嘛，这一点相信大家很容易理解，接下来就是遍历了，遍历是通过一个指针去维护的，可以这么说对链表的所有操作都是用一个指针去维护的，通过改变指针的指向以达到访问不同节点的目的，因为链表是由多个节点共同组成的，说白了也就是多个结构体变量共同组成的，如果是值传递，那这个链表有多少个节点，我们就得在函数中再创建多少个节点来接收，这在造成空间浪费的同时也大大增加了我们处理问题的复杂度。在明确了用指针去遍历链表之后，接下来就该让这个指针动起来。cur = cur->next;这条语句就实现了让指针动起来，把cur指向的节点的指针域中存的地址赋值给cur自己，而cur指向的节点的指针域存放的就是下一个节点的地址。直到cur == NULL的时候说明已经遍历完了整个链表。需要注意遍历结束的条件不能是：cur->next != NULL，因为cur->next == NULL说明cur指向最后一个节点，并没有遍历结束。下面给出遍历过程的物理示意图和逻辑示意图。
物理结构示意图：
逻辑结构示意图：
2.3 尾插
尾插的第一步当然是先创建一个节点（也就是结构体类型的变量）来存储数据，注意尾插我们是通过函数来实现的，因此在创建新节点的时候不能用SLTNode newnode来创建节点，因为这样创建的节点是一个局部变量，函数结束局部变量就销毁了，通常情况下是通过malloc去堆上申请一块空间来存储数据。节点创建好后，就要想办法把此节点链接到原链表的最后，因此接下来要先找到原链表的最后一个节点，然后让最后一个节点的指针域存放新创建节点的地址，这样就实现了链接，下面还是通过逻辑结构示意图和物理结构示意图演示一下尾插的过程：
逻辑结构示意图：
物理结构示意图：
尾插还有一种情况需要注意，那就是当链表为空的时候。上面提到过一个链表为空，意味着链表只有一个节点，并且该节点的地址是0x00000000。首先第一步还是创建节点把要尾插的数据先存储起来，然后呢？把这个节点链接到这个地址是0x00000000的节点后面嘛？答案是不行的因为0x00000000所在的地址空间是不允许我们随意访问的，它属于操作系统严格管控的区域，这就意味着我们无法去访问到这块空间的指针域然后把新节点的地址存进去。
对于空链表尾插的正确做法是，直接将新创建的节点当作头节点。这就意味着：需要把头指针中存放的地址修改成新创建节点的地址！，要记得尾插的所有操作都是封装成函数来实现的，对于函数来说形参的改变不会影响实参，而这里需要修改一个指针变量里面存放的地址，并且希望在函数里面修改之后，在函数外面依然生效，因此这里我们需要进行址传递，也就是传递头指针的地址，地址的地址那形参自然就需要用一个二级指针来接收，这里记作pphead。注意：这个二级指针不能为空，因为他存的是指向头节点指针的地址，如果为空那就说明没有这个指向头结点的指针，那就说明链表不存在，要区分链表不存在和空链表各自是如何表示的。
空链表：头指针为空，也就是pList == NULL表示的是一个空链表，有些操作时允许空链表的情况的，比如说遍历、尾插、头插数据，而有些情况则不允许出现空链表的情况，比如说头删、尾删数据。因此我们需要根据具体的情况去做检查。
链表不存在：pphead ==NULL则是说明链表不存在，对链表的操作，链表不存在当然是不被允许的，所以只要使用了pphead就要对他进行检查。
代码实现：
void SLTPushBack(SLTNode** pphead,SLTDataType x) { assert(pphead);//pphead不能为空，pphead为空说明里面没有存指向头节点指针的地址，那就说明没有链表 SLTNode* newnode = BuySLTNode(x);//由于在头插和随机插入的过程中也会涉及到节点的创建，所以这里把节点的创建单独封装了一个函数 if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* cur = *pphead; while (cur->next != NULL)//假如链表为空这里就非法访问了，因此要先判断 { cur = cur->next; } cur->next = newnode; } }
