介绍
- 一种线性表
- 内存分布不连续
- 节点node不仅存储数据，还存储上下节点的地址
常用链表
单链表
- 数据结构如下：
单链表（图片来自网络）
可以发现
1.尾节点指向的是一个空地址
2.每个节点只包含一个指针，即后继指针
3.插入和删除节点的时间复杂度为O(1)，查找的时间复杂度为O(n)
循环链表
- 数据结构如图
循环链表（图片来自网络）
可以发现
1.除了尾节点的后继指针指向首节点的地址外均与单链表一致
2.适用于存储有循环特点的数据，比如约瑟夫问题，见：https://www.jianshu.com/p/ee0e4d36eaba
双向链表
如图
双向链表
可以发现
1.每个结点不止有一个后继指针 next 指向后面的结点，还有一前驱指针 prev 指向前面的结点。
2.首节点的前驱指针prev和尾节点的后继指针均指向空地址。
3.需要更多的存储空间
4.插入、删除操作比单链表效率更高O(1)级别
5.空间换时间思想
以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。
对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据
双向循环链表
如图
双向循环链表
- 首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点。
数组、链表
时间复杂度
1.数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。
2.链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。
链表缺点
1.内存空间消耗更大，因为需要额外的空间存储指针信息
2.对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作
数组缺点
1.大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制
2.数组过大，容易导致内存不足（out of memory）
正确编写链表代码
插入节点
如果如果我们在结点 p 后面插入一个新(x)的结点。
x—>next = p—>next;
p—>next = x;
注意
- 这两行代码不能反过来，否则会导致内存泄漏。
- 先判判断头结点是否为空，如下：
if (head == null) { head = x}
删除节点
如果要删除p节点的后续节点，一行代码可以搞定
p->next = p->next->next;
注意
如果要删除的节点是最后一节点，要先判断：
if (head->next == null) { head == null}
技巧方案
利用哨兵实现简单化
引入哨兵节点，避免头尾节点的判断
重点留意边界条件处理
经常用来检查链表是否正确的4个边界条件：
1.如果链表为空时，代码是否能正常工作？
2.如果链表只包含一个节点时，代码是否能正常工作？
3.如果链表只包含两个节点时，代码是否能正常工作？
4.代码逻辑在处理头尾节点时是否能正常工作？
多练
1.单链表反转
2.链表中环的检测
3.两个有序链表合并
4.删除链表倒数第n个节点
5.求链表的中间节点
这5个问题后续介绍
网友评论