链表思维导图
链表详解
树图思维导图提供 链表 在线思维导图免费制作，点击“编辑”按钮，可对 链表 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：f1bd22a149ab2a7abfc096d8e26f5ea6
思维导图大纲
链表思维导图模板大纲
分类
根据线性表的链式存储结构中每一个结点包含的指针个数分为单链表和多重链表
根据指针连接方式，分为动态链表和静态链表
单链表
定义
存储结构是链式存储，逻辑结构是线性结构
代码实现
c++实现
c实现
注意
typedef关键字用法
“LinkList”等价于“LNode*”,前者强调是链表，后者强调是结点
基本操作
插入：太简单了不多说；要注意特殊处理第一个结点；
删除：也太简单了不多说，要注意特殊处理最后一个结点；
查找：不具备随机访问特性，只能依次扫描，O(N)
创建
尾插法：设置一个表尾指针r，每次都插到最后，然后移动表尾指针r;
头插法：每次都插到头结点后面
初始一定一定要设置L->next = NULL
用于逆序链表
循环链表
循环单链表：表尾结点next指向表头结点
初始L->next = L;
如果很多时候对链表操作是在头部或尾部，可以让L指向表尾元素
循环双链表：表头prior指向表尾，表尾next指向表头
初始L->next = L;L->prior = L;
双链表
基本同单链表，唯一的不同就是多了一个指向前驱的指针
插入时应先连接好第i+1结点，再连接第i结点，顺序是绿黄蓝橙
静态链表
定义：用数组方式实现的链表
初始化：a[0]的next设为-1，其余设为-2，表示空闲
优点：增删不需要大量移动
缺点：不能随机存取；容量固定不可变
应用：操作系统的文件分配表FAT，用于数据元素数量固定不变的场景
顺序表与链表的比较
开放式问题，谈论顺序表和链表优缺点，从时间空间两方面来讨论
顺序表
优点
时间上
可以直接存取，查找速度快
空间上
不保存指针，存储密度高
缺点
时间上
插入、删除操作要移动大量元素，更新速度慢
空间上
如果采用静态存储，空间满了不能扩充；再插入导致溢出
链表
优点
时间上
插入、删除操作无需移动元素，更新速度快
空间上
基本不会满，也不会有溢出问题
缺点
时间上
只能顺序访问，查找速度慢
空间上
存储指针，存储密度低
头结点与头指针与首元节点
头结点作用
统一空链表和非空链表的操作
方便插入、删除操作在表头的实现与在表中一致
头指针
具有标识作用
常用头指针冠以链表的名字
是头结点的指针
首元结点是头结点后第一个结点
沪公网安备 31011502019485号
上海工商