一文十三张图带你彻底了解所有数据结构

一段回忆

曾几何时，我是一个懵懵懂懂的写CRUD写到飞起的小菜鸟，当时我最大的优势就是业务bug比别人要少，总是很多人夸我细心耐心，也能得到别人的赏识。可是我自己从来没有成就感，总是觉得内心缺少了点什么，总是觉得身边这个是大神，那个也是大神，总是感觉自己在仰望着别人，我不想在浑浑噩噩间变成一只老菜鸟，我也希望自己能发点光，也能点亮一点别人的道路。

以前提到数据结构，提到源码等这些，我总是一脸羡慕的看着别人侃侃而谈，其实心里也想变成那样的人，可是真要去学又总是给自己找各种各样的理由去推脱，还有就是潜意识里觉得那些知识高深莫测且枯燥，我能学会吗？逃避着、恐惧着。

直到18年的某一场面试，从头到尾都聊的非常好，薪资也谈的差不多，最后别人忽然想起来问我熟不熟悉数据结构，常见的数据结构有哪些，能不能手写一个出来，至今都记得那是一次多么羞愧的否认三连，不熟悉不清楚不会写。那人笑着跟我说没关系，就是回去后再也没等到通知。

消除恐惧的最好办法就是面对恐惧，知耻而后勇，回去后我就下定决心要让数据结构存在我的技能库里，不要再次成为我的软肋，没想到真正去面对数据结构学习的时候，发现它并没有那么难，反而在学习的过程中有种醍醐灌顶的感觉，好像知道自己以前的空虚和不自信来自哪里了，好像感觉到我与大神的区别在哪里了。

提到这一茬，是因为我在csdn立了flag，要写一个数据结构的系列文章，中间又懒惰了几天，今天正式敲键盘前，想起了那段记忆，没想到被自己写下来竟有种看网课的感觉，哈哈，话不多说了，如果你有共鸣，那么就让我带着一起解锁新的姿势吧，呸，解锁新技能之——设计模式。

什么是数据结构？

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

上面是百度百科的定义，通常情况下，我们说的数据结构可以理解成是指一组数据的存储结构。

image

如上图所示，数据是存储在计算机的内存里的，在存储时，决定了数据顺序和位置关系的便是“数据结构”。 如果你还不明白什么是数据结构的话，我再来举个生活中的例子，在手机没有出现之前我们存电话号码都是在笔记本上手抄，这样每次新记一个电话号码都是在最后一行后面加，然后找的时候就需要在所有的号码中找某一个，查找很不方便。

image

后来当有了手机之后，你们再看，你每次添加一个新联系人时，系统会根据你的存的人名的姓氏拼音首字母自动加到姓氏那一组，当你要查找某一个人的时候，你可以搜索，也可以直接点击右边的首字母去查找，效率大大提高，微信联系人的存储结构也是这样，你们可以看一下。 举这个例子，是要你明白两件事，第一个就是电话号码存在笔记本或者存在手机上，这种存储结构的顺序和位置关系就是“数据结构”。选择合适的数据结构，不但可以提高内存的使用率，也可以提高查找的效率。查找效率就是指算法，数据结构是为算法而生，当然我们这里主要讲数据结构，所以算法就不展开多说了。

数据结构分类

数据结构分为逻辑结构和物理结构。

• 逻辑结构：指数据元素之间逻辑关系的数据结构，这里的逻辑关系是指数据元素之间的前后间关系，与数据在计算机中的存储位置无关。

• 物理结构：指数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构，也叫做存储结构。

数据的逻辑结构主要分为线性结构和非线性结构。

• 线性结构：数据结构的元素之间存在一对一线性关系，所有结点都最多只有一个直接前趋结点和一个直接后继结点。常见的有数组、队列、链表、栈。

• 非线性结构：各个结点之间具有多个对应关系，一个结点可能有多个直接前趋结点和多个直接后继结点。常见的有多维数组、广义表、树结构和图结构等。

数据的物理结构（以后我都统一称存储结构），表示数据元素之间的逻辑关系，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有：

• 顺序存储：存储顺序是连续的，在内存中用一组地址连续的存储单元依次存储线性表的各个数据元素。

• 链式存储：在内存中的存储元素不一定是连续的，用任意地址的存储单元存储元素，元素节点存放数据元素以及通过指针指向相邻元素的地址信息。

• 索引存储：除建立存储结点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。

• 散列存储：又称Hash存储，由节点的关键码值决定节点的存储地址。

常用的数据结构

• 数组（Array）
• 队列（Queue）
• 链表（Linked List）
• 栈（Stack）
• 树（Tree）
• 散列表（Hash）
• 堆（Heap）
• 图（Graph）

下面我们来先对这几个数据结构有个大概的印象。

数组（Array）

