数据结构中二叉树，哈希表，顺序表，链表的比较补充

阿华代码，不是逆风，就是我疯，希望本文内容能帮到你！你们的点赞收藏是我前进最大的动力！！

零：引入

查询时间复杂度，我们默认是以最坏的情况来看，其次说平均，基本不会说最优的情况，

平衡二叉树，查询能达到O(logN),快于O（N），近似理解成O（1）

一：二叉搜索树

元素非常多，树的高度就很高，就会增加查询过程中的次数，如果实在数据库中就会比较敏感了，每次比较都可能会涉及到硬盘操作，

二：哈希表

1：速度最快O(1),哈希表会在合适的时机进行扩容，可以保持整体的时间复杂度任然是O（1），在实际开发中，我们用到的最多的就是hash表和数组

2：查询大致步骤——哈希表是把key转换为数组下标（通过一定的哈希函数），再在对应的数组下标中进行查找，这里只能比较相等

3：与数据库异——数据库查询的时候，经常需要指定条件，不是一定按照 相等 来比较的 例如：<> between and 范围查询

三：ArrayList

错误说法：ArrayList 查找速度比较快，LinkedList新增删除的速度比较快。

1：ArrayList底层使用的是数组，可以进行随机访问，每次随机访问进行读写的时候，速度是比较快的

2：随机访问不是查找，查找使用的是indexOf 这样的方法，按照元素的值进行查找，这个过程是要遍历ArrayList 开销为O（N）

3：ArrayList 尾插入/删除的速度比较快，但是头/中间/尾插入，删除元素比较慢（会对元素进行搬运）

四：LinedList

1：特点

底层是一个链表，不能进行随机访问

进行头/尾插，头/尾删时间复杂度都是O（1）

进行查找/中间位置的插入删除操作，都是O（N）

总结：相比较于ArrayList优势在于能够快速的进行头插、头删，在实现队列的时候很有用，其他方面ArrayList更优

2：三问:

（1）：用LinkedList 是否遍历速度更快呢？

答：链表访问下个元素的操作是用next这个引用，相比较顺序表元素下标++的操作，多了一次内存访问的过程

（2）：ArrayList是要预分配空间的，那么用LinkedList是否更节省内存呢？

答：链表的每一个节点都要有额外的空间储存指针，具体谁更省，有待考虑

（3）：用LinkedList ，在中间位置插入删除，为什么是O（N）?

LinkedList 是通过add(元素,下标)进行插入，这个根据下标找位置的过程，就是链表遍历O(N)的操作。