一、数组（Array）
1. 概念
<b>连续内存块</b>存储相同类型元素，通过下标（索引）随机访问，分为静态数组（长度固定）、动态数组（ArrayList/Vector，自动扩容）。
2. 底层原理
内存地址连续，首地址 + 下标 × 元素大小 = 目标元素地址；
静态数组编译 / 初始化时分配固定长度，超出直接越界；
动态数组底层依然是数组，存满后新建更大数组，拷贝旧数据，丢弃原数组。
3. 时间复杂度
随机访问：O(1)
头部 / 中间插入删除：O(n)（需要平移大量元素）
尾部追加：均摊 O(1)
4. 应用场景
基础存储：列表、缓存固定数据集；
底层容器：ArrayList、String 底层、图片像素存储；
算法：二分查找、滑动窗口、矩阵运算；
底层实现：栈、队列、哈希表底层。
二、链表（Linked List）
核心特征：<b>非连续内存</b>，节点存储「数据 + 指针」，依靠指针串联，无随机访问能力。
2.1 单向链表（Singly Linked List）
概念
每个节点只存：data + next指针，next 指向下一个节点；只能从头节点单向遍历，尾节点 next=null。
原理
内存分散，无需连续空间；
查询必须从头遍历，不能直接跳下标；
插入 / 删除只需修改指针，无需移动元素。
复杂度
查找：O(n)
已知节点插入 / 删除：O(1)
头部操作极快，尾部操作需要遍历全表 O(n)
场景
栈简单实现、LRU 简易缓存、稀疏数据存储。
2.2 双向链表（Doubly Linked List）
概念
节点：data + prev前驱指针 + next后继指针，可向前、向后双向遍历。
原理
支持从任意节点正反遍历；
删除当前节点时，不需要遍历找前驱（单向链表删节点必须从头找前驱）；
缺点：多存一份指针，内存开销更大。
复杂度
查找：O(n)
已知节点插入 / 删除：O(1)
场景
Java LinkedList、LRU 缓存、浏览器前进后退历史。
2.3 环形链表（循环链表 Circular Linked List）
概念
尾节点 next 指向头节点，首尾相连，无 null 终止；分单向环形、双向环形。
原理
遍历循环往复，不会出现空指针；
适合循环轮询场景；
判断环：快慢指针（弗洛伊德判环算法）。
三、双端队列 Deque（Double End Queue）
概念
同时支持<b>头部、尾部</b>插入、删除的线性容器，兼具栈和队列特性。
底层实现：数组（ArrayDeque）、双向链表（LinkedList）。
原理
数组实现：头尾双指针，循环数组，扩容拷贝；
链表实现：复用双向链表头尾节点操作。
操作
头增 / 头删、尾增 / 尾删 均 O(1)
应用场景
滑动窗口最大值算法；
消息双向缓冲、栈 / 队列混合使用；
Java ArrayDeque、阻塞队列。
四、哈希表（Hash Table / 散列表）
概念
通过<b>哈希函数</b>把 key 映射到数组下标，实现 key-value 快速存取；核心解决哈希冲突。
底层原理
哈希函数：hash(key)→index，将任意 key 转为数组索引；
哈希冲突：不同 key 算出相同下标；
冲突解决方案：
链地址法（HashMap）：数组下标挂单向链表，链表过长转红黑树；
开放寻址法（ThreadLocalMap）：线性探测、二次探测；
扩容：负载因子达到阈值，数组扩容 2 倍，重新哈希所有元素。
复杂度
理想无冲突：增删查 O(1)；最坏全冲突退化成链表 O(n)，树化后 O(logn)
场景
缓存：Redis Hash、Java HashMap；
去重、字典、词频统计；
数据库索引辅助、路由映射。
七、跳表 Skip List
概念
有序链表的多层索引结构，空间换时间，实现平衡树同等 O(logn) 性能。
底层原理
底层是完整有序单向链表（原始层）；
随机向上建立多层稀疏索引，高层索引快速跳跃，底层精准查找；
插入时随机生成层数，保证整体平衡，无需旋转、染色。
复杂度
增删查平均 O(logn)，实现简单，无复杂平衡操作。
场景
Redis 有序集合 ZSet 底层；
部分 KV 存储、内存有序容器；
替代平衡树，工程实现成本更低。
