数组
- 数组是一种非常常见的线性数据结构
- 它最大的特点是使用一组连续的内存空间，存储一组相同类型的数据：
数组的存储形式.jpg
- 之所以强调相同类型，是因为相同的类型的数据会占据相等的存储空间，因此就可以通过计算直接获取内存地址。
- 优点：数组最大的特性，是支持随机访问，即可以通过索引直接访问某个数据
- 数组的访问性能非常高，还有一个原因是在硬件层面有CPU的高速缓存（cache）提升性能
- 缺点：数组的添加、删除的性能很低，因为会涉及大量的数据搬移工作。
- 所以你会发现，go 中给数组和切片的操作很少，低性能可能是其中的原因之一
- 这也是为什么 go 中指定 slice 长度可以提升性能（减少追加数据时的数据搬移工作）
链表
- 链表是另一种非常基础的数据结构，与数组不同，它使用零散的内存存储数据：
数组和链表的存储.jpg
单链表.jpg
- 由于它的存储方式和数组完全不同，所以它和数组的特性完全不同：
- 优点：高效的插入和删除
链表的插入和删除.jpg
- 缺点：链表的查找非常低效，只能依次遍历所有节点
- 在 go 中，container 包里有双向链表、双向循环链表等容器供我们使用，下面是链表的部分方法：
func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveAfter(e, mark *Element)
func (l *List) MoveToFront(e *Element)
func (l *List) MoveToBack(e *Element)
func (l *List) Front() *Element
func (l *List) Back() *Element
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) InsertAfter(v interface{}, mark *Element) *Element
func (l *List) PushFront(v interface{}) *Element
func (l *List) PushBack(v interface{}) *Element
- 单纯的链表在实际编程中很少用到，但是如果我们对链表进行升级，给一些额外的结构，它就会有非常广泛的应用。
- 简单的变型有：双向链表、循环链表等，复杂的变型有：红黑树、B+树等。这种变型非常重要，其中就包括 redis 中实现 zset 的跳表：
跳表-二级索引.jpg
栈
- 一种操作受到限制的线性表，最大的特点是后进先出
- 栈可以用数组或者链表实现
- 栈只有两种操作：入栈和出栈
栈.jpg
def sum(a,b):
return a + b
if __name__ == '__main__':
print(sum(1,2))
下面的图片展示了这个程序执行的过程：
函数调用栈，省略了变量名
队列
- 队列也是一种操作受限的线性表，它的特性是先进先出
栈和队列.jpg
- 队列也只有两种主要操作：从队尾入队和从队首出队
- 队列也可以有变型：循环队列、阻塞队列等：
循环队列.jpg
阻塞队列.jpg
- 队列可以非常方便地实现生产者-消费者模型，应用有消息队列中间件。
散列表（哈希表）
- 散列表依赖于数组支持依照下标随机访问的特性
- 散列表由三个部分组成：键、散列函数 和 散列值。这个的过程是，键通过散列函数的计算得到散列值，然后去寻找这个值代表的响应的地址：
散列
- 非常常见的一个问题是，如果多个键的散列值相同（散列冲突），该怎么办？常见的解决办法有两种：
- 开放寻址法：
散列冲突-开放寻址法.jpg
- 链表法
散列冲突-链表法.jpg
- 上面的方法都是最基础的解决方法，实际上，根据场景的不同，会有很多种解决方案。例如，将链表法后接的链表设计成红黑树，可以防止哈希碰撞攻击。
- 你会发现，数据结构的使用不是孤立的，多种数据结构的组合，会有超乎想象的结果。
在这些组合中，哈希+链表就是一个包打天下的万金油组合，redis中的zset就是这样。
树
- 树是一种非线性表结构，可以用于表示一对多的关系：
树
-
树中有一些概念用于描述这个结构：
树的描述 - 树有很多类型，其中最简单的是二叉树，因为二叉树的性质简单，且方便存储。
- 树有很多应用，其中就有大家最为熟知的B+树:
B+树
-
还有一种比较有意思的应用：Trie树，这个数据结构可以帮助我们实现关键词提示功能：
搜索关键词提示
Trie树的结构是这样的：
Trie树
在这个树中，存储了“hello”、“her”、“hi”、“how”、“see”、“so” 几个查找关键字，当用户输入一个特定字符的时候，Trie树会搜索相关的节点，并遍历到树的叶子节点，途径的所有路径都会被记录下来，用于关键字提示：
Trie树搜索
实际上，输入法的自动补全，IDE的代码的自动补全，浏览器网址输入的自动补全，都使用了这种数据结构。
图
- 图用于表示一种多对多关系
图
- 多对多的关系很比较复杂，所以图的种类也比较多，大体来说有无向图、有向图、带权图等
有向图.jpg
带权图.jpg
- 图有两种存储方法：使用邻接矩阵 和 使用邻接表
图存储-邻接矩阵.jpg
- 临接矩阵的优点：存储方式简单、直接，可以高效地获取两个点之间的关系
- 缺点：
1、如果是无向图，邻接矩阵是关于主轴对称的，这会浪费一般的空间
2、如果各个点之间的关联非常稀疏，使用邻接矩阵会浪费大量空间。例如微信的好友关系
图存储-邻接表.jpg
优点
1、比较节省存储空间
2、你可以根据业务场景改造邻接表，以提升特定场景下的性能。例如将链表改造成红黑树。缺点
1、对缓存不友好
2、邻接表的查找比邻接矩阵更加耗时
3、如果存储的图是有向图，又要统计点的出度和入度，需要添加逆邻接表图的应用非常广泛，如保存好友关系、最短路径规划等
