浅析数据结构-线性结构之线性表-链表
b.链式存储[链表]
重要性：学习树和图的基础
定义：
- 1.N个结点离散分配，彼此通过指针相连；
- 2.每个结点只有一个前驱结点，每个结点只有一个后续结点；
- 3.首结点没有前驱结点，尾结点没有后续结点。
链表的优缺点：
- 优点:
1:： 删除 不需移动其他元素, 只需改变指针.
2：结点在内存中空间不要求连续!空间利用率高
3：内存利用率高 - 缺点:
1：数组元素效率低,例如:访问第100个元素,必须从头节一直next99次才能找到。
专业术语：
首结点：第一个有效结点
尾结点：最后一个有效结点
头结点：
- 头结点数据类型和首结点类型一样
- 第一个有效结点之前的结点
- 头结点并不存放数据
头指针：指向头结点的指针变量
尾指针：指向尾结点的指针变量
为什么需要使用头结点？
对链表进行操作的时候，在首结点加入一个没有实际含义的头结点，方便操作。
如果希望通过一个函数对链表进行处理，我们至少需要哪些参数？
- 确定链表需要一个参数：头指针
- 因为我们通过头指针就可以推算出链表的其他所有参数。
分类：
单链表：每一个结点上面有两个指针域
双链表：每一个结点上面有两个指针域
循环链表：能通过任何一个结点找到其他结点
非循环链表
插入结点：
a. r = p->pNext;p->pNext = q;q->qNext = r;
b. q->pNext = p->pNext;p->pNext = q;
删除结点：
直接写：p->pNext = p->pNext->pNext;是错误的，会造成内存泄漏。
r = p->pNext;p->pNext = p->pNext->pNext;free(r);
链表的头插法：
链表的头插法简单来说，就是每一个新结点都插入在最前端，即头结点之后。
链表的尾插法：
链表的尾插法，新结点每次都插入在最后一个。
链表的实现
1 |