数组是最简单、使用最频繁的一种数据结构。它一种线性表数据结构，用一组连续的内存空间来存储一组相同类型的数据。

image

如上图所示，数据是按照顺序存储在内存的连续空间内，arr后面的[]代表下标，由于数据是存储在连续空间内的，所以每个数据的内存地址(在内存上的位置)都可以通过数组下标计算出来，从而可以直接访问目标数据，达到随机访问的目的。

队列（Queue）

队列也是一种非常基础的数据结构，其特点是先入先出，也就是我们常听到的FIFO（First in First Out），即操作数据是从两端进行的。

image

上图就是生活中常见的使用队列场景，为了更方便大家理解，我再画一个入队列，出队列的示意图，加深大家对队列的印象。

image

链表（Linked List）

链表是一种物理存储单元上非连续，非顺序的存储结构。链表有一系列节点组成，所谓节点就是指链表中的每一个元素，每个节点包含两个数据，一个是存储元素的数据域（值），另一个是存储下一个节点地址的指针域。

image

通俗点说，链表数据一般都是分散存储于内存中 的，无须存储在连续空间内。这样大家可能还不能直观的感受链表的非连续，我再画一张图：

image

假设上图中100-108是一块内存中连续地址的内存分布，假设101、103、106、107这几个内存地址都已经存储数据了，那剩下的100、102、104、105、108是不是就浪费呢，答案是否定的，我们可以使用链表的方式存储数据。

栈（Stack）

栈也是一种数据呈线性排列的数据结构，和上面的队列相反，栈的特点先进后出、后进先出，就是常说的LIFO（Last in First Out）。

作者大学毕业时去当了两年兵，在部队里面给弹匣装子弹时就类似栈的入栈操作，射击时相当于出栈操作。（为了证明我拿过真枪，放一张作者当年的靓照给你们欣赏一下，哈哈。不过你们也不用着急，如果你们玩过玩具枪，应该也能稍微感受一下，嘿嘿）

image

防止大家嫉妒我的容颜，还是画图来说明一下栈的入栈出栈操作。

image

树（Tree）

树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。

数的结构特点是：

• 每个节点有零个或多个子节点；

• 没有父节点的节点称为根节点；

• 每一个非根节点有且只有一个父节点；

• 除了根节点外，每个子节点可以分为多个不相交的子树。

我们平时用到最多的就是二叉树，我也以二叉树来为例，先看一下树结构：

image

二叉树有几下特点：

• 每个结点最多有两颗子树，结点的度最大为2。

• 左子树和右子树是有顺序的，次序不能颠倒。

• 即使某结点只有一个子树，也要区分左右子树。

• 个结点的值均大于其左子树上任意一个结点的值。比如 点的值。结点100大于其左子树上的30，18和16。

• 每个结点的值均小于其右子树上任意 一个结点的值。比如结点 100 小于其右子树上的 120、130 和 135。

散列表（Hash）

散列表又叫哈希表，存储的是由键(key)和值(value)组 成的数据，根据键直接访问存储在内存存储位置的数据结构。

image

从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。哈希表查找数据的公式为：记录的存储位置=f(key)这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。我们将在后面详细讲解哈希表数据结构。

堆（Heap）

堆比较特殊，是一种图的树形结构。被用于实现“优先队列”(priority queues)，优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺 序取出。在堆的树形结构中，各个顶点被称为“结点”(node)，数据就存储在这些结点中。

只要满足下面两个特点的树形结构就是堆：

• 堆是一个完全二叉树（所谓完全二叉树就是除了最后一层其他层的节点个数都是满的）。

• 堆中每一个节点的值都必须大于等于或者小于其子树中每一个节点的值。

下面我们看一下堆的结构：

image

上面其实叫大顶堆，如果每一个节点小于子树中每个节点的值，那就叫小顶堆。

图（Graph）

图是相对复杂的一种数据结构，由顶点和连接每对顶点的边所构成的图形就是图。

我们先来看图：

image

上图中的圆圈叫作“顶点”(Vertex，也叫“结点”)，连接顶点的线叫作“边”（Edge）。也就是说，由顶点和连接每对顶点的边所构成的图形就是图。 图按照顶点指向的方向可分为无向图和有向图，像我上面的就叫无向图。 图在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。常见的图遍历算法就是广度优先算法和深度优先算法。

总结

好了，上面我们用图形并茂的方式介绍了什么是数据结构以及常用的数据结构，相信你对这些数据结构的概念已经有了一点粗略的印象。后面的文章我将对每一种数据结构展开进行详细的讲解，并教你怎样手写实现这些数据结构。

原创不易，如果你觉得本文还不错的话，还麻烦您帮忙点个在看，或者帮忙转发一下，这比夸我帅或者给我钱还更让我激动，谢谢大家！