# 数据结构 ## 数据结构和基本实现 ### 数据存储总结一下一些常用数据结构，和它们支持的查找顺序。 | 数据结构 | 支持写查删 | 可以的实现 | | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | ---------------------------------------------------------------------------------------------------------------------------- | ------------------------------- | |

| `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

哈希链表