1. 链表的概念及结构
概念：
链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的（链表在逻辑上是连续的，在物理结构上不一定连续） 。
链表是由一个一个节点（结点）组成的，一个节点由两个部分组成：要存储的数据 + 指针（结构体指针）
因此，只要定义节点的结构，就等于定义了链表：
typedef int SLTDataType; //链表是由节点组成 typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
2. 实现单链表
2.1 链表的打印
void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead; while (pcur) { printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL\n"); }
2.2 链表的尾插
void SLTPushBack(SLTNode* phead, SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; //链表为空，新节点作为phead if (NULL == phead) { phead = newnode; return; } //链表不为空，找尾节点 SLTNode* ptail = phead; while (ptail->next) { ptail = ptail->next; } //ptail就是尾节点 ptail->next = newnode; }
这样写是错误的！当一开始链表为空时，尾插的节点就变成了第一个节点，因此要把phead中的NULL改为第一个节点的地址，所以要传phead的地址，而不是传值。
应该这样写：
//因为头插、尾插、指定位置插入都需要申请新节点，所以单独封装成一个函数 SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (NULL == newnode) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; return newnode; } void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x); //链表为空，新节点作为phead if (NULL == *pphead) { *pphead = newnode; return; } //链表不为空，找尾节点 SLTNode* ptail = *pphead; while (ptail->next) { ptail = ptail->next; } //ptail就是尾节点 ptail->next = newnode; }
2.3 链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x); newnode->next = *pphead; *pphead = newnode; }
2.4 链表的尾删
void SLTPopBack(SLTNode** pphead) { assert(pphead); //链表不能为空 assert(*pphead); //链表不为空 //链表只有一个节点，有多个节点 if (NULL == (*pphead)->next) { free(*pphead); *pphead = NULL; return; } SLTNode* ptail = *pphead; SLTNode* prev = NULL; while (ptail->next) { prev = ptail; ptail = ptail->next; } prev->next = NULL; //销毁尾节点 free(ptail); ptail = NULL; }
2.5 链表的头删
void SLTPopFront(SLTNode** pphead) { assert(pphead); //链表不能为空 assert(*pphead); //让第二个节点成为新的头 //把旧的头节点释放掉 SLTNode* next = (*pphead)->next;//->的优先级高于* free(*pphead); *pphead = next; }
2.6 查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) { assert(pphead); //遍历链表 SLTNode* pcur = *pphead; while (pcur) //等价于pcur != NULL { if (pcur->data == x) { return pcur; } pcur = pcur->next; } //没有找到 return NULL; }
2.7 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); assert(pos); //要加上链表不能为空 assert(*pphead); SLTNode* newnode = SLTBuyNode(x); //pos刚好是头节点 if (pos == *pphead) { //头插 SLTPushFront(pphead, x); return; } //pos不是头节点的情况 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //prev -> newnode -> pos prev->next = newnode; newnode->next = pos; }
2.8 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = SLTBuyNode(x); newnode->next = pos->next; pos->next = newnode; }
2.9 删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(*pphead); assert(pos); //pos刚好是第一个节点，没有前驱节点，执行头删 if (*pphead == pos) { //头删 SLTPopFront(pphead); return; } SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; }
2.10 删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) { assert(pos); //pos->next不能为空 assert(pos->next); SLTNode* del = pos->next; pos->next = pos->next->next; free(del); del = NULL; }
2.11 销毁链表
void SListDesTroy(SLTNode** pphead) { assert(pphead); assert(*pphead); SLTNode* pcur = *pphead; while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }
完整代码：
//SList.h #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDataType; //链表是由节点组成 typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; void SLTPrint(SLTNode* phead); //链表的头插、尾插 //void SLTPushBack(SLTNode* phead, SLTDataType x);//err void SLTPushBack(SLTNode** pphead, SLTDataType x); void SLTPushFront(SLTNode** pphead, SLTDataType x); //链表的头删、尾删 void SLTPopBack(SLTNode** pphead); void SLTPopFront(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode** pphead, SLTDataType x); //在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos); //销毁链表 void SListDesTroy(SLTNode** pphead);
//SList.c #include "SList.h" void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead; while (pcur) { printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL\n"); } //因为头插、尾插、指定位置插入都需要申请新节点，所以单独封装成一个函数 SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (NULL == newnode) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; return newnode; } void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x); //链表为空，新节点作为phead if (NULL == *pphead) { *pphead = newnode; return; } //链表不为空，找尾节点 SLTNode* ptail = *pphead; while (ptail->next) { ptail = ptail->next; } //ptail就是尾节点 ptail->next = newnode; } void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x); newnode->next = *pphead; *pphead = newnode; } void SLTPopBack(SLTNode** pphead) { assert(pphead); //链表不能为空 assert(*pphead); //链表不为空 //链表只有一个节点，有多个节点 if (NULL == (*pphead)->next) { free(*pphead); *pphead = NULL; return; } SLTNode* ptail = *pphead; SLTNode* prev = NULL; while (ptail->next) { prev = ptail; ptail = ptail->next; } prev->next = NULL; //销毁尾节点 free(ptail); ptail = NULL; } void SLTPopFront(SLTNode** pphead) { assert(pphead); //链表不能为空 assert(*pphead); //让第二个节点成为新的头 //把旧的头节点释放掉 SLTNode* next = (*pphead)->next;//->的优先级高于* free(*pphead); *pphead = next; } //查找 SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) { assert(pphead); //遍历链表 SLTNode* pcur = *pphead; while (pcur) //等价于pcur != NULL { if (pcur->data == x) { return pcur; } pcur = pcur->next; } //没有找到 return NULL; } //在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); assert(pos); //要加上链表不能为空 assert(*pphead); SLTNode* newnode = SLTBuyNode(x); //pos刚好是头节点 if (pos == *pphead) { //头插 SLTPushFront(pphead, x); return; } //pos不是头节点的情况 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //prev -> newnode -> pos prev->next = newnode; newnode->next = pos; } //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = SLTBuyNode(x); newnode->next = pos->next; pos->next = newnode; } //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(*pphead); assert(pos); //pos刚好是第一个节点，没有前驱节点，执行头删 if (*pphead == pos) { //头删 SLTPopFront(pphead); return; } SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos) { assert(pos); //pos->next不能为空 assert(pos->next); SLTNode* del = pos->next; pos->next = pos->next->next; free(del); del = NULL; } //销毁链表 void SListDesTroy(SLTNode** pphead) { assert(pphead); assert(*pphead); SLTNode* pcur = *pphead; while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }
//Test.c //int removeElement(int* nums, int numsSize, int val) //{ // //定义两个变量 // int src = 0, dst = 0; // // while (src < numsSize) // { // //nums[src] == val,src++ // //否则赋值,src和dst都++ // if (nums[src] == val) // { // src++; // } // else // { // //说明src指向位置的值不等于val // nums[dst] = nums[src]; // dst++; // src++; // } // } // // //此时dst的值刚好是数组的新长度 // return dst; //} //void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) //{ // int l1 = m - 1; // int l2 = n - 1; // int l3 = m + n - 1; // // while (l1 >= 0 && l2 >= 0) // { // //从后往前比大小 // if (nums1[l1] > nums2[l2]) // { // nums1[l3--] = nums1[l1--]; // } // else // { // nums1[l3--] = nums2[l2--]; // } // } // // //要么是l1 < 0，要么是l2 < 0 // while (l2 >= 0) // { // nums1[l3--] = nums2[l2--]; // } //} #include "SList.h" void SListTest01() { //一般不会这样去创建链表，这里只是为了给大家展示链表的打印 SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode)); node1->data = 1; SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode)); node2->data = 2; SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode)); node3->data = 3; SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode)); node4->data = 4; node1->next = node2; node2->next = node3; node3->next = node4; node4->next = NULL; SLTNode* plist = node1; SLTPrint(plist); } void SListTest02() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); //SLTPushBack(NULL, 5); //SLTPushFront(&plist, 5); //SLTPrint(plist); //SLTPushFront(&plist, 6); //SLTPrint(plist); //SLTPushFront(&plist, 7); //SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); //SLTPopBack(&plist); //SLTPrint(plist); } void SListTest03() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); //头删 //SLTPopFront(&plist); //SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); //SLTNode* FindRet = SLTFind(&plist, 3); if (FindRet) { printf("找到了！\n"); } else { printf("未找到！\n"); } SLTInsert(&plist, FindRet, 100); SLTPrint(plist); SLTInsertAfter(FindRet, 100); SLTPrint(plist); 删除指定位置的节点 //SLTErase(&plist, FindRet); //SLTPrint(plist); SListDesTroy(&plist); } int main() { //SListTest01(); //SListTest02(); SListTest03(); return 0; }
3. 链表的分类
链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：
链表说明：
注：
- 之前代码里写的 SList 意思是 single linked list --> 单链表（不带头单向不循环链表）
- 刚才在单链表中提到的“头节点”指的是第一个有效的节点；“带头”链表里的“头”指的是无效的节点
- “带头”中的“头”：放哨的；头节点：哨兵位（不保存任何有效的数据）
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表。
- 无头单向非循环链表：结构简单，⼀般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等；另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，⼀般用在单独存储数据，实际中使用的链表数据结构，都是带头双向循环链表；另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
