常见的数据结构

目录

1.数组（Arrays）

2.链表

 3.栈

 4.队列

 5.Map和哈希表

 6.树

7.堆

 

---

1.数组（Arrays）

数组是最简单也是最常见的数据结构，他们的特点是可以通过索引（位置）轻松访问元素

它们是做什么用的？

想象一下有一排剧院椅。每把椅子都分配了 一个位置，因此每个观众都会从他将要坐的椅子上分配一个号码（索引）。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）

特性

• 元素的值按照顺序存储，并通过从0到数组长度的索引访问
• 数组是连续的内存块
• 它们通常由相同类型的元素组成
• 元素的访问和添加速度很快（尾插时）；搜索和删除不是 在O（1）中完成的

2.链表

链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接

它们是做什么用的？

链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索显示的页面的完美数据结构。

特性：

• 元素不存储在连续的内存中
• 完美的优秀内存管理（内存可以动态使用）
• 插入和删除都很快；访问和搜索元素是线性时间内完成的

 3.栈

堆栈是一种抽象的数据类型，它形式化了受限访问集合的概率。后进先出，因此，添加到堆栈中的最后一个元素是您从中删除的第一个元素

堆栈可以使用数组或者链表实现

它们是做什么用的？

现实生活中最常见的例子是在食堂中将盘子叠放在一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。

堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。

另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。

特性：

• 您一次只能访问最后一个元素（顶部的元素）
• 一个缺点是，一旦从顶部弹出元素以访问其他元素，它们的值将从堆栈的内存中丢失；
• 其他元素的访问实在线性时间内完成的；任何其他操作都在O（1）中

 4.队列

队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。

它们是做什么用的？

这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。

 特性：

• 我们只能直接访问引入的“最旧”元素
• 搜索元素将从队列的内存中删除所有访问过的元素
• 弹出/推送元素或获取队列的前端是在恒定时间内完成的。搜索是线性的。

 5.Map和哈希表

散列表也叫哈希表，是根据键值对（key，value）进行访问的一种数据结构。他是把一对（key，
value）通过key的哈希值来映射到数组中的，也就是说，它通过把关键码值映射到表中一个位置
来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。最常见的代表就是我们的HashMap

它是做什么用的？

Maps 最著名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的（其键按字母顺序排列）。

特性：

• 键是唯一的（没有重复）；
• 抗碰撞性：应该很难找到具有相同键的两个不同输入；

 6.树

树是一个有n个有限的节点组成一个具有层次关系的集合，每个节点都有0个或者多个子节点，没有父节点的节点称为“根节点”，也就是说除了根节点以外每个节点都有父节点，并且有且只有一个。

树的种类比较多，有二叉树，红黑树，AV L树，B树，哈夫曼树，字典树等等。

甚至 堆 我们 也 可以 把 它看 成 是一 棵 树， 树 的 这么 多 种 类 中 ，我 们 最常 见 的 应该是 二 叉树了，下面我们来看一下他的结构。

二叉树：每个节点最多含有两个子树的树称为二叉树；

7.堆

通常情况下我们把堆看成是一棵完全二叉树。堆一般分为两种，一种是最大堆，一
种是最小堆。最大堆要求根节点的值即大于左子树的值，又大于右子树的值。 也 就
是说最大堆根节点的值是堆中最大的。最小堆根节点的值是堆中最小的， 前 面 我 们
讲堆排序的时候介绍过堆，实际上他就是数组结构，但因为数组中间有关联，所以
我们可以把它当做一棵完全二叉树来看，下面我们再来看一下堆的数据结构是什么
样的。

 

结点中的数字是数组元素的下标，不是数组元素的值。所以如果我们知道父节
点的下标我们就可以知道他的两个子节点（如果有子节点），如果知道子节点
的下标也一定能找到父节点的下标，他们的关系是：
父节点的下标=（子节点下标-1）>>1；
左子节点下标=父节点下标*2+1；
右子节点下标=父节点下标*2+2；

堆的创建：

堆有两种，一种是最大堆，一种是最小堆。顾名思义，最大堆就是堆顶的元素是最大的，最小堆就是堆顶的元素是最小的。原理都差不多，我们只分析一个就行了，我 们 就 以 数 组 【 10 ， 4 ，8 ， 3 ， 5 ， 1 】 为 例 来 画 个 图 分 析 一 下 最 小 堆 是 怎 么 创 建的。

这 就 是 堆 的 创 建 ， 把 元 素 加 入 到 堆 中 的 时 候 ， 都 要 和 父 节 点 进 行 比 对 ， 在 最 小 堆中，如果比父节点小，就要和父节点交换，交换之后还要继续和再和新的父节点对比……。同理在最大堆中，如果比父节点大，就要和父节点交换。