前言：

  上一次简单的介绍了链表的概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。这个章节我主要梳理一下 无头单向非循环链表，因为这个链表考察最多。也最需要逻辑清晰。

目录

1.无头单向非循环链表

2.单链表实现增删查改

2.1打印函数实现

2.2尾插函数实现

 2.3头插函数实现

2.4尾删函数的实现 

2.5 头删函数实现 

2.6 查找函数 

2.7插入函数

 2.8 擦除函数

2.9销毁函数

 2.10后插函数

2.11后删函数

1.无头单向非循环链表

 无头单向非循环链表 一般格式如下图所示：

  一般逻辑结构如下图所示，变量plist里面存第一个节点的地址，第一个节点的next存第二个节点的地址，依次往后，知道结束最后一个节点的next指向空NULL。

   链式结构在逻辑上是连续的，但是在物理上不一定连续，节点一般都是从堆上申请，所以两次申请的空间可能连续，也可能不连续；

  每个节点，都封装了 自身数据以及下一个节点的地址，所以节点一般都是由结构体实现，结构体的形式如下所示：

typedef struct SList
{SLDataType data;SList* next;}SL;

 上面的代码对吗？答案是错的，因为 只有struct SList 才是结构体类型。

typedef struct SList
{SLDataType data;SL* next;}SL;

上面的代码对吗？答案也是错的，因为 类型重定义是将整体 重定义为SL,当还未完成时，就用重定义之后的名字是不合法 ，当编译时候，系统想找SL,需要向上寻找，但没有声明定义，所以肯定通过不了。

正确的定义结构如下所示：

typedef int SLDataType;typedef struct SList
{SLDataType data;struct SList* next;}SL;

2.单链表实现增删查改

2.1打印函数实现

我们从最简单的打印函数深入剖析 链表这碗牛肉汤,图解分析如下：

需要先定义一个结构体指针变量cur 用来遍历 整个链表的节点，首先将指向第一个节点的头指针变量的值赋值给cur只要cur不为空，就将结构体成员data打印出来 然后 将cur->next 赋值给cur继续遍历，直到cur为空指针 跳出循环。代码如下:

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

 思考两个问题，第一个问题，如果将cur改成 cur++ 可以吗 为什么? 答案是不行，我们知道 每个节点都是从堆上申请的，所以 地址不一定连续，指针++不一定能够访问到下一个节点；

第二个问题，在顺序表中我们写打印函数的时候，加了个断言，在单链表中我们需要加断言吗，为什么？其实，因为顺序表定义的数据 并不是直接存在结构体，二是通过结构体成员访问数据，而且，数据个数是否为零，也是有变量size决定，设计到解引用访问结构体成员，所以需要断言一下，如下图示：

但是链表，他的数据是存在结构体中的，只需要变量指针访问就行 ，没有解引用的操作，所以即使为NULL,也没事，所以不需要断言。

2.2尾插函数实现

先看如下代码：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{//定义一个新的节点 用于尾插SLTNode* newcode = (SLTNode*)malloc(sizeof(SLTNode));if (newcode == NULL){perror("malloc:faild");return;}newcode->data = x;newcode->next = NULL;if (phead == NULL){phead = newcode;}else{//找尾SLTNode* tail = phead;while (tail){tail = tail->next;}tail = newcode;}}

 定义一个结构体指针tail用来遍历寻找NULL ，当指向空时候，跳出循环，然后将newcode地址赋值给tail，然后将newcode->next指向空，如果phead为空直接将phead指向newcode就行，图解如下：

 执行代码：

void TestSList1()
{SLTNode* phead = NULL;SLTPushBack(phead, 1);SLTPushBack(phead, 2);SLTPushBack(phead, 3);SLTPushBack(phead, 4);SLTPrint(phead);}

 为什么会产生这个结果呢，我们仔细想一下，链表的含义是要保证他们能链接上，最后的tail指针变量里面真的存了newcode的地址了吗，tail可是局部变量啊，出了作用域就会被销毁啊，就像我们之前学的，形参是实参的一份临时拷贝，如果我们想改变形参就要传址，想改变整形的值，就要传 int * 同样的想改变，int*就要传int ** 我们要想概念结构体指针变量就要传 二级指针，

实际上我们应该接收 指针变量的地址，才能改变指针变量，如下图所示：

修改后，代码如下：

void TestSList2()
{SLTNode* phead = NULL;SLTPushBack(&phead, 1);SLTPushBack(&phead, 2);SLTPushBack(&phead, 3);SLTPushBack(&phead, 4);SLTPrint(phead);}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//定义一个新的节点 用于尾插SLTNode* newcode = (SLTNode*)malloc(sizeof(SLTNode));if (newcode == NULL){perror("malloc:faild");return;}	newcode->data = x;newcode->next = NULL;if (*pphead == NULL){*pphead = newcode;}else{//找尾SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newcode;}
}

 2.3头插函数实现

  在链表的头部插入节点，当链表不为空时候，只需要将新增节点的next指向 第一个节点，然后将头指针指向新增节点即可，如果链表为空的话，上述操作仍然可行，具体分析如下图所示:

