数据结构——单链表（不带头）【C】
单链表
1. 链表的概念以及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
单链表结构：
注意：
- 从图上可以看出，单链表在逻辑结构上是连续的，但是物理结构上不一定连续。
- 在实际过程中我们单链表的节点都是从堆上申请出来的。
- 从堆上的空间是编译器分配出来的，因此申请的空间地址有可能连续，也有可能不连续。
2. 单链表的模拟实现
接口总览
typedefint SLDateType;typedefstructSListNode{ SLDateType date;structSListNode* next;}SLNode;//打印链表voidSLPrint(SLNode* plist);//尾插voidSLPushBack(SLNode** plist, SLDateType num);//头插voidSLPushFront(SLNode** plist, SLDateType num);//尾删voidSLPopBack(SLNode** plist);//头删voidSLPopFront(SLNode** plist);//查找链表中的元素 SLNode*SLFind(SLNode* plist, SLDateType num);//在任意位置插入元素voidSLInsert(SLNode** plist, SLNode* pos, SLDateType num);//删除任意位置的元素voidSLErase(SLNode** plist, SLNode* pos);//摧毁链表voidSLDestory(SLNode** plist);2.1 单链表的尾插和尾删
2.1.1 尾插
voidSLTPushBack(SLNode** pphead, SLNDataType x){assert(pphead); SLNode* newnode =CreateNode(x);//判断空链表 if(*pphead ==NULL){*pphead = newnode;}else{// 找尾 SLNode* tail =*pphead;while(tail->next !=NULL){ tail = tail->next;} tail->next = newnode;}}2.1.2 尾删
voidSLTPopBack(SLNode** pphead){assert(pphead);//assert(*pphead);// 温柔的检查//if (*pphead == NULL)// return;// 空assert(*pphead);// 1、一个节点// 2、一个以上节点if((*pphead)->next ==NULL){free(*pphead);*pphead =NULL;}else{ SLNode* tail =*pphead;while(tail->next->next !=NULL)// 找到尾结点的前驱结点 { tail = tail->next;}free(tail->next); tail->next =NULL;}}2.2 头插和头删
2.2.1 头插
voidSLTPushFront(SLNode** pphead, SLNDataType x){assert(pphead); SLNode* newnode =CreateNode(x); newnode->next =*pphead;*pphead = newnode;}2.2.2 头插的应用（链表的逆置）
反转链表
根据头插法将源链表的头结点，头插入新建的newNode 链表中。
structListNode*ReverseList(structListNode* head ){structListNode* cur = head ;structListNode* newNode =NULL;while(cur !=NULL){structListNode* next = cur ->next ; cur->next = newNode; newNode = cur; cur = next ;}return newNode ;}2.2.3 头删
voidSLTPopFront(SLNode** pphead){assert(pphead);// 空assert(*pphead); SLNode* tmp =*pphead;*pphead =(*pphead)->next;free(tmp);}2.3 查找链表中的元素
按值查找 时间复杂度为: O(N)
SLNode*SLTFind(SLNode* phead, SLNDataType x){ SLNode* cur = phead;while(cur){if(cur->val == x){return cur;}else{ cur = cur->next;}}returnNULL;}2.4 在任意位置插入元素
voidSLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x){// 严格限定pos一定是链表里面的一个有效节点assert(pphead);assert(pos);assert(*pphead);if(*pphead == pos){// 头插SLTPushFront(pphead, x);}else{ SLNode* prev =*pphead;while(prev->next != pos){ prev = prev->next;} SLNode* newnode =CreateNode(x); prev->next = newnode; newnode->next = pos;}}2.5 删除任意位置的元素
voidSLTErase(SLNode** pphead, SLNode* pos){assert(pphead);assert(*pphead);assert(pos);if(*pphead == pos){// 头删SLTPopFront(pphead);}else{ SLNode* prev =*pphead;while(prev->next != pos){ prev = prev->next;} prev->next = pos->next;free(pos); pos =NULL;}}2.6 遍历链表 和 销毁链表
时间复杂度为 O(N)
voidSLTPrint(SLNode* phead){ SLNode* cur = phead;while(cur !=NULL){printf("%d->", cur->val); cur = cur->next;}printf("NULL\n");}voidSLTDestroy(SLNode** pphead){assert(pphead); SLNode* cur =*pphead;while(cur){ SLNode* next = cur->next;free(cur); cur = next;}*pphead =NULL;}3. 链表 VS 顺序表
3.1 比较存储结构
顺序表
- 优点：支持随机存储 ，存储密度高
- 缺点：大片连续空间分配不方便 ，更改容量不方便
链表
- 优点：离散的小空间分配方便，方便更改容量
- 缺点：不可以随机存取，存储密度底
3.2 从基本操作比较
一、创建
顺序表
- 需要分配大片连续的空间，若空间过小则之后不方便扩容 ，若空间过大则回造成空间的浪费
- 静态分配：数组容量不可改变
- 动态分配：容量可以改变单是存入数据需要移动大量的元素，时间代价高
链表
- 只需要分配结点即可，之后方便拓展
- 相较于顺序表灵活性高
二、销毁
顺序表
- 静态： 系统回收
- 动态： 需要手动“fee” 回收堆中的空间
链表
- 一次删除各个结点 “fee” 注意要将链表置空
三、 增加和删除
顺序表 ：增删都需要移动元素，前移或是后移 时间复杂度为 O(N) 开销主要来自移动元素 （代价高）
链表：只需要插入和删除修改指针既可 时间复杂度为 O(N) ，开销主要来自查找目标元素 （代价底）
四、 查找
顺序表 ： 按位查找时间复杂度为 O(1)、按值查找时间复杂度为 O(N)有序情况下为O(logn)
链表： 按位查找时间复杂度为 O(N)、按值查找时间复杂度为 O(N)都只能从头结点开始查找
注 ： 顺序表的查找效率比链表高
链表——表长难以估计、经常要增加和删除元素 。
顺序表——表长可以估计、查询操作较多。
