链表的概念及结构
概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
结构
在逻辑上链表应该是这样子的：
在现实中是这样子的：
注意：
链表在逻辑上时连续的，但是在物理上不一定连续。
现实中的节点一般是从堆上申请出来的 。
从堆上申请的空间，可能是连续的也可能是不连续的。
单链表的实现
结构
单链表结构中有两个数据，一个是存储数据的，还有一个指针指向下一个节点。
typedef int SLTDateType; typedef struct SListNode { SLTDateType date; struct SListNode* next; }SLTNode;
它的接口有哪些呢？
// 动态申请一个节点 SLTNode* BuySListNode(SLTDateType x); // 单链表打印 void SListPrint(SLTNode* plist); // 单链表尾插 void SListPushBack(SLTNode** pplist, SLTDateType x); // 单链表的头插 void SListPushFront(SLTNode** pplist, SLTDateType x); // 单链表的尾删 void SListPopBack(SLTNode** pplist); // 单链表头删 void SListPopFront(SLTNode** pplist); // 单链表查找 // 找到返回这个节点的地址。找不到返回NULL SLTNode* SListFind(SLTNode* plist, SLTDateType x); // 单链表在pos位置之后插入x void SListInsertAfter(SLTNode* pos, SLTDateType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SLTNode* pos); // 单链表的销毁 void SListDestroy(SLTNode* plist); //在pos前插入 void SListInsert(SLTNode** pplist,SLTNode* pos, SLTDateType x); // 删除pos节点 void SListErase(SLTNode** pplist, SLTNode* pos);
申请节点
我们要添加数据，难免要频繁的开辟节点，所以我们分装以个函数专门来开辟节点。
// 动态申请一个节点 SLTNode* BuySListNode(SLTDateType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); //开辟失败结束掉程序 exit(-1); } newnode->date = x; newnode->next = NULL; return newnode; }
打印链表
打印链表比较简单，只需要遍历一遍链表即可。
void SListPrint(SLTNode* plist) { SLTNode* cur = plist; while (cur) { printf("%d->", cur->date); cur = cur->next; } printf("NULL\n"); }
尾插
尾插时链表可能为空，所以这时就要把将头指向开辟的节点，这是需要改变头，想要改变一级指针，所以就要传一级指针的地址，这时就需要用一个二级指针来接收，如果链表不为空，我们正常尾插就可以，我们需要先找到尾节点，然后就为节点的next指向newnode即可。
// 单链表尾插 void SListPushBack(SLTNode** pplist, SLTDateType x) { // 断言pplist一定不为空，为空时程序异常，终止程序 assert(pplist); SLTNode* newnode = BuySListNode(x); if (*pplist == NULL) { //链表为空 *pplist = newnode; } else { SLTNode* cur = *pplist; //找尾节点 while (cur->next) { cur = cur->next; } cur->next = newnode; } }
头插
头插同样需要改变头结点，所以还是需要二级指针，头插只需要将newnode的next指向原链表的头，然后将原链表的头指向newnode就可以了。
void SListPushFront(SLTNode** pplist, SLTDateType x) { // 断言pplist一定不为空，为空时程序异常，终止程序 assert(pplist); SLTNode* newnode = BuySListNode(x); newnode->next = *pplist; (*pplist) = newnode; }
尾删
尾删只剩一个节点时同样的需要改变头指针，这时free掉头结点，将其置NULL即可。正常情况下，我们只需要找到尾节点的前一个，然后释放掉尾节点，然后把前一个的next置NULL即可。
// 单链表的尾删 void SListPopBack(SLTNode** pplist) { // 断言pplist一定不为空，为空时程序异常，终止程序 assert(pplist); //断言链表为空就不要删了 assert(*pplist); if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { SLTNode* tail = *pplist; // 至少有两个节点所以tail->next一定不为NULL while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
头删
头删一定需要改变头结点，所以同样需要二级指针，我们需要保存头结点的next，让然后释放掉头结点，将头结点重新指向保存下来的next即可。
// 单链表头删 void SListPopFront(SLTNode** pplist) { // 断言pplist一定不为空，为空时程序异常，终止程序 assert(pplist); //断言链表为空就不要删了 assert(*pplist); //*pplist一定不为NULL SLTNode* cur = (*pplist)->next; free(*pplist); *pplist = cur; }
查找
查找就很简单了，我们只需要遍历一遍链表即可。
// 单链表查找 SLTNode* SListFind(SLTNode* plist, SLTDateType x) { //断言链表为空就不要查了 assert(plist); SLTNode* cur = plist; while (cur) { if (cur->date == x) { return cur; } cur = cur->next; } return NULL; }
在pos位置之后插入x
只需要将newnode的next指向pos的next，然后将pos的next指向newnode即可。
// 单链表在pos位置之后插入x void SListInsertAfter(SLTNode* pos, SLTDateType x) { assert(pos); SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; }
在pos位置前面插入
如果是一个节点间的话接相当于头插，我们可以复用上面头插的代码，正常情况下我们需要遍历找到pos的前一个位置，将newnode的next指向pos，再把该节点指向newnode即可。
void SListInsert(SLTNode** pplist, SLTNode* pos, SLTDateType x) { assert(pplist); if (pos == *pplist) { SListPushFront(pplist, x); } else { SLTNode* cur = *pplist; while (cur->next != pos) { cur = cur->next; } SLTNode* newnode = BuySListNode(x); newnode->next = pos; cur->next = newnode; } }
删除pos之后的值
不能删除最后一个节点，其他情况我们可以直接释放掉pos的next，将pos的next指向下一个即可。
// 单链表删除pos位置之后的值 void SListEraseAfter(SLTNode* pos) { assert(pos); assert(pos->next); SLTNode* cur = pos->next; pos->next = cur->next; free(cur); cur = NULL; }
删除pos位置的值
我们需要遍历找pos的前一个位置，然后将pos的前一个位置的next指向pos的next，然后释放掉pos即可，但是如果pos是头结点，我们这样处理不了，我们可以单独处理，相当头删。
void SListErase(SLTNode** pplist, SLTNode* pos) { assert(pplist); if (pos == *pplist) { SListPopFront(pplist); } else { SLTNode* cur = *pplist; while (cur->next != pos) { cur = cur->next; } cur->next = pos->next; free(pos); } }
销毁链表
销毁只需要遍历释放即可。
// 单链表的销毁 void SListDestroy(SLTNode* plist) { assert(plist); SLTNode* cur = plist; while (cur) { SLTNode* pur = cur; cur = cur->next; free(pur); } }
到这里对于单链表的增删查改已经讲的差不多了，我们的查找可以充当改，找到那个节点，直接修改date即可。
今天的分享就到这里结束了，感谢大家的支持和关注。
