​数据结构想必大家都不会陌生，对于一个成熟的程序员而言，熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合，特殊的结构在不同的应用场景中往往会带来不一样的处理效率。

常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的链表、栈、队列等，非线性结构包括树、图等。数据结构种类繁多，本文将通过图解的方式对常用的数据结构进行理论上的介绍和讲解，以方便大家掌握常用数据结构的基本知识。

本文提纲：

 1  数组

数组可以说是最基本最常见的数据结构。数组一般用来存储相同类型的数据，可通过数组名和下标进行数据的访问和更新。数组中元素的存储是按照先后顺序进行的，同时在内存中也是按照这个顺序进行连续存放。数组相邻元素之间的内存地址的间隔一般就是数组数据类型的大小。

 2  链表

链表相较于数组，除了数据域，还增加了指针域用于构建链式的存储数据。链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问，使得链表的自由度更高。

这表现在对节点进行增加和删除时，只需要对上一节点的指针地址进行修改，而无需变动其它的节点。不过事物皆有两极，指针带来高自由度的同时，自然会牺牲数据查找的效率和多余空间的使用。

一般常见的是有头有尾的单链表，对指针域进行反向链接，还可以形成双向链表或者循环链表。

链表和数组对比

链表和数组在实际的使用过程中需要根据自身的优劣势进行选择。链表和数组的异同点也是面试中高频的考察点之一。这里对单链表和数组的区别进行了对比和总结。

 3  跳表

从上面的对比中可以看出，链表虽然通过增加指针域提升了自由度，但是却导致数据的查询效率恶化。特别是当链表长度很长的时候，对数据的查询还得从头依次查询，这样的效率会更低。跳表的产生就是为了解决链表过长的问题，通过增加链表的多级索引来加快原始链表的查询效率。这样的方式可以让查询的时间复杂度从O(n)提升至O(logn)。

跳表通过增加的多级索引能够实现高效的动态插入和删除，其效率和红黑树和平衡二叉树不相上下。目前redis和levelDB都有用到跳表。

从上图可以看出，索引级的指针域除了指向下一个索引位置的指针，还有一个down指针指向低一级的链表位置，这样才能实现跳跃查询的目的。

 

 4  栈

栈是一种比较简单的数据结构，常用一句话描述其特性，后进先出。栈本身是一个线性表，但是在这个表中只有一个口子允许数据的进出。这种模式可以参考腔肠动物...即进食和排泄都用一个口...

栈的常用操作包括入栈push和出栈pop，对应于数据的压入和压出。还有访问栈顶数据、判断栈是否为空和判断栈的大小等。由于栈后进先出的特性，常可以作为数据操作的临时容器，对数据的顺序进行调控，与其它数据结构相结合可获得许多灵活的处理。

 

 5  队列

队列是栈的兄弟结构，与栈的后进先出相对应，队列是一种先进先出的数据结构。顾名思义，队列的数据存储是如同排队一般，先存入的数据先被压出。常与栈一同配合，可发挥最大的实力。

 6  树

树作为一种树状的数据结构，其数据节点之间的关系也如大树一样，将有限个节点根据不同层次关系进行排列，从而形成数据与数据之间的父子关系。常见的数的表示形式更接近“倒挂的树”，因为它将根朝上，叶朝下。

树的数据存储在结点中，每个结点有零个或者多个子结点。没有父结点的结点在最顶端，成为根节点；没有非根结点有且只有一个父节点；每个非根节点又可以分为多个不相交的子树。

这意味着树是具备层次关系的，父子关系清晰，家庭血缘关系明朗；这也是树与图之间最主要的区别。

别看树好像很高级，其实可看作是链表的高配版。树的实现就是对链表的指针域进行了扩充，增加了多个地址指向子结点。同时将“链表”竖起来，从而凸显了结点之间的层次关系，更便于分析和理解。

树可以衍生出许多的结构，若将指针域设置为双指针，那么即可形成最常见的二叉树，即每个结点最多有两个子树的树结构。二叉树根据结点的排列和数量还可进一度划分为完全二叉树、满二叉树、平衡二叉树、红黑树等。

完全二叉树：除了最后一层结点，其它层的结点数都达到了最大值；同时最后一层的结点都是按照从左到右依次排布。

满二叉树：除了最后一层，其它层的结点都有两个子结点。

平衡二叉树

