【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（一）https://developer.aliyun.com/article/1617260
6.4 查找单链表中数据
SLNode* SLTFind(SLNode* pphead, SLNDataType x) { SLNode* cur = pphead; while (cur!=NULL) { if (cur->val == x) return cur; else cur = cur->next; } return NULL; }
这里需要注意的是:遍历链表，找到返回当前节点，没有找到继续向下遍历
6.5 关于单链表的任意位置插入和删除
6.5.1 单链表的pos指定前插入
void SLTInsert(SLNode** pphead,SLNode *pos,SLNDataType x)//pos指定之前插入 { assert(pphead); assert(*pphead); if (pos == NULL)//没有节点 { SLTPushFront(pphead, x); } if (*pphead == pos)//一个节点 { SLTPushFront(pphead, x); } else//多个节点 { SLNode* newnode = CreateNode(x); SLNode* cur = *pphead; while (cur->next != pos)//上面避免了pos等于cur { cur = cur->next; } cur->next = newnode; newnode->next = pos; } }
这里需要注意的是:需要分为三种情况，空节点，一个节点，多个节点就行处理。空节点调用尾插或者头插都可以，一个节点(在pos前插入)那么可以调用头插
6.5.2 单链表的删除pos当前结点
void SLTEeara(SLNode** pphead, SLNode* pos) { assert(pphead);//防止用户传个空指针 assert(*pphead); assert(pos); SLNode* next = pos->next; SLNode* cur = *pphead; if (cur==pos) *pphead = NULL; free(cur); cur = NULL; else { while (cur->next != pos) { cur = cur->next; } cur->next = next; free(pos); pos = NULL; } }
这里需要注意的是：分为两种情况，存在一个节点和多个节点的处理。如果使用三个变量，需要使用到的地址不会丢失，就不需要担心先后顺序问题。结点是一块块的独立空间，其链接方式也是较灵活的，这里跟上面方法是类似的。
如果不想在pos之前插入\删除，可以改动逻辑在pos之后进行插入、删除。
6.5.3 单链表的pos之后插入
void SLTInsertAfter(SLNode **pphead,SLNode* pos, SLNDataType x) { assert(pphead); assert(*pphead); if (pos == NULL)//没有节点 { SLTPushFront(pphead, x); } if (*pphead == pos)//一个节点 { SLTPushBack(pphead, x); } else//多个节点 { SLNode* newnode = CreateNode(x); SLNode* back = pos->next; newnode->next = back; pos->next = newnode; } }
6.5.4 单链表的pos之后删除
void SLTEearaAfter(SLNode **pphead,SLNode* pos) { assert(pphead); assert(*pphead); assert(pos); SLNode* cur = *pphead; SLNode* back = pos->next; if (cur == pos)//只有一个结点 SLTPopBack(pphead); if(back->next==NULL) { free(back); back = NULL; pos->next = NULL; } else { pos->next = back->next; free(back); back = NULL; } }
上面的两个接口实现过程跟SLTInsert、SLTEeara实现类似的，看看代码就能理解
在完成了单链表的核心接口，我们需要继续完善剩下的接口，使实现的单链表功能更加丰富起来。
6.6 单链表的打印
void SLTPrint(SLNode** pphead)//二级指针改变外的结构体指针类型 { assert(pphead); SLNode* cur = *pphead; while (cur!= NULL) { printf("%d->", cur->val); cur = cur->next; } printf("NULL\n"); }
这里需要注意的是：当cur==NULL时，没有进去循环，需要额外打印NULL，最后不要忘记单链表的销毁
void SLTDestroy(SLNode** pphead) { assert(pphead); SLNode* cur = *pphead; while (cur) { SLNode* next = cur->next; free(cur); //这里cur不要赋空，还需要使用的 cur = next; } *pphead = NULL; }
这里需要注意的是：链表是通过多个节点链接而成的，同时也是一块块独立空间，通过cur去访问每一个空间和释放每一块空间。其中free指针跟指针变身是没有关系的，释放的是指针所指向的那一块动态空间
七、顺序表和链表的区别
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定 连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除 元素 | 可能需要搬移元素，效率低 O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要 扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
不管是哪一种数据结构都有他的优点和缺点，对此在使用数据结构中应该知道它的优缺点是什么，加以合理地利用解决实际中的问题。
