数据结构

链表

1. 定义：head, current, current.next。只已知第一节点，通过每个节点里存储下一节点地址的指针，形成线性数据存储关系。不按顺序的存储降低了数据插入/删除的时间复杂度。逻辑上相邻，物理上不相邻。
2. 存储结构：共用存储空间/独立存储空间
3. 特性：善于数据的增删改查，无序存储的数据检索效率比较低

共用存储空间

1. 节点和其他数据共用一个储存空间
2. 优点：无需提前分配空间，可存储无限数据
3. 缺点：由于存储比较分散，调试比较困难

独立存储空间

1. 一个链表或者多个链表使用独立的储存空间
2. 优点：具有唯一的编号，方便调试
3. 缺点：内存无法动态分配
4. 弥补缺陷：数组模拟链表，用数组实现，在其上加一层块状链表

常用分类

1. 单向链表

   • 每个节点(current)只存储下一个节点地址的指针 (current.next)

2. 双向链表

   • 每个节点(current)不仅存储下一个节点地址的指针，还存储上一个节点地址的指针 (current.next, current.previous)。包含head(第一个节点)和tail(最后一个节点)。

3. 循环链表

   • 在双向链表/单向链表的基础上，链表的第一个节点的上一个节点为链表的最后一个节点。

4. 块状链表

   • 储存的是数据的顺序表，每一个节点储存的是数据的顺序表，是块状的。