数据结构

数据结构和基本实现

数据存储

总结一下一些常用数据结构，和它们支持的查找顺序。

数据结构	支持写查删	可以的实现
Stack/Queue 栈/队列	O(1)首尾写查删value	LinkedList 链表
SortedContainers 有序结构	O(logn)写查删value O(logn)查value→rank	BalancedTree 二叉平衡树
Set/Dict 集合/字典	O(1)写查删(key, value)	HashTable 哈希表

基本上所有的数据类型都是建立在List和LinkedList的基础上。Python中有些方便的库能支持不同的查找顺序，下面也有一些简单的基于List或LinkedList的实现。

支持快速写查删数据结构

还有一些衍生数据结构，在一些场景很有用：

Data Structure	Function	可以的实现
Binary Heap 二叉堆	O(1) 查找最大最小值 O(logn) 插入/删除最大最小值	Complete Binary Tree 满二叉树
OrderedDict 有序字典	O(1)查找首尾(key, value)	LinkedHashmap 哈希链表
Monotonic Stack 单调栈	O(n) 查找数组每一位的 nextGreater/nextSmaller元素	Stack 栈
Trie 前缀树	O(n) 查找字符串是词典中的 前缀/单词	Dict->Dict 字典
UnionFind 并查集	O(1) 查找图的连通性	N-array Tree 多叉树的森林