单链表
链表的概念及结构
概念：链表是一种物理存储结构上连续、非顺序的存储结构，数据元素的逻辑顺序 是通过链表中的指针链接次序实现的。
注意：
- 从上图可以看出，链式结构在逻辑上连续的，但是在物理上不一定连续
- 现实中的节点一般是从堆上申请出来的
- 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能是连续的也可能是不连续
链表的分类
实际中链表的结构非常多样，一下情况组合起来就有8中情况：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用的还是两种结构：
- 无头单向非循环链表：结构简单，一般不会用来单独存放数据。实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等等。另外这种结构在笔试面试中出现很多
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构带来很多优势，实现反而简单了。
链表的实现
动态申请一个节点
SListNode* BuySListNode(SLTDataType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
创建链表
SListNode* CreateSListNode(int n) { SListNode* phead = NULL, * ptail = NULL; for (int i = 0; i < n; i++) { SListNode* newnode = BuySListNode(i); if (phead == NULL) { ptail = phead = newnode; } else { ptail->next = newnode; ptail = newnode; } } return phead; }
单链表打印
void SListPrint(SListNode* phead) { SListNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
单链表尾插
//尾插要想改变原来的，就要传地址 void SListPushBack(SListNode** pplist, SLTDataType x) { SListNode* newnode = BuySListNode(x); if (*pplist == NULL) { *pplist = newnode; } else { SListNode* cur = *pplist; while (cur->next != NULL) { cur = cur->next; } cur->next = newnode; } }
单链表尾删
void SListPopBack(SListNode** pplist) { assert(*pplist); if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { SListNode* ptail = *pplist; while (ptail->next->next != NULL) { ptail = ptail->next; } free(ptail->next); ptail->next = NULL; } }
单链表头插
void SListPushFront(SListNode** pplist, SLTDataType x) { SListNode* newnode = BuySListNode(x); newnode->next = *pplist; *pplist = newnode; }
单链表头删
void
注意：在C语言的单链表，关于改变链表的数字的函数传递方式，传的都是地址。如果不传地址的话就不能改变链表的数值。
就如这个例子一样：
void swap(int* a, int* b) { int x = *a; *a = *b; *b = x; } void swap1(int a, int b) { int x = a; a = b; b = x; } int main() { int a = 10; int b = 20; swap1(a, b); printf("a=%d b=%d\n", a, b); swap(&a, &b); printf("a=%d b=%d\n", a, b); }
运行结果：
对于第二种方法，传递的是地址，这里直接把地址里面的数字改了
单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x) { SListNode* cur = plist; while (cur != NULL) { if (cur->data == x) { printf("找到了\n"); } cur = cur->next; } printf("找不到\n"); }
单链表在pos位置之后插入x
void SListInsertAfter(SListNode** pplist, SListNode* pos, SLTDataType x) { assert(pos); if (*pplist == pos) { SlistPushFront(pplist, x); } else { SListNode* prve = *pplist; while (prve->next != pos) { prve = prve->next; } SListNode* newnode = BuySListNode(x); prve->next = newnode; newnode->next = pos; } }
单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos) { assert(pos); if (pos->next == NULL) { return; } else { SListNode* newNode = pos->next; pos->next = newNode->next; free(newNode); } }
双向循环链表
初始化
typedef struct ListNode { struct ListNode* prve; struct ListNode* next; LTDataType data; }LTNode; LTNode* LTInit() { LTNode* phead = BuyListNode(-1); phead->next = phead; phead->prve = phead; return phead; }
申请一个新的节点
LTNOde* BuyListNode(LTDatatype x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = NULL; node->prve = NULL; return node; }
双向链表的尾插
这个最主要的一部分，就是找到双向链表的尾部。
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prve;//tail 现在就是尾指针 tail->next = newnode; newnode->prve = tail; newnode->next = phead; phead->prve = newnode; }
双向链表的尾删
void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next = phead); LTNode* tail = phead->prve; LTNode* tailPrve = tail->prve; free(tail); tailPrve->next = phead; phead->prve = tailPrve; }
思路：找到最后一个节点，然后再通过最后一个节点，找到最后一个的前一个节点。连接起来就可以了。
双向链表的头插
void LTPushFront(LTNode* phead, LTDataType x) { LTNode* newnode = BuyListNode(x); assert(phead); newnode->next = phead->next; phead->next->prve = newnode; phead->next = newnode; newnode->prve = phead; }
双向链表的头删
思路：先找到第一个然后再找到第二个节点，接着释放掉第一个节点。
void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* first = phead->next; LTNode* second = first->next; free(first); phead->next = second; second->prve = phead; }
顺序表和链表的区别
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低 | 只需要修改指针指向 |
| 插入 | 动态顺序表，空间不够的时候，需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