平衡二叉树又被称为AVL树，它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉排序树：是一棵空树，或者：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

树的高度：结点层次的最大值

平衡因子：左子树高度 - 右子树高度

二叉排序树意味着二叉树中的数据是排好序的，顺序为左结点<根节点<右结点，这表明二叉排序树的中序遍历结果是有序的。（还不懂二叉树四种遍历方式[前序遍历、中序遍历、后序遍历、层序遍历]的同学赶紧补习！）

平衡二叉树的产生是为了解决二叉排序树在插入时发生线性排列的现象。由于二叉排序树本身为有序，当插入一个有序程度十分高的序列时，生成的二叉排序树会持续在某个方向的字数上插入数据，导致最终的二叉排序树会退化为链表，从而使得二叉树的查询和插入效率恶化。

 

平衡二叉树的出现能够解决上述问题，但是在构造平衡二叉树时，却需要采用不同的调整方式，使得二叉树在插入数据后保持平衡。主要的四种调整方式有LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。这里先给大家介绍下简单的单旋转操作，左旋和右旋。LR和RL本质上只是LL和RR的组合。

在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改，当平衡因子大于1时，就需要进行平衡化处理。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点，如果这三个结点在一条直线上，则采用单旋转进行平衡化，如果这三个结点位于一条折线上，则采用双旋转进行平衡化。

左旋：S为当前需要左旋的结点，E为当前结点的父节点。

左旋的操作可以用一句话简单表示：将当前结点S的左孩子旋转为当前结点父结点E的右孩子，同时将父结点E旋转为当前结点S的左孩子。可用动画表示：

右旋：S为当前需要左旋的结点，E为当前结点的父节点。右单旋是左单旋的镜像旋转。

左旋的操作同样可以用一句话简单表示：将当前结点S的左孩子E的右孩子旋转为当前结点S的左孩子，同时将当前结点S旋转为左孩子E的右孩子。可用动画表示：

红黑树

平衡二叉树（AVL）为了追求高度平衡，需要通过平衡处理使得左右子树的高度差必须小于等于1。高度平衡带来的好处是能够提供更高的搜索效率，其最坏的查找时间复杂度都是O(logN)。但是由于需要维持这份高度平衡，所付出的代价就是当对树种结点进行插入和删除时，需要经过多次旋转实现复衡。这导致AVL的插入和删除效率并不高。

为了解决这样的问题，能不能找一种结构能够兼顾搜索和插入删除的效率呢？这时候红黑树便申请出战了。

红黑树具有五个特性：

1. 每个结点要么是红的要么是黑的。

2. 根结点是黑的。

3. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。

4. 如果一个结点是红的，那么它的两个儿子都是黑的。

5. 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

红黑树通过将结点进行红黑着色，使得原本高度平衡的树结构被稍微打乱，平衡程度降低。红黑树不追求完全平衡，只要求达到部分平衡。这是一种折中的方案，大大提高了结点删除和插入的效率。C++中的STL就常用到红黑树作为底层的数据结构。

红黑树VS平衡二叉树

除了上面所提及的树结构，还有许多广泛应用在数据库、磁盘存储等场景下的树结构。比如B树、B+树等。这里就先不介绍了诶，下次在讲述相关存储原理的时候将会着重介绍。（其实是因为懒）

 7  堆

了解完二叉树，再来理解堆就不是什么难事了。堆通常是一个可以被看做一棵树的数组对象。堆的具体实现一般不通过指针域，而是通过构建一个一维数组与二叉树的父子结点进行对应，因此堆总是一颗完全二叉树。

对于任意一个父节点的序号n来说（这里n从0算），它的子节点的序号一定是2n+1，2n+2，因此可以直接用数组来表示一个堆。

不仅如此，堆还有一个性质：堆中某个节点的值总是不大于或不小于其父节点的值。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆常用来实现优先队列，在面试中经常考的问题都是与排序有关，比如堆排序、topK问题等。由于堆的根节点是序列中最大或者最小值，因而可以在建堆以及重建堆的过程中，筛选出数据序列中的极值，从而达到排序或者挑选topK值的目的。

 

 8  散列表

散列表也叫哈希表，是一种通过键值对直接访问数据的机构。在初中，我们就学过一种能够将一个x值通过一个函数获得对应的一个y值的操作，叫做映射。散列表的实现原理正是映射的原理，通过设定的一个关键字和一个映射函数，就可以直接获得访问数据的地址，实现O(1)的数据访问效率。在映射的过程中，事先设定的函数就是一个映射表，也可以称作散列函数或者哈希函数。

