Data Structures & Algorithms

1. 数据结构 1.1. 数组 - array.md 1.2. 链表 - linkedlist.md 1.3. 栈 - stack.md 1.4. 队列 - queue.md 1.5. 堆 - heap.md 1.6. 树 - tree.md 1.7. 图 - graph.md 1.8. 哈希表 -

1. 是什么 - 可动态扩容的数组 2. 动态数组 2.1. 数据结构 - 存放数据的数组 - 已使用的长度 - 总长度 2.2. API 2.3. 实现 2.3.1. 测试 3. 刷题套路 3.1. 双指针 3.1.1. 同向 - - [0, i) 是处理好的数据， [i, j) 是处理过但不需要

1. 是什么 - K-V对 2. 二叉搜索树实现 2.1. 数据结构 - 二叉搜索树 2.2. API 2.3. 实现 2.3.1. 测试 3. 哈希表实现 3.1. hash函数的设计 - 原则 - 一致性：如果a==b，则hash（a）==hash（b） - 高效性：计算高效简便 - 均匀性：哈

1. 是什么 2. 数组 vs 链表 数组按照索引查找快，链表插入删除快 3. 单向链表 3.1. 数据结构 - 头节点 - 长度 3.2. API 3.3. 实现 3.3.1. 测试 4. 双向链表 4.1. 数据结构 - 头节点 - 尾节点 - 长度 4.2. API - 同单向链表 4.3.

1. 是什么 - 先进先出 2. 普通队列 2.1. 数据结构 - 动态数组或链表 2.2. API 2.3. 实现 2.3.1. 测试 3. 循环队列 3.1. 数据结构 - 存放数据的数组 - 已使用的长度 - 总长度 - 头节点下标位置 - 尾节点下标位置 3.2. API - 同队列 3.3

1. 是什么 - 无序、不重复的集合 1.1. 数据结构 - hashmap 1.2. API 1.3. 实现 1.3.1. 测试

1. 是什么 - 后进先出 1.1. 数据结构 - 动态数组或链表 1.2. API 2. 实现 2.1. 测试

1. 二叉树是什么 每个节点最多有两个子节点 2. 二叉树操作 2.1. 遍历 2.1.1. 先序遍历 先访问根节点，然后访问左子树，最后访问右子树 2.1.2. 中序遍历 先访问左子树，然后访问根节点，最后访问右子树 2.1.3. 后序遍历 先访问左子树，然后访问右子树，最后访问根节点 2.1.4

1. 红黑树是什么 - 一种平衡二叉查找树 - 满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值 - 满足5条特性即可保证平衡 - 节点 要么是Red，要么是Black - 根节点 是Black - 叶子节点 （外部节点以及空节点）都是Black - Red

1. 跳表是什么 - 跳表相当于普通的链表有两个区别 - 有上、下、左、右四个指针 - 多了层的概念 1.1. 举例 - 普通链表 - - 有效层数为2的跳表 - - 有效层数为4的跳表 - 1.2. 特点 - 随机的数据结构 - 最底层包含了整个跳表的所有元素 - 典型的空间换时间，增删查改效率为