数据结构中二叉树，哈希表，顺序表，链表的比较补充
阿华代码，不是逆风，就是我疯，希望本文内容能帮到你！你们的点赞收藏是我前进最大的动力！！
目录
（2）：ArrayList是要预分配空间的，那么用LinkedList是否更节省内存呢？
（3）：用LinkedList ，在中间位置插入删除，为什么是O（N）?
零：引入
查询时间复杂度，我们默认是以最坏的情况来看，其次说平均，基本不会说最优的情况，
平衡二叉树，查询能达到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)的操作。
原文地址：https://blog.csdn.net/2301_80133875/article/details/142124080
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！