数据结构的存储方式

数据结构的存储方式只有两种，数组（顺序存储）、链表（链式存储）

队列、栈:既可以用数组实现也可以用链表实现
图:邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。
邻接表和邻接矩阵是图（graph）这种数据结构的两种常见表示方法。它们各自有优缺点，适用于不同的场景。下面分别介绍这两种表示方法。

邻接矩阵
定义：邻接矩阵是一个二维数组（或矩阵），用来表示图中顶点之间的连接关系。对于一个包含n个顶点的图，它的邻接矩阵是一个n×n的矩阵A，其中A[i][j]的值代表从顶点i到顶点j是否存在边。对于无权图，如果顶点i和顶点j之间有边，则A[i][j] = 1；否则A[i][j] = 0。对于有权图，A[i][j]则存储的是边(i, j)的权重，而如果不存在这样的边，通常会用一个特殊的值（如无穷大或0）来表示。
优点：
- 简单直观，容易理解和实现。
- 检查两个顶点之间是否存在边的时间复杂度为O(1)。
- 对于稠密图（即边数接近最大可能值的图），使用邻接矩阵比较节省空间且高效。
缺点：
- 对于稀疏图（即边数远小于最大可能值的图），邻接矩阵会浪费大量的空间，因为大多数元素都是0。
- 添加或删除顶点时需要重新分配矩阵的空间，这可能会很耗时。
邻接表
定义：邻接表是一种更加节省空间的图表示方法，特别是对于稀疏图。它由一个长度为n的数组组成，每个元素指向一个链表（或列表），这个链表包含了与该顶点相邻的所有顶点。对于有权图，链表中的每一个元素还可以包括边的权重信息。

优点：
- 相比于邻接矩阵，对于稀疏图来说，邻接表更节省空间。
- 添加或删除边的操作相对简单，时间复杂度为O(1)（假设可以快速定位到相应的顶点）。
- 对于遍历图中的所有边，邻接表也更为高效。
缺点：
- 检查两个顶点之间是否存在边的时间复杂度为O(d)，其中d是出发顶点的度（即与之相连的顶点数量）。在最坏情况下，这可能是O(n)。
- 实现起来稍微复杂一些，尤其是在处理有权图时，需要额外的数据结构来存储边的权重。
  选择哪种表示法
- 如果图是稠密的，并且你需要频繁检查两个顶点之间是否有边，那么邻接矩阵可能是更好的选择。
- 如果图是稀疏的，或者你更关心节省空间以及添加/删除边的效率，那么邻接表可能更适合。
- 在某些特定的应用场景下，比如当图的边具有方向性（有向图）或图的结构是动态变化的时候，邻接表通常也是更好的选择。
散列表:就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针;线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。
树:用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单;用链表实现就是很常⻅的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。

总结

数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N);而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。
链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题;如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问;而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。