关于那些数据结构，如果要讨论他们的优劣性。我只能记住这么多：

数组

连续排列，所以省 空间 ，自带索引，所以查询时间复杂度低，缺点是插入和修改比较难，需要移动相当多的元素来为目标元素腾位置，时间复杂度高。

链表

不需要连续排列，所以占用空间比起数组要多一些， 优点：插入和修改操作简单，只需要改动相应的少数几个元素的指针指向。 缺点：查询时间复杂度高，需要查询整个链表才能找到 (这是最坏情况，看批运，因为没索引)

树

通常情况下讨论二叉树，时间复杂度比线性好，但可以被 退化 成链表，即失去所有左或者右子树 AVL 树和 B 树都是具有良好稳定性的树

堆

可以以树的方向理解，是一种特殊的 完全二叉树 ，这种数据结构是拿来存放诸如” 大量的 “” 带有冗余的 “” 不经常做查询的 “数据，对堆的查询会很复杂，但是插入比较简单：压到最底端，在完全二叉树下即右下方向，然后根据完全二叉树数值上左子树 ≤ 根 ≤ 右子树的性质，维护。

栈

先进后出的形式

队列

先进先出

哈希表

比起链表，在每个栈帧空间中除了元素数值，多存储一个指针，这样占用空间更多但是查询，删除修改和插入简单都是 O (1)，通过对应哈希函数做到，但是会遇见 哈希冲突 ，避免和解决哈希冲突 (也就是维护哈希表) 需要花费额外的时间复杂度和空间复杂度。

图

分有向图和无向图 有向图会为了存储方向花掉更多空间，而且限制会比无向图多，不够灵活，但是有向图也分为单向有向图和双向有向图，这个跟双向链表相似，不展开讲了
无向图非常灵活

总结：

数组，链表是线性数据结构时间复杂度 O (n) 开始，树是分治，时间复杂度 logn 开始 (n 叉树，对数的底数就为 n)

时间：2023-11-30 22:51:28

tags: 算法，数据结构，编程，数据结构与算法，数据结构与算法分析，数据结构与算法设计

作者：buynonsense