链表尾删
- 尾删的细节较多一点
1: 链表为空时，无须删除
2: 链表只有一个元素时，做特需处理
3: 正常处理
这里提供两种方法给大家参考
- 方法一： 前后指针
使用一个指向为空的指针 prev和一个指向头节点的指针cur,当cur->next指向的不是NULL时我们让prev 指向cur节点，而cur指向cur的下一个节点，循环直到cur->next指向null时，prev->next指向的就是我们要删除的最后一个节点.
void SListPopBack(SListNode** pplist) { assert(*pplist); //断言 判断是否为空指针 //当只有一个节点时 if ((*pplist)->next == NULL) { //只有一个结点，直接释放该结点，然后将结点置为NULL free(*pplist); *pplist = NULL; } else { SListNode* cur = *pplist; SListNode* prev = NULL; while (cur->next != NULL) { prev = cur; cur = cur->next; //循环遍历 } free(prev->next); //释放尾结点 prev->next = NULL; } }
- 方法二: 知需判断cur->next->next是否为空，如果为空释放cur->next。当链表只有两个
节点时循环不进去，直接释放cur->next.
void SListPopBack(SListNode** pplist) { assert(*pplist);//断言 判断是否为空指针 //只有一个结点，直接释放该结点，然后将结点置为NULL if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { SListNode* cur = *pplist; while (cur->next->next != NULL) { cur = cur->next;//循环遍历 } free(cur->next); //释放尾结点 cur->next = NULL; } }
链表头删
- 链表头删逻辑也简单，只需要注意一下链表是否为空。然后用一个临时变量保存头指针
的->next,然后在把头指针销毁，把头指针给回临时变量即可.
// 单链表头删 void SListPopFront(SListNode** pplist) { assert(*pplist); //断言 判断是否为空指针 SListNode* tmp = (*pplist)->next;//保存头指针的下一个节点 free(*pplist); //销毁释放头指针 *pplist = tmp; 头指针指向释放前的下一个节点 }
链表查找
- 获得链表某个节点的数据思路也较简单
1： 定义一个cur指针指向头节点，不断指向下一个节点
2： 如查找成功，返回节点cur的数据
3： 如cur指向Null已经遍历完了，则说明查找的内容不存在，返回空指针。
SListNode* SListFind(SListNode* plist, SLTDateType x) { assert(plist);//断言 判断是否为空指针 SListNode* cur = plist; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
链表在指定位置之后插入数据
- 先把新节点的next 指向pos->next, 然后再把pos->next 更新成新节点.
void SLInsertAfter(SListNode* pos, SLTDateType x) { assert(pos);//断言 判断是否为空指针 SListNode* newnode = BuySListNode(x);//申请一个节点 newnode->next = pos->next; //新节点指向pos位置的下一个节点 pos->next = newnode; //pos下一个位置插入新节点 }
链表删除指定位置之后的数据
- 整体逻辑就是保存将要删除位置下一个节点的位置，把pos->next后的位置在链接上要删
除位置的下一个节点。 如果pos下一个节点为空，无需删除直接返回即可.
void SListEraseAfter(SListNode* pos) { assert(pos);//断言 判断是否为空指针 if (pos->next == NULL) //如果pos下一个节点为空，无须删除 return; SListNode* cur = pos->next->next;//保存要删除位置的下一个节点 free(pos->next); //释放pos之后的数据 pos->next = cur; //链接上要删除位置的下一个节点 }
链表在指定位置之前插入数据
- 算法思路：
1： 当指定位置为第一个元素时，这时我们只需调用一下头插函数即可.
2： 遍历链表，找到pos上一个节点的数据.
3： 找到上一个节点数据，把新节点的next指向指定位置，在把找到的节点指向新开辟的节点，这样就可以链接上了。
void SLInsertfront(SListNode** pplist, SListNode* pos, SLTDateType x) { assert(pos);//断言 判断是否为空指针 if (*pplist == pos) //当pos位置是第一个节点数据时，那就是头插了 { SListPushFront(pplist, x);//头插 } else { SListNode* tmp = *pplist; while (tmp->next != pos) { tmp = tmp->next;//循环遍历 } SListNode* newnode = BuySListNode(x); newnode->next = pos; //把新节点的next指向指定位置 tmp->next = newnode; //找到的节点指向新开辟的节点 } }
链表删除指定位置之前的数据
- 整体思路：
- 1: 当指定位置pos是第一个节点时，无需删除，直接返回即可。
- 2: 当指定位置pos是第二个节点数据时，只需要进行头删即可。
- 3: 遍历数组，找到pos 之前要删除节点数据的上一个节点。把该节点的next（就是pos上
一个节点的数据）直接销毁释放掉，再把找到的节点next重新链接上pos.
void SLErasefront(SListNode** pplist, SListNode* pos) { assert(pos); //断言 判断是否为空指针 if (pos == *pplist) //当指定是第一个节点时，无需再删除，直接返回. { printf("pos位置前为空\n"); return; } else if ((*pplist)->next == pos)//当指定位置pos是第二个节点数据时，只需要进行头删即可 { SListPopFront(pplist);//头删 } else { SListNode* tmp = *pplist; while (tmp->next->next != pos) { tmp = tmp->next; //遍历循环 } free(tmp->next);//释放pos之前的节点数据 tmp->next = pos; //链接上pos } }
链表删除指定位置的数据
- 思路:
1: 当指定位置pos是第一节点数据时，直接使用头删即可。
2: 查找指定位置pos上一个节点位置，再把该位置的next链接上pos的next位置.
3: 释放指定位置的数据。
void SLErase(SListNode** pplist, SListNode* pos) { assert(pos);//断言 判断是否为空指针 if (pos == *pplist)//当pos是第一节点数据时，直接使用头删即可 { SListPopFront(pplist);//头删 } else { // SListNode* tmp = *pplist; while (tmp->next != pos)//找pos上一个节点 { tmp = tmp->next; } tmp->next = pos->next;//将需要删除的结点的上一个结点的next指向需要删除的下一个结点 free(pos);//释放指定位置的数据 pos = NULL; } }
链表的销毁
当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。
- 思路：保存当前节点的下一个结点的地址，释放当前结点，再将指针指向刚刚保留的结
点，如此循环直到为空。链表销毁成功.
// 单链表的销毁 void SListDestroy(SListNode* plist) { assert(plist); SListNode* cur = plist; while (cur != NULL) { SListNode* next = cur->next; //保存下一个节点 free(cur); //释放当前指定 cur = next; //指向下一个节点 } }
