[数据结构]好好思考一下吧，单链表真的那么难写吗？

一个目录

故事还在继续，菜鸡大学生写完顺序表，感觉十分良好，萌生了把数据结构都撸一遍的想法。他自信满满的翻到后面的高阶数据结构，然后合上了，做出了一个伟大的决定：还是先挑软的欺负。
于是，今天的受害者就是单链表。

链表

什么是链表？

链表，是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接顺序实现的。

（链表的娇容）

好，我们已经解决了什么是，下面来解决为什么要有链表的问题，是顺序表不香了吗？
香，特香，嘎嘎香。

但是，顺序表存在几个小问题：

1. 头插/指定位置删除，时间复杂度为**O(N)**。
2. 增容需要申请新的空间，假如遇到极端情况，一个顺序表的空间特别大，这样拷贝数据释放空间，会存在不小的消耗。
3. 我们之前选择的是2被增容，如果我们需要的空间比较小，势必会存在不小的空间浪费。

所以我们需要一种新的数据结构，来解决以上问题。
于是，链表就出生了。
注：

1. 由图可知，链式结构在逻辑上是连续的，但在物理上不一定连续。
2. 链表的结点一般都是从堆上申请。
3. 从堆上申请的空间可能连续，可能不连续。

链表的分类

• 单向或者双向
• 带头或者不带头
• 循环或者非循环

以上几种情况进行一个排列组合就可以有8种链表结构。

今天我们要写的是单向不带头非循环链表。
无奖竞猜：下一篇写什么？

目标

• 一个单向不带头非循环链表
• 实现基本的增删查改等接口函数

开工！

一点简单的准备工作

单链表的本体

typedefint SLTDataType;typedefstruct SListNode
{
    SLTDataType data;struct SListNode* next;}SListNode;

与此同时，主函数：

intmain(){
    SListNode* plist =NULL;return0;}

单链表的打印

//单链表打印voidSListPrint(SListNode* phead){assert(phead);
    SListNode* cur = phead;while(cur !=NULL){printf("%d->", cur->data);
        cur = cur->next;}printf("NULL\n");}

遍历整个链表，打印当前节点的值，指针指向下一个节点，直到节点为空，打印结束。

不难，很好理解。

动态申请一个节点

//动态申请一个节点
SListNode*BuySListNode(SLTDataType x){
    SListNode* newnode =(SListNode*)malloc(sizeof(SListNode));
    newnode->data = x;
    newnode->next =NULL;return newnode;}

申请一个节点，给数据赋值，指针初始化为空。

是不是很简单？下面我们来看增删查改：

增删查改等接口函数

尾插

由于尾插相对比较容易所以我们先讲尾插。

voidSListPushBack(SListNode** pphead, SLTDataType x){
    SListNode* newnode =BuySListNode(x);if(*pphead==NULL){*pphead= newnode;}else{
        SListNode* tail =*pphead;while(tail->next !=NULL){
            tail = tail->next;}
        tail->next = newnode;}}

传二级指针的原因：函数传递的是形参，形参的改变不影响实参。 老问题了。

链表比顺序表稍微复杂一点的地方就是链表需要考虑的情况比顺序表多， 但是不用担心，我会慢慢画图分析的。
什么是极端情况？就是端点的情况。
所以我们在写链表的时候，需要考虑一下这种写法适不适合端点，如果不适合，需要特殊考虑。

比如我们现在的尾插：
注：为了方便理解我们都是从一般到特殊去分析。

• 一般情况：
• 特殊情况：链表为空，不存在tail->next，直接插入就好。

头插

voidSListPushFront(SListNode** pphead, SLTDataType x){
    SListNode* newnode =BuySListNode(x);
    newnode->next =*pphead;*pphead = newnode;}

按图所示的方法链接即可。

这时可能有人会问了，链表为空怎么办？
我们不妨分析一下：如果链表为空，pphead指向NULL，newnode->next= *pphead;然后newnode指向空，pphead指向newnode。是没有问题的。

头删

voidSListPopFront(SListNode** pphead){if(*pphead ==NULL){printf("链表已空!\n");return;}
    SListNode* tmp =*pphead;*pphead =(*pphead)->next;free(tmp);}

先用tmp接收头节点，然后pphead向后移动一步，释放tmp即可。
注意点就是防止链表为空。

尾删

voidSListPopBack(SListNode** pphead){if(*pphead ==NULL){printf("链表已空!\n");return;}elseif((*pphead)->next ==NULL){free(*pphead);*pphead =NULL;}else{
        SListNode* tail =*pphead;
        SListNode* prev =NULL;while(tail->next !=NULL){
            prev = tail;
            tail = tail->next;}free(tail);
        prev->next =NULL;}}

尾删应该是比较复杂的了，我们慢慢分析：

• 先写出大概逻辑：先找尾节点和尾节点前一个节点，尾节点删掉，尾节点前一个节点指向空。
• 考虑特殊情况： 1. 空链表：直接返回。2. 只有一个节点，直接删除，pphead置为空。

指定位置增删函数

查找指定位置

//链表的查找
SListNode*SListFind(SListNode* pphead, SLTDataType x){
    SListNode* pos = pphead;while(pos !=NULL){if(pos->data == x){return pos;}
        pos = pos->next;}returnNULL;}

遍历，找到返回地址，没找到返回NULL。
遍历什么最棒了。

在指定位置之前插入数据

//单链表在pos位置之前插入xvoidSListInsert(SListNode** pphead, SListNode* pos, SLTDataType x){if(pos ==*pphead){SListPushFront(pphead, x);return;}else{
        SListNode* newnode =BuySListNode(x);
        SListNode* cur =*pphead;while(cur->next != pos){
            cur = cur->next;}
        newnode->next = pos;
        cur->next = newnode;}}

在第一个节点之前插入就是头插。
其余位置大概逻辑见下图：

在指定位置删除数据

//单链表删除pos位置的值voidSListErase(SListNode** pphead, SListNode* pos){if(pos ==*pphead){SListPopFront(pphead);return;}else{
    SListNode* cur =*pphead;while(cur->next != pos){
        cur = cur->next;}
    cur->next = pos->next;free(pos);}}

第一个位置就是头删，直接上函数。
其余位置直接上就行。

注：删除和增加函数都使用cur接收pos前的位置，在写代码的时候就不需要考虑断开的顺序了，写起来很方便，所以就不考虑放动图了。

最后

• 单链表适合头插头删，其余位置需要遍历，不太划算。
• 还是画图重要。

小广告：好哥哥们，最近整了个非科班转码社区，欢迎来玩啊！