¶ # 简单数据结构比较

本section作者: coderwhyopen in new window

• 树结构和数组/链表/哈希表的对比有什么优点呢?

数组:

• 优点:
  • 数组的主要优点是根据下标值访问效率会很高.
  • 但是如果我们希望根据元素来查找对应的位置呢?
  • 比较好的方式是先对数组进行排序, 再进行二分查找.
• 缺点:
  • 需要先对数组进行排序, 生成有序数组, 才能提高查找效率.
  • 另外数组在插入和删除数据时, 需要有大量的位移操作(插入到首位或者中间位置的时候), 效率很低.

链表:

• 优点:
  • 链表的插入和删除操作效率都很高.
• 缺点:
  • 查找效率很低, 需要从头开始依次访问链表中的每个数据项, 直到找到.
  • 而且即使插入和删除操作效率很高, 但是如果要插入和删除中间位置的数据, 还是需要重头先找到对应的数据.

哈希表:

• 优点:
  • 我们学过哈希表后, 已经发现了哈希表的插入/查询/删除效率都是非常高的
  • 但是哈希表也有很多缺点.
• 缺点:
  • 空间利用率不高, 底层使用的是数组, 并且某些单元是没有被利用的.
  • 哈希表中的元素是无序的, 不能按照固定的顺序来遍历哈希表中的元素.
  • 不能快速的找出哈希表中的最大值或者最小值这些特殊的值.

树结构:

• 我们不能说树结构比其他结构都要好, 因为每种数据结构都有自己特定的应用场景.
• 但是树确实也综合了上面的数据结构的优点(当然优点不足于盖过其他数据结构, 比如效率一般情况下没有哈希表高), 并且也弥补了上面数据结构的缺点.
• 而且为了模拟某些场景, 我们使用树结构会更加方便. 比如文件的目录结构.