散列表的实现最关键的就是散列函数的定义和选择。一般常用的有以下几种散列函数：

直接寻址法：取关键字或关键字的某个线性函数值为散列地址。

数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。

平方取中法：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。

取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。

除留取余法：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n。

确定好散列函数之后，通过某个key值的确会得到一个唯一的value地址。但是却会出现一些特殊情况。即通过不同的key值可能会访问到同一个地址，这个现象称之为冲突。

冲突在发生之后，当在对不同的key值进行操作时会使得造成相同地址的数据发生覆盖或者丢失，是非常危险的。所以在设计散列表往往还需要采用冲突解决的办法。

常用的冲突处理方式有很多，常用的包括以下几种：

开放地址法（也叫开放寻址法）：实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。

再哈希法：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。

链地址法：链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的。

公共溢出区：这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。

目前比较常用的冲突解决方法是链地址法，一般可以通过数组和链表的结合达到冲突数据缓存的目的。

左侧数组的每个成员包括一个指针，指向一个链表的头。每发生一个冲突的数据，就将该数据作为链表的节点链接到链表尾部。这样一来，就可以保证冲突的数据能够区分并顺利访问。

考虑到链表过长造成的问题，还可以使用红黑树替换链表进行冲突数据的处理操作，来提高散列表的查询稳定性。

 

 9  图

图相较于上文的几个结构可能接触的不多，但是在实际的应用场景中却经常出现。比方说交通中的线路图，常见的思维导图都可以看作是图的具体表现形式。

图结构一般包括顶点和边，顶点通常用圆圈来表示，边就是这些圆圈之间的连线。边还可以根据顶点之间的关系设置不同的权重，默认权重相同皆为1。此外根据边的方向性，还可将图分为有向图和无向图。

图结构用抽象的图线来表示十分简单，顶点和边之间的关系非常清晰明了。但是在具体的代码实现中，为了将各个顶点和边的关系存储下来，却不是一件易事。

邻接矩阵

目前常用的图存储方式为邻接矩阵，通过所有顶点的二维矩阵来存储两个顶点之间是否相连，或者存储两顶点间的边权重。

无向图的邻接矩阵是一个对称矩阵，是因为边不具有方向性，若能从此顶点能够到达彼顶点，那么彼顶点自然也能够达到此顶点。此外，由于顶点本身与本身相连没有意义，所以在邻接矩阵中对角线上皆为0。

有向图由于边具有方向性，因此彼此顶点之间并不能相互达到，所以其邻接矩阵的对称性不再。

用邻接矩阵可以直接从二维关系中获得任意两个顶点的关系，可直接判断是否相连。但是在对矩阵进行存储时，却需要完整的一个二维数组。若图中顶点数过多，会导致二维数组的大小剧增，从而占用大量的内存空间。

而根据实际情况可以分析得，图中的顶点并不是任意两个顶点间都会相连，不是都需要对其边上权重进行存储。那么存储的邻接矩阵实际上会存在大量的0。虽然可以通过稀疏表示等方式对稀疏性高的矩阵进行关键信息的存储，但是却增加了图存储的复杂性。

因此，为了解决上述问题，一种可以只存储相连顶点关系的邻接表应运而生。

邻接表

在邻接表中，图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点。相较于无向图，有向图的情况更为复杂，因此这里采用有向图进行实例分析。

在邻接表中，每一个顶点都对应着一条链表，链表中存储的是顶点能够达到的相邻顶点。存储的顺序可以按照顶点的编号顺序进行。比如上图中对于顶点B来说，其通过有向边可以到达顶点A和顶点E，那么其对应的邻接表中的顺序即B->A->E，其它顶点亦如此。

通过邻接表可以获得从某个顶点出发能够到达的顶点，从而省去了对不相连顶点的存储空间。然而，这还不够。对于有向图而言，图中有效信息除了从顶点“指出去”的信息，还包括从别的顶点“指进来”的信息。这里的“指出去”和“指进来”可以用出度和入度来表示。

入度：有向图的某个顶点作为终点的次数和。

出度：有向图的某个顶点作为起点的次数和。