代码如下：

void TestSList2()
{SLTNode* phead = NULL;SLTPushFront(&phead, 1);SLTPushFront(&phead, 2);SLTPushFront(&phead, 3);SLTPushFront(&phead, 4);SLTPrint(phead);
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newcode = BuyListNode(x);newcode->next = *pphead;*pphead = newcode;}

 执行结果如下：

2.4尾删函数的实现 

如果定义一个新的结构体指针tail，用来找尾，当tail->next 为空时候，free这个节点 并将这个节点置空，这样的代码可行吗？图示和代码如下：

//尾删
void SLTPopBack(SLTNode** pphead)
{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}free(tail);tail = NULL;}

我们运行一下这个代码：

我们发现，尾删的时候好像并没有将尾节点置空，但是我的代码中明明已经将tail释放并置空了啊，为什么还会这样呢？我们仔细分析一下，tail只是定义的临时变量，程序结束，tail就会被销毁，我们想要改变结构体的成员next，free（tail）并将tail置空，并不能改变结构体成员的指向链接到NULL,所以我们还需要定义一个结构体指针变量pre，用来记录置空节点的上一个节点，并用该节点访问next并修改，图解分析如下：

具体代码如下：

//尾删
void SLTPopBack(SLTNode** pphead)
{SLTNode* tail = *pphead;SLTNode* pre = tail;while (tail->next != NULL){pre = tail;tail = tail->next;}free(tail);pre->next = NULL;}

 执行结果如下：

我们继续 执行试试

发现当省一个节点的时候，我们删的话就会出问题，我们走读代码的时候发现，当有一个节点时候，不会进入循环，pre还为空呢，还要执行pre->next为空，这一步肯定要出问题的，所以我们需要将链表为空，以及只有一个节点的问题解决，为空我们可以断言解决，一个节点的话 我们就free一下 并将plist置空，具体代码如下：

//尾删
void SLTPopBack(SLTNode** pphead)
{assert(*pphead != NULL);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* pre = NULL;while (tail->next != NULL){pre = tail;tail = tail->next;}free(tail);tail = NULL;pre->next = NULL;}
}

执行结果如下：

2.5 头删函数实现 

头删实现的时候就会容易很多，只要定义一个指向第一个节点的指针first，然后将该节点的next赋值给plist 然后销毁first就行啦，图解如下：

具体代码如下：

//头删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}

 执行结果如下：

2.6 查找函数 

  在链表中查找想要的的数值 并返回下标，这个应该很好写，就是遍历 找到就返回下标，代码如下所示：

//发现需要寻找的数据，并将该位置的下标返回
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* pos = phead;while (pos){if (pos->data == x){return pos;}else{pos = pos->next;}}return NULL;}

其实查找函数写完，修改函数也就跟着出来了，当我们找到该位置，修改该位置的内部数据就行，具体代码如下：

void TestSList5()
{SLTNode* phead = NULL;SLTPushFront(&phead, 1);SLTPushFront(&phead, 2);SLTPushFront(&phead, 3);SLTPushFront(&phead, 2);SLTPushFront(&phead, 4);SLTPushFront(&phead, 2);SLTNode* pos = SListFind(phead, 2);if (pos){//pos->data = 50;}SLTPrint(phead);}

2.7插入函数

插入函数，是在给定下标之前插入想要的数据，所以我们还需要定义一个结构体指针用来找到pos之间的位置，然后就是插入，如果是在第一个位置那就是头插，具体代码如下：

//插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{SLTNode* newcode = BuyListNode(x);//如果是在头部插入if (*pphead == pos){newcode->next = *pphead;*pphead = newcode;}SLTNode* prepos = *pphead;if (prepos->next != pos){prepos = prepos->next;}else{prepos->next = newcode;newcode->next = pos;}
}

 2.8 擦除函数

类似于尾删，头删 只不过这个擦除包括链表中间的任意位置，只需要加入遍历部分，查找到pos之前的位置，然后进行修改，具体代码如下：

void SListErase(SLTNode** pphead, SLTNode* pos)
{if (*pphead == pos){*pphead = pos->next;free(pos);pos = NULL;}SLTNode* prepos = *pphead;if (prepos->next != pos){prepos = prepos->next;}else{prepos->next = pos->next;free(pos);pos = NULL;}}

2.9销毁函数

往后遍历，将前一个节点销毁置空就行，直到遍历到空指针，代码如下：

void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* tail = *pphead;while (tail){SLTNode* next = tail->next;free(tail);tail = next;}}

 2.10后插函数

 比插入函数简单，只需要在pos位置之后插入函数就行 代码如下：

void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* tail = *pphead;while (tail){SLTNode* next = tail->next;free(tail);tail = next;}}

2.11后删函数

 只需要将pos位置之后的节点删除，将pos指向 pos之后的第二个节点就行；为防止pos是最后一个节点的情况需要断言一下

void SListEraseAfter(SLTNode* pos)
{assert(pos->next);SLTNode* next = pos->next;pos->next = next->next;free(next);
}