1.链表的概念
概念：链表是一种物理上不连续，非顺序的存储结构，数据元素的逻辑顺序上是通过指针来连接的线性表。
2.链表的分类
链表的分类有很多，主要有以下部分组成不同的链表：
3.链表和顺序表的区别
不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续，但物理上不一定连续
随机访问 支持O(1) 不支持：O(N)
任意位置插入或者删除元素 可能需要搬移元素，效率低O(N) 只需修改指针指向
插入 动态顺序表，空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁
缓存利用率 高 低
4.单链表的增删查改
链表结构如下：
头文件（函数声明）：
typedef int SLTDataType; typedef struct SListNode { SLTDataType a; struct SListNode* next; }SLTNode; void SLTPrint(SLTNode* phead); //头部插入删除/尾部插入删除 void SLTPushBack(SLTNode** pphead, SLTDataType x); void SLTPushFront(SLTNode** pphead, SLTDataType x); void SLTPopBack(SLTNode** pphead); void SLTPopFront(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos); //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //销毁链表 void SListDesTroy(SLTNode** pphead);
代码实现
打印链表：
//打印 void SLTPrint(SLTNode* phead) { SLTNode* node = phead; while (node) { printf("%d ", node->a); node = node->next; } }
头部插入删除：
//头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* node = c_jian(x); if (*pphead==NULL) { *pphead = node; } node->next = *pphead; *pphead = node; } //头删 void SLTPopFront(SLTNode** pphead) { assert(*pphead && pphead); SLTNode* node = (*pphead)->next; free(*pphead); *pphead = NULL; *pphead = node; }
尾部插入删除：
//尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* node = c_jian(x); if (*pphead == NULL) { *pphead = node; } else { SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = node; } } //尾删 void SLTPopBack(SLTNode** pphead) { assert(*pphead && pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } SLTNode* tail= *pphead; SLTNode* tail_1 = *pphead; while (tail->next) { tail_1 = tail; tail = tail->next; } free(tail); tail_1->next = NULL; tail = NULL; }
查找数据：
//查找结点 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { assert(phead); while (phead) { if (phead->a == x) return phead; phead = phead->next; } return NULL; }
在指定位置之前插入数据：
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); assert(pos); SLTNode* node = c_jian(x); SLTNode* prev = *pphead; if (*pphead == pos) { SLTPushFront(pphead, x); } else { while (prev->next != pos) { if (prev->next == NULL) exit(1); prev = prev->next; } node->next = pos; prev->next = node; } }
删除pos节点：
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); SLTNode* node = *pphead; if (*pphead == pos) { SLTPopFront(pphead); } else { while (node->next != pos) { if (node == NULL) exit(1); node = node->next; } SLTNode* node1 = node->next; node->next = node1->next; free(node1); node1 = NULL; } }
在指定位置之后插入数据：
void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* node = c_jian(x); node->next = pos->next; pos->next = node; }
销毁链表：
void SListDesTroy(SLTNode** pphead) { SLTNode* node = NULL; while ((*pphead)->next) { node = *pphead; *pphead = (*pphead)->next; free(node); } free(*pphead); }