由此看出，在对有向图进行表示时，邻接表只能求出图的出度，而无法求出入度。这个问题很好解决，那就是增加一个表用来存储能够到达某个顶点的相邻顶点。这个表称作逆邻接表。

逆邻接表

逆邻接表与邻接表结构类似，只不过图的顶点链接着能够到达该顶点的相邻顶点。也就是说，邻接表时顺着图中的箭头寻找相邻顶点，而逆邻接表时逆着图中的箭头寻找相邻顶点。

邻接表和逆邻接表的共同使用下，就能够把一个完整的有向图结构进行表示。可以发现，邻接表和逆邻接表实际上有一部分数据时重合的，因此可以将两个表合二为一，从而得到了所谓的十字链表。

十字链表

十字链表似乎很简单，只需要通过相同的顶点分别链向以该顶点为终点和起点的相邻顶点即可。

但这并不是最优的表示方式。虽然这样的方式共用了中间的顶点存储空间，但是邻接表和逆邻接表的链表节点中重复出现的顶点并没有得到重复利用，反而是进行了再次存储。因此，上图的表示方式还可以进行进一步优化。

十字链表优化后，可通过扩展的顶点结构和边结构来进行正逆邻接表的存储：（下面的弧头可看作是边的箭头那端，弧尾可看作是边的圆点那端）

data：用于存储该顶点中的数据；

firstin指针：用于连接以当前顶点为弧头的其他顶点构成的链表，即从别的顶点指进来的顶点；

firstout指针：用于连接以当前顶点为弧尾的其他顶点构成的链表，即从该顶点指出去的顶点；

边结构通过存储两个顶点来确定一条边，同时通过分别代表这两个顶点的指针来与相邻顶点进行链接：

tailvex：用于存储作为弧尾的顶点的编号；

headvex：用于存储作为弧头的顶点的编号；

headlink 指针：用于链接下一个存储作为弧头的顶点的节点；

taillink 指针：用于链接下一个存储作为弧尾的顶点的节点；

以上图为例子，对于顶点A而言，其作为起点能够到达顶点E。因此在邻接表中顶点A要通过边AE（即边04）指向顶点E，顶点A的firstout指针需要指向边04的tailvex。同时，从B出发能够到达A，所以在逆邻接表中顶点A要通过边AB（即边10）指向B，顶点A的firstin指针需要指向边10的弧头，即headlink指针。依次类推。

十字链表采用了一种看起来比较繁乱的方式对边的方向性进行了表示，能够在尽可能降低存储空间的情况下增加指针保留顶点之间的方向性。具体的操作可能一时间不好弄懂，建议多看几次上图，弄清指针指向的意义，明白正向和逆向邻接表的表示。

 

 10  总结

数据结构博大精深，没有高等数学的讳莫如深，也没有量子力学的玄乎其神，但是其在计算机科学的各个领域都具有强大的力量。本文试图采用图解的方式对九种数据结构进行理论上的介绍，但是其实这都是不够的。

即便是简单的数组、栈、队列等结构，在实际使用以及底层实现上都会有许多优化设计以及使用技巧，这意味着还需要真正把它们灵活的用起来，才能够算是真正意义上的熟悉和精通。但是本文可以作为常见数据结构的一个总结，当你对某些结构有些淡忘的时候，不妨重新回来看看。

------------

感兴趣可微信搜索【业余码农】，阅读更多技术干货！

   最近在做一个公司的管理系统，涉及到很多表格数据的展示，就需要做分页，这时通常有两种方式，一种是前端一次请求获取全部数据，前端再对数据做分页，这种方式如果数据规模比较小的情况下可以使用，如果数据量较大，对内存、网络传输的消耗都是非常大的，所以实际开发中一般很少使用。另外一种方式是前端在请求时将分页信息传给后端，后端查询时进行分页，并将相应的分页数据返回给前端，而后端分页的实现又可以分为逻辑分页和物理分页，逻辑分页就是在进行数据库查询时一次性将数据查出来，然后将相应页的数据筛选出来返回，很明显逻辑分页跟第一种前端分页的方式有着相同的弊端。物理分页就是在查数据库时就查询相应页的数据(比如直接在mysql查询语句中添加limit)。

   mybatis原生也支持分页，但为了与数据库语法解耦，实现的是逻辑分页，首先将所有结果查询出来，然后通过计算offset和limit，来返回部分结果，操作在内存中进行，所以也叫内存分页，Mybatis逻辑分页是通过RowBounds实现的。而物理分页一般是通过为sql添加limit实现的，本文主要讲解物理分页，通过改造mapper.xml文件添加limit的方式实现。

