之前的笔记搬运
链表
0x1链表的分类
- 单项链表
链表中最简单的一种是单向链表，每个元素包含两个域，值域和指针域，我们把这样的元素称之为节点。每个节点的指针域内有一个指针，指向下一个节点，而最后一个节点则指向一个空值。
- 单项循环链表
单项循环链表和单项链表唯一的区别, 就是尾结点的NEXT指针指向首节点
- 双项链表
双向链表的指针域有两个指针，每个数据结点分别指向直接后继和直接前驱。单向链表只能从表头开始向后遍历，而双向链表不但可以从前向后遍历，也可以从后向前遍历。除了双向遍历的优点，双向链表的删除的时间复杂度会降为O（1），因为直接通过目的指针就可以找到前驱节点，单向链表得从表头开始遍历寻找前驱节点。缺点是每个节点多了一个指针的空间开销。
- 双项循环链表
同理, 双项循环链表和双项链表唯一的区别, 就是尾结点的NEXT指针指向首节点
0x2 链表的使用环境
已经动态数组的优缺点
缺点: 增删改查的时间复杂度都是线性阶, 所以非常慢
优点: 随机访问的时间复杂度为常量阶, 非常快
适用场景: 已知数据大概大小, 增删改查操作少, 随机访问操作多;
而链表的的优缺点正好和动态数组相反, 所以适用场景也和动态数组相反;
