Ch09 Summary

数组

​ 优点：

• 随机访问快（可以通过下标迅速定位）
• 查找速度快

​ ** 缺点**：

• 增加删除的效率低（可能需要大幅度移动数据）
• 内存空间不灵活，需要一整块的内存，也有可能浪费内存
• 扩展性差，大小在初始化时就指定好了

链表:

​ 缺点：

• 访问速度慢，需要从头开始遍历

​ 优点：

• 插入删除的速度快
• 可扩展性强，大小不固定
• 内存空间是分散的

单链表与双链表的区别：

• 单链表在删除节点时需要一个temp，指针移动的复杂度为2i
• 双向链表可以用二分法查找

哈希表：

​ 优点：

• 插入/查询/删除效率非常高

缺点:

• 空间利用率不高，底层使用的是数组，并且使用的某些单元是没有被利用的
• 哈希表中的元素是无序的，不能按照固定的顺序来遍历哈希表中的元素
• 不能快速的找出哈希表中的最大值或者最小值

树结构：

• 在某种场景下，使用树结构会更加方便

• 因为树结构是非线性，可以表示一对多

• 比如文件的目录结构

• 对于一个平衡树的插入和查找等效率为O(logN) 平衡树： 树两边的数据均匀分布 非平衡树： 树两边的数据不均匀分布

• 连续插入有序的数据，树分布不均匀，变成一个链表结构，插入和查找等效率变成 O(N)