sql添加limit实现物理分页

1.用户持久化类

package com.test.po;

import java.util.Date;

/**
* 用户持久化类
*
* @author  xxx
* @version 1.0
*/

public class User {
    /*
    * 用户ID
    */
    private String userId;

   /*
   * 用户名
   */
   private String userName;

   /*
   * IP地址
   */
   private String ip;

   /*
   * 用户角色
   */
   private int roleNum;
   
   /*
   * 创建时间
   */
   private Date createtime;

   /**
   * @return the userId
   */
   public String getUserId() {
     return userId;
   }

   /**
   * @param userId the userId to set
   */
   public void setUserId(String userId) {
      this.userId = userId;
   }

   /**
   * @return the userName
   */
   public String getUserName() {
      return userName;
   }

   /**
   * @param userName the userName to set
   */
   public void setUserName(String userName) {
      this.userName = userName;
   }

   /**
   * @return the ip
   */
   public String getIp() {
     return ip;
   }

   /**
   * @param ip the ip to set
   */
   public void setIp(String ip) {
      this.ip = ip;
   }

   /**
   * @return the roleNum
   */
   public int getRoleNum() {
      return roleNum;
   }

   /**
   * @param roleNum the roleNum to set
   */
   public void setRoleNum(int roleNum) {
      this.roleNum = roleNum;
   }

   /**
   * @return the createtime
   */
   public Date getCreatetime() {
      return createtime;
   }

   /**
   * @param createtime the createtime to set
   */
   public void setCreatetime(Date createtime) {
      this.createtime = createtime;
   }
}

2.mapper.xml

<!-- 分页获取用户列表 -->
    <resultMap id="userEntity" type="com.test.po.User"></resultMap>
    <resultMap id="userTotalCount" type="int"></resultMap>
    <select id="getUserList" parameterType="hashmap" resultMap="userEntity,userTotalCount">
       SELECT sql_calc_found_rows
              user_id as userId, 
              user_name as userName,
              ip,
              role_num as roleNum,
              createtime,  
        FROM tb_test_user
        ORDER BY user_id ASC limit #{curCount,jdbcType=INTEGER},#{pageSize,jdbcType=INTEGER};
        <!-- 查询数量 --> 
        select found_rows() as userTotalCount;  
    </select>

3.Service层 用户管理类

package com.test.service;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

import org.mybatis.spring.SqlSessionTemplate;
import org.springframework.beans.factory.annotation.Autowired;

import com.alibaba.fastjson.JSONObject;
import com.test.po.User;

/**
*
* 用户管理Service
*
* @author xxx
* @version 1.0
*/
@Service
public class UserService {

    @Autowired
    private SqlSessionTemplate sqlSessionTemplate;

    public SqlSessionTemplate getSqlSessionTemplate() {
        return sqlSessionTemplate;
    }

    public void setSqlSessionTemplate(SqlSessionTemplate sqlSessionTemplate) {
        this.sqlSessionTemplate = sqlSessionTemplate;
    }

    /**
    * 按分页列出用户
    *
    * @param param
    * @return
    */
    public JSONObject listUsers(int pageNum, int pageSize) {
        Map<String, Object> paramMap = new HashMap<>();
        paramMap.put("curCount", (pageNum - 1) * pageSize);
        paramMap.put("pageSize", pageSize);

        List<List<?>> list = this.nlpwebSqlSessionTemplate.selectList("getUserList", paramMap);

        JSONObject resultObject = new JSONObject();
        resultObject.put("totalCount",list.get(1).get(0));
        resultObject.put("dataList", list.get(0));

        return resultObject;
    }
}

https://www.toutiao.com/a6649963989537128967/

 

2019-01-24 15:36:35

国外 IT 教育学院 Educative.io 创始人 Fahim ul Haq 写过一篇过万赞的文章《The top data structures you should know for your next coding interview》,总结了程序员面试中需要掌握的 8 种数据结构知识。

Fahim ul Haq 曾在 Facebook 和微软任职，面试过不少程序员，所以这篇文章还是值得参考的。以下内容编译自他的这篇《准备下次编程面试前你应该知道的数据结构》：

