数组

1. 数组提供对元素O(1)访问，又能很好地使用二分检索和快速排序。
2. 数组维护一组不断变化的数据代价很大，如插入，删除。
3. 插入和删除操作通常需要通过移动元素来实现。
4. 数组扩容通常需要通过数组复制来实现。
5. 在数据量不多或静态数据时，数组是最佳选择。

链表

1. 一个单链表包含一组元素，每个元素包含数据和指向下一个元素的指针。双向链表，循环链表等都是链表的变种。
2. 链表具有恰好容纳其所有内容的大小，每个元素都需要指针的附加存储开销。
3. 在链表中，插入和删除操作只需要通过修改指针来实现，并不需要移动其他元素。
4. 链表特别适合需要中间插入和删除的情况，也适用于管理一批规模经常变动的无顺序数据。
5. 链表不适合随机访问，只能通过遍历实现。

树

1. 树是一种分层性数据结构。
   1.1. 在一颗树里存储着一组节点，每个节点保存一个值，它可以指向0个或多个节点，但只能被另一个节点所指向。
   1.2. 根节点没有被其他节点的指针指向。
2. 二分搜索树
   2.1. 二叉树。
   2.2. 每个节点大于左子树所有节点；每个节点小于右子树所有节点。
   2.3. 完全随机的数据，普通的二分搜索树很好用；极端情况下会退化成链表。
3. AVL树(平衡二叉树)
   3.1. 对于任意一个节点，左子树和右子树的高度不能超过1。
   3.2. 平衡二叉树的高度和节点数量之间的关系是 logn。
   3.3. 核心操作：标注节点高度，计算平衡因子（高度差），维护平衡 -> LL/RR/LR/RL -> 左旋转,右旋转。
   3.4. 对于查询较多的使用情况，AVL树很好用 -> O(logn)。
4. 红黑树
   4.1. 红色节点表示『2-3』树中 3节点 的左边元素。；
   4.2. 红黑树是保持『黑平衡』的二叉树，严格意义上不是平衡二叉树。 最大高度：2logn -> O(logn)。
   4.3. 核心操作：左旋转；右旋转；颜色翻转。
   4.4. 红黑树牺牲了平衡性（2logn高度），添加删除相对AVL树更有优势
   红黑树统计性能更优（综合增删改查所有的操作）- > TreeMap。

散列表

1. 散列表是由数组,链表,红黑树等数据结构,构造的一种能够支持动态数据的存储和提取的结构。
2. 散列表关键思想就是散列函数 通过关键码(key)生成一个散列值,这个值作为存储信息的链表的下标。
3. 缺点：如果散列函数不好,或者所用数组太小,则链表长度则有可能很长。
4. java中Hashmap实现：数组 + 链表 + 红黑树。红黑树则是优化链表过长的问题。