一些关于单链表的操作

思维导图：

一， 链表

1.1节点的结构

链表是啥样的啊？顾名思义链表就是一种用链子链接起来的表。那这种表是怎么样的啊？

这样的呗：

现在，我们知道了链表的形状了。那我们该如何用编程语言来形成这一种形状呢？

首先，一个链表节点是这样的:

毫无疑问，链表也需要存储一些数据（不然要链表来干嘛？)。而且链表还有一条尾巴（当然这是为了形象而画出来的）这条尾巴又要如何形成呢？现在让我们来想一想尾巴的作用是什么啊？当然是为了找到下一个节点啊，那我们要找到下一个节点的话我们应该用什么去找呢？当然是下一个节点的地址啊！那放地址我们是不是应该要用指针啊？那好,现在我们已经清楚的知道了这一个节点的结构组成了。画图如下：

现在，我们再往下推。首先，我们这一个结构里面含有两种不同类型的数据。不同类型的数据应该用什么数据结构来存储呢？明显是结构体。那我的指针指向的下一个节点是不是又是一个结构体或者空指针呢？那这个指针是不是又可以定义为结构体指针呢？答案是肯定的！

经过以上分析，现在我们就可以把代码写出来了：

代码：

typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;//这里的typedef是为了在后面对这个结构体更好的使用

 1.2节点的生成

现在我们已经把节点的结构搞明白了，我们就要进入第二阶段了。我们要把上面的结构的节点生成一下。生成节点用什么啊？malloc啊！

生成节点代码：

SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//动态开辟空间if (newnode == NULL) {printf("malloc fail\n");return NULL;}newnode->data = x;//在数据区内放入数据newnode->next = NULL;//先置空指针区return newnode;//将新节点返回
}

1.3打印链表

打印链表该怎么做呢？

其实很简单，这样做就行了！

代码:

void SListPrint(SListNode* plist) {SListNode* cur = plist;while (cur) {printf("%d->", cur->data);cur = cur->next;}printf("->NULL\n");//当链表为空的时候就打印一个NULL来提示一下
}

1.4在链表中插入数据

         现在我们的链表的设计已经写好了，但是这个链表是一个空链表。现在我们就要来给这个链表插入数据。当然，插入数据的方法有很多种。像头插，尾插，中间插入等等……。现在我们就来一 一实现一下。

1.4.1：头插

头插的方法就是生成一个新的节点，然后让新的节点成为新的头节点连接*pplist。然后再移动*pplist的位置让它指向新的节点。

void SListPushFront(SListNode** pplist, SLTDateType x) {SListNode* newhead = BuySListNode(x);newhead->next = *pplist;*pplist = newhead;	
}

其实，这里的头插逻辑基本上没有什么难度。但是这里使用一级指针还是二级指针才是需要花时间去理解的！可以看到我们这里使用的是二级指针，为什么呢？一句话——“你要改变谁就要用谁的指针”。因为在test文件里面我用的是结构体的指针：

SListNode* plist = NULL;

所以我要改变外面的plist的话就要用plist的指针了，因为指针的指针就是二级指针！所以我这里就用了二级指针！！！(解答完毕）

1.4.2：中间插入

先来讲一下我的中间插入的逻辑：我的插入是在我要找到的数据的后一个位置插入，所以找到位置很重要所以我会写一个查找数据位置的函数

代码;

SListNode* SListFind(SListNode* plist, SLTDateType x) {assert(plist);SListNode* pos = plist;while (pos) {if (pos->data == x) {return pos;//找到了就返回，结束循环}pos = pos->next;}printf("你要找的值不存在\n");return NULL;//找不到就返回空
}

写完了寻找节点的函数以后，我们就可以来写一个中间插入的函数来。代码如下：

void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);//要对pos断言一下，因为这是中间插入，链表中有节点才能中间插入！SListNode* newnode = BuySListNode(x);SListNode* next = pos->next;//记录一下pos指向的下一个节点，因为pos->next要被改变!pos->next = newnode;newnode->next = next;}

1.4.3尾插

尾插？啥是尾插啊？顾名思义，尾插便是找到链表的尾巴然后再来插入，具体的逻辑可以参见代码。

void SListPushBack(SListNode** pplist, SLTDateType x)
{SListNode* newtail = BuySListNode(x);SListNode* tail = *pplist;if (tail == NULL) {//如果链表为空那就直接让*pplist指向newtail*pplist = newtail;}else {while (tail->next) {//这里找的是尾节点，所以当tail->next为空时就找到了尾节点了tail = tail->next;}tail->next = newtail;}
}

 1.5在链表中删除节点

和链表的插入一样，链表节点的删除也有三种。分别是头删，尾删，中间删除！

1.5.1：头删

头删，顾名思义便是删除头节点。思路很简单，就是调整一下plist的指向让plist指向下一个节点然后释放上一个节点就可以了。

代码：

void SListPopFront(SListNode** pplist) {assert(pplist);//pplist不可能为空，所以这里要预防一下assert(*pplist);//空链表不能删SListNode* del = *pplist;*pplist = (*pplist) ->next;free(del);del = NULL;
}

1.5.2：中间删除

这个操作的实现也是需要和 SListFind搭配使用的，前面我已经将 SListFind写好了。这里我就不再写了，我在这里直接写中间删除的函数就好了。当然这个中间删除函数与前面的中间插入一样，都只是删除中间的节点而不会删除头节点与尾节点。所以依照这个思路，我们便可以将代码写出来：

 代码：

void SListEraseAfter(SListNode* pos) {assert(pos);//中间删除不会删除头节点，更不会删除不存在的值。assert(pos->next);//也不能删除空指针SListNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

1.5.3尾删

顾名思义，尾删就是把链表的尾节点删除掉。删除的逻辑就是找到链表的尾节点的前面一个节点然后将这一个节点中的指向改为空。并把尾节点给释放掉。

代码：

void SListPopBack(SListNode** pplist) {assert(pplist);//指针的地址不可能为NULLassert(*pplist);//空链表不能尾删if ((*pplist)->next == NULL) {free(*pplist);*pplist = NULL;}else {SListNode* tail = *pplist;while (tail->next->next) {tail = tail->next;}SListNode* del = tail->next;tail->next = NULL;free(del);del = NULL;}
}

1.6销毁链表

因为我们的链表是malloc出来的一块一块的空间，所以当我们的链表用完以后就要对这些一块一块的空间进行释放。说所以我们又要写一个函数来销毁链表。

代码：

void SListDestroy(SListNode** pplist) {assert(pplist);assert(*pplist);//链表未创建不能销毁SListNode* cur = NULL;while (*pplist) {cur = (*pplist)->next;free(*pplist);*pplist = cur;}*pplist = NULL;printf("链表销毁成功!\n");
}

总结：

到这里我们就已经把我能讲的一些关于链表的知识，我所知道的关于链表的知识给讲完了。但是我还是想要总结一下：

1.在我们要操作链表时，比如想要增删时就要用二级指针。

2.当一个变量不可能为空指针时要对它进行assert断言。

3.当一个变量为空时会导致错误时也要对这个变量进行assert断言。

好了，总结完毕！