准备下次编程面试前你应该知道的数据结构

瑞典计算机科学家 Niklaus Wirth 在 1976 年写了一本书，叫作《Algorithms + Data Structures = Programs》（算法+数据结构=程序）。

即便在 40 年后的今天，这条等式仍然成立。这也是为何程序员求职者应该向面试官展示出已经透彻理解了数据结构知识。

几乎所有的面试问题都要求求职者表现出已经熟练掌握数据结构，不管你是刚毕业的应届生还是工作了多年的老手，都是这样。

有时，面试问题会明确提到数据结构，比如“给定一个二叉树”；有时则比较含蓄，比如“我们想追踪和每位作者相关的书籍数量。”

学习数据结构知识很有必要，哪怕你只是想找份比现在的工作更好的一份差事。我们首先了解数据结构的基本知识。

什么是数据结构？

简单说，数据结构就是一个容器，以某种特定的布局存储数据。这个“布局”使得数据结构在某些操作上非常高效，在另一些操作上则不那么高效。你的目标就是理解数据结构，这样就能为手头的问题选择最优的数据结构。

为什么我们需要数据结构？

由于数据结构用来以有组织的形式存储数据，而且数据是计算机科学中最重要的实体，因此数据结构的真正价值显而易见。

无论你解决什么问题，你都必须以这种或那种方式处理数据比如员工的工资，股票价格，购物清单，甚至简单的电话簿等等。

根据不同的场景，数据需要以特定格式存储。目前有一些数据结构可以满足我们以不同格式存储数据的需求。

常用的数据结构

我们首先列出最常用的数据结构，然后再挨个讲解：

• 数组
• 堆栈
• 队列
• 链表
• 树
• 图
• 字典树
• 哈希表

数组

数组是一种最简单和最广泛使用的数据结构，其它数据结构比如堆栈和队列都源自数组。

下图是一个大小为 4 的简单数组，包含几个元素（ 1 , 2 , 3，4）。

数组

每个数据元素会被分配一个正的数值，叫作“索引”，它对应该元素在数组中的位置。大部分编程语言都将初始索引定义为 0.

以下是两种数组：

• 一维数组（如上所示）
• 多维数组（数组的数组）

数组的基本操作：

• Insert——在给定索引位置插入一个元素
• Get——返回给定索引位置的元素
• Delete——删除给定索引位置的元素
• Size——获取数组内所有元素的总数

常问的数组面试问题：

• 找到数组中第二小的元素
• 找到数组中第一个没有重复的整数
• 合并两个分类数组
• 重新排列数组中的正值和负值

堆栈

我们都熟悉很有名的撤销（Undo）选项，它几乎存在每个应用程序中。有没有想过它是如何工作的？其思路就是，按照最后的状态排列在先的顺序将工作的先前状态（限于特定数字）存储在内存中。这只用数组是无法实现的，因此堆栈就有了用武之地。

可以把堆栈看作一堆垂直排列的书籍。为了获得位于中间位置的书，你需要拿掉放在它上面的所有书籍。这就是 LIFO（后进先出）方法的工作原理。

这是一个包含三个数据元素（1,2 和 3）的堆栈图像，其中3位于顶部，首先把它删除：

堆栈

堆栈的基本操作：

• Push——在顶部插入元素
• Pop—— 从堆栈中删除后返回顶部元素
• isEmpty——如果堆栈为空，则返回 true
• Top ——返回顶部元素，但不从堆栈中删除

常见的堆栈面试问题：

• 使用堆栈计算后缀表达式
• 对堆栈中的值进行排序
• 检查表达式中的括号是否平衡

队列

与堆栈类似，队列是另一种线性数据结构，以顺序方式存储元素。堆栈和队列之间唯一的显着区别是，队列不是使用 LIFO 方法，而是应用 FIFO 方法，这是 First in First Out（先入先出）的缩写。

队列的完美现实例子：一列人在售票亭等候。如果有新人来，他们是从末尾加入队列，而不是在开头——站在前面的人将先买到票然后离开队列。

下图是一个包含四个数据元素（1,2,3 和 4）的队列，其中 1 位于顶部，首先把它删除：

队列

队列的基本操作：

• Enqueue() —— 向队列末尾插入元素
• Dequeue() —— 从队列头部移除元素
• isEmpty() —— 如果队列为空，则返回 true
• Top() —— 返回队列的第一个元素

