常用的数据结构
数组、链表、散列表、栈、队列、图、树
数组
数组，在内存上必须给出连续的空间（一但内存空间不足时，需要将整个数组移位到另一块内存足够大的地方）。
内存空间占用的少，因为链表还要保存下一个节点的内存地址。
访问性：访问性好，数组内的数据可随机访问，因为其内存地址时连续的。
操作性：操作性差，在数组中插入、删除元素，都会导致其后的元素整体移动（插入时向后移动、删除时向前移动）。
扩展性：扩展性差，因为一个数组建立后所占用的空间大小就是固定的（大多数语言时这样的）。
大O表示：读取 O(1)，插入 O(n)，删除 O(n)
链表
链表，内存地址上可以是不连续的,每个链表的节点包括当前节点的值和下一个节点的内存地址(单向链表的一个,双向链表的话会有两个)。
访问性：访问性差，链表不具备随机访问性，其每次访问都是从头开始访问。
操作性：操作性好，只需要操作对应节点之前的内存地址为变更后的节点地址。
扩展性：扩展性好，因为其内存不连续，只要还有剩余内存即可。
大O表示：读取 O(n)，插入 O(1)，删除 O(1)
散列表
散列表使用数组来存储数据，通过一个散列函数将其映射到数组不同位置。
避免hash冲突
较低的填装因子（填装因子=散列表包含的元素数/位置总数）。
良好的散列函数。
使用数组链表处理冲突。
大O表示：平均情况读取、插入、删除都为O(1)，最糟糕情况读取、插入、删除都为O(n)
图
非加权图—广度优先搜索用于查找其最短路径。
加权图（权重为正）—狄克斯特拉算法用于查找其最短路径。
加权图（权重有负）—贝尔曼-福德算法用于查找其最短路径。
参考文档
数组与链表的优缺点
