前言：
前面我们已经把顺序表的优点和缺点讲了，那么这篇文章就是单链表的这种数据结构的实现和理解。
1.概念
链表定义
链表是一种离散存储的数据结构，它只有一个指针域，下一个指针保存着前一个数据的地址；像链子一样串起来的结构就叫做单链表。
n个节点离散分配， 彼此通过指针相连每个节点只有一个前驱节点，每个节点只有一个后续节点。首节点没有前驱节点，尾节点没有后续节点。
结点结构体定义
struct ListNode { DataType data; //数据域 struct ListNode*next; //指针域 }ListNode;
结点的创建
为链表创建新结点并分配内存，把传进来的值赋给data, next置为空指针，并返回新结点。
ListNode *ListCreateNode(DataType data) { ListNode *node = (ListNode *) malloc ( sizeof(ListNode) ); if (node == NULL) { perror("malloc"); exit(-1); } node->data = data; node->next = NULL; return node; }
2.链表的头插法
动画演示
链表的头插有两种情况 ： 1.如果链表为空 ，执行头部插入 2.链表不为空，需要找到链表的头再进行插入
情况 1的处理
当前是空链表，插入之后成为头结点。
情况 2
当前链表不为空，则需要找到当前头结点，让新结点指向头结点；头结点再指向新结点。
代码实现
void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
3.链表的尾插
动画演示
代码实现
1. 如果当前链表为空 ，那么尾插 等于 头插
2. 如果当前链表不为空，则需要找到最后一个结点，让最后一个结点的指针指向新结点，新结点再指向尾结点、
void SListPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { *pphead = newnode; } else { // 找尾节点 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
4.链表的头删
函数接口
void SListPopFront(SLTNode** pphead)
动画演示
代码实现
1.如果当前链表是空的，不用删
2. 如果当前链表还有结点，则继续删。
void SListPopFront(SLTNode** pphead) { assert(*pphead != NULL); //if (*pphead == NULL) // return; SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
5.链表的尾删
函数接口：
void SListPopBack(SLTNode** pphead)
动画演示
代码实现
1. 链表内只有一个结点的情况，将当前结点的指针置为NULL，再释放当前结点。最后置空
2.如果链表内有多个结点存在，则需要遍历链表找到尾结点，然后释放尾结点；最后将指针置为NULL，防止空指针异常。
void SListPopBack(SLTNode** pphead) { assert(*pphead); // 1、只有一个节点 // 2、多个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { /*SLTNode* tailPrev = NULL; SLTNode* tail = *pphead; while (tail->next != NULL) { tailPrev = tail; tail = tail->next; } free(tail); tailPrev->next = NULL;*/ SLTNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
6.链表从中间插入结点
在第 i 个结点后面插入一个数据，数据值为 v
规则说明：
Head 为链表头，并且头结点内有数据
i >= 0
动画演示
代码实现
先分析情况
1.如果当前链表为空，则链表不需要删除。
2.如果链表不为空，则需要让新结点指向要插入的结点，再让前一个结点指向新结点。
ListNode *ListInsertNode(ListNode *head, int i, DataType v) { ListNode *pre, *aft, *vtx; // (1) 插入完毕后， pre -> vtx -> aft int j = 0; // (2) 定义一个计数器，当 j == i 时，表明找到要插入的位置 pre = head; // (3) 从链表头开始 while(pre && j < i) { // (4) 如果还没有到链表尾，或者没有找到插入位置则继续循环 pre = pre->next; // (5) 游标指针指向它的后继结点 ++j; // (6) 计数器加 1 } if(!pre) { return NULL; // (7) 元素个数不足，无法找到给定位置，返回 NULL } vtx = ListCreateNode(v); // (8) 创建一个值为 v 的鼓孤立结点 aft = pre->next; // (9) - (11) 为了串成 pre -> vtx -> aft vtx->next = aft; // (10) pre->next = vtx; // (11) return vtx; // (12) 返回插入的那个结点 }
7.从单链表中删除任意结点
删除任意结点跟任意位置插入结点的思路是一致的，只是反着来。
动画演示
代码实现
分情况讨论
1.如果当前链表为空，不需要删除
2.不为空，先找到要删除结点的前一个结点，让前一个结点指向要删除的结点的后一个结点，然后释放要删除结点的内存，再让后一个结点的指针指向前一个结点.
void SListErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); if (*pphead == pos) { SListPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
8.销毁链表
函数接口：
void ListDestroyList(ListNode **pHead)
动画演示
代码实现
1.链表为空，不删除。
2.链表不为空，遍历链表释放结点，最后指针置空。
void ListDestroyList(ListNode **pHead) { // (1) 这里必须用二级指针，因为删除后需要将链表头置空，普通传参无法影响外部变量； ListNode *head = *pHead; // (2) 给链表头解引用； while(head) { // (3) 如果链表非空，则继续循环； head = ListDeleteNode(head, 0); // (4) 产出链表头部，并且返回 后继结点； ListPrint(head); } *pHead = NULL; // (5) 将链表头置空 }
完整代码
#include "SList.h" void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); assert(newnode); newnode->data = x; newnode->next = NULL; return newnode; } void SListPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { *pphead = newnode; } else { // 找尾节点 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } void SListPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } void SListPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead); // 1、只有一个节点 // 2、多个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { /*SLTNode* tailPrev = NULL; SLTNode* tail = *pphead; while (tail->next != NULL) { tailPrev = tail; tail = tail->next; } free(tail); tailPrev->next = NULL;*/ SLTNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } void SListPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead != NULL); //if (*pphead == NULL) // return; SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; } SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; } void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pos); assert(pphead); // 头插 if (pos == *pphead) { SListPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySListNode(x); prev->next = newnode; newnode->next = pos; } } // 删除pos位置的值 void SListErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); if (*pphead == pos) { SListPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } } // 单链表在pos位置之后插入x void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); /*SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode;*/ // 不在乎链接顺序 SLTNode* newnode = BuySListNode(x); SLTNode* next = pos->next; // pos newnode next pos->next = newnode; newnode->next = next; } // 分析思考为什么不删除pos位置？ void SListEraseAfter(SLTNode* pos) { assert(pos); if (pos->next == NULL) return; SLTNode* del = pos->next; //pos->next = pos->next->next; pos->next = del->next; free(del); del = NULL; }