常问的队列面试问题：

• 使用队列来实现堆栈
• 颠倒队列中前 k 个元素的顺序
• 使用队列生成从 1 到 n 的二进制数

链表

链表是另一个重要的线性数据结构，刚一看可能看起来像数组，但在内存分配，内部结构以及如何执行插入和删除的基本操作方面有所不同。

链表就像一个节点链，其中每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针，指向链表的第一个元素，如果列表是空的，那么它只指向 null 或不指向任何内容。

链表用于实现文件系统，哈希表和邻接表。下图是链表内部结构的直观展示：

链表

下面是几种类型的链表：

• 单链表（单向）
• 双链表（双向）

链表的基本操作：

• InsertAtEnd —— 在链表末尾插入指定元素
• InsertAtHead —— 在链表头部插入指定元素
• Delete —— 从链表中删除指定元素
• DeleteAtHead —— 删除链表的第一个元素
• Search —— 返回链表中的指定元素
• isEmpty —— 如果链表为空，返回 true

常问的链表面试问题：

• 翻转列表
• 检测链表中的循环
• 返回链表中倒数第 n 个节点
• 移除链表中的重复值

图

图就是一组节点，以网络的形式互相连接。节点也被称为顶点（vertices）。一对（x,y）就叫做一个边，表示顶点 x 和顶点 y 相连。一个边可能包含权重/成本，显示从顶点 x 到 y 所需的成本。

图

图的类型：

• 无向图
• 有向图

在编程语言中，图可以表示为两种形式：

• 邻接矩阵
• 邻接列表

常见的图遍历算法：

• 广度优先搜索
• 深度优先搜索

常问的图面试问题：

• 实现广度优先搜索和深度优先搜索
• 检查一个图是否为树
• 计算一张图中的边的数量
• 找到两个顶点之间的最短路径

树

树是一种层级数据结构，包含了连接它们的顶点（节点）和边。树和图很相似，但二者有个很大的不同点，即树中没有循环。

树广泛应用在人工智能和复杂的算法中，为解决各种问题提供高效的存储机制。

下图是一个简单的树，以及在树型数据结构中所用的基本术语：

树

下面是几种类型的树：

• N 叉树
• 平衡树
• 二叉树
• 二叉搜索树
• 平衡二叉树
• 红黑树
• 2-3 树

其中，二叉树和二叉搜索树是最常用的树。

常问的树面试问题：

• 找到一个二叉树的高度
• 找到一个二叉搜索树中第 k 个最大值
• 找到距离根部“k”个距离的节点
• 找到一个二叉树中给定节点的祖先（ancestors）

字典树

字典树，也叫“前缀树”，是一种树形结构，在解决字符串相关问题中非常高效。其提供非常快速的检索功能，常用于搜索字典中的单词，为搜索引擎提供自动搜索建议，甚至能用于IP路由选择。

下面展示了“top”“thus”和“their”这三个词是如何存储在字典树中的：

字典树

这些单词以从上到下的方式存储，其中绿色节点“p”，“s”和“r”分别表示“top”，“thus”和“their”的末尾。

常见的字典树面试问题：

• 计算字典树中的总字数
• 打印存储在字典树中的所有单词
• 使用字典树对数组的元素进行排序
• 使用字典树从字典中形成单词
• 构建一个T9字典

哈希表

散列是一个用于唯一标识对象并在一些预先计算的唯一索引（称为“密钥”）存储每个对象的过程。因此，对象以“键值”对的形式存储，这些项的集合被称为“字典”。可以使用该键值搜索每个对象。有多种不同的基于哈希的数据结构，但最常用的数据结构是哈希表。

哈希表通常使用数组实现。

哈希数据结构的性能取决于以下三个因素：

• 哈希函数
• 哈希表的大小
• 碰撞处理方法

下图展示了如何在数组中映射哈希。该数组的索引是通过哈希函数计算的。

哈希表

常问的哈希面试问题：

• 找到数组中的对称对
• 追踪遍历的完整路径
• 查看一个数组是否为另一个数组的子集
• 检查给定数组是否不相交

以上就是你在准备编程面试前需要掌握的8种数据结构。

在上面的 8 种数据结构中，每种结构都有对应的面试问题，接下来的一段时间我会将这三十一道问题依旧使用动画的形式解析清楚。