程序员必须知道的7种数据结构

大家好，我是渔夫子。今天跟大家简单介绍几种常见的数据结构。

数据结构是计算机中用于组织和存储数据的一种方式，其目的是为了提高相关数据操作的效率。在几乎所有的程序或软件系统中都会用到数据结构。而且数据结构也是计算机科学和软件工程的基础。同时在面试时也是一个必考的知识点。因此，作为开发人员，必须要掌握数据结构相关的知识。

本文就简单介绍一下每个程序员必须要掌握的7种常见的数据结构。

01 数组

数组是用一组连续的内存空间,来存储一组具有相同类型的数据的结构，该空间具有固定的大小。所以其特点就是空间连续、数据类型相同、空间大小固定、可以进行随机访问。如下图：

数组的常用操作：

• 遍历：依次遍历元素并输出元素值
• 搜索：在数组中搜索某个元素是否存在。可以通过元素搜索，也可以通过索引下标搜索。
• 更新：更新一个给定索引位置处的已存在元素的值

因为数组的大小是固定的，所以从数组中插入和删除元素是不能直接完成的。必须要先分配一个新的数组空间。以插入一个元素到数组中为例，首先创建一个新的数组，该新数组的元素个数比原来数组的元素个数多1个。然后将原来数组中的元素依次拷贝到新数组中，最后将要插入的元素放到新数组的最后一个位置即可。删除操作也是同理。

数组结构的应用：

• 作为其他数据结构的底层结构。例如数组列表、堆、hash表等。
• 用于不同的排序算法。例如插入排序、快速排序、冒泡排序以及合并排序。

02 链表

链表是一种物理存储单元上非连续、非顺序的存储结构。链表由一系列的节点组成，每个节点之间是相互连接的。因此，在要想访问链表上的某个节点，必须从头开始依次查找，不能进行随机访问。这也是和数组的其中一个重要区别。链表提供了一种简单且灵活的动态结构。

在链表中需有以下几个术语：

• 链表中的每个元素称为节点
• 每个节点包含一个key和一个指向下一个节点的指针。key是该节点用来存放数据的，也叫数据区域。下一个节点指针通常用next表示，用来指向下一个节点的地址。
• 有一个head的指针，该指针指向链表的第一个节点。
• 有一个tail指针，该指针指向链表的最后一个节点。

一个单链表如下图所示：

链表会有以下变种类型：

• 单向链表：单向链表的遍历只能是从头儿到尾的顺序进行。
• 双向链表：可以从前后两个方向进行遍历。每个节点有两个指针：prev和next。分别指向自己的前驱和后继节点。
• 循环链表：循环链表指的是链表的头节点的前驱指针指向尾部节点。尾部节点的后继指针指向头部节点。

链表的常用操作

• 搜索：查找指定的节点，并返回指向该节点的指针。
• 插入：将一个节点插入到链表中。插入操作有三种形式：插入到链表的头部位置；插入到列表的尾部。插入到链表的中部。
• 删除：将一个节点从链表中移除。删除节点不能通过一步完成，删除后 需要将链表的前后节点再关联上。同样，删除操作也有3种不同的方式：删除链表的头节点，删除链表的尾部节点，删除链表的中间节点。

链表结构的应用

• 编译器中的符号表管理
• 通过Alt+Tab快捷键的程序切换（使用循环链表实现）

03 栈

栈是一种后进先出（后进入的元素先被访问）的结构，这种结果在很多编程语言中都很常见。该结构叫做“栈”，因为它看起来就像如下这样：

栈的常见操作

以下是栈额两个基本操作。可以结合下图一起理解：

• Push：将元素插入到栈顶
• Pop：从栈顶删除一个元素并返回

以下函数是用于检查栈状态的：

• Peek：返回栈顶元素但不从栈顶删除
• isEmpty：检查栈是否为空
• isFull：检查栈是否是满了

栈的应用

• 用于函数的调用栈
• 用于表达式的的解析计算（例如：用于解析数学表达式的运算，最简单的就是四则运算）

04 队列

队列是一种 先进先出（FIFO：First In First Out） 的数据结构。该结构叫做“队列”，因为跟现实世界中的队列类似：

队列的常见操作

• 入队（Enqueue）： 将一个元素插入到队列的队尾
• 出队（Dequeue）： 删除队列头部的元素

队列的应用

• 在多线程系统中管理线程
• 用于实现队列系统（例如：优先级队列）

05 哈希表

哈希表是一种通过1个key关联1个或多个value的数据结构，支持通过key高效的查找value值。因此，在插入和搜索操作上都是非常高效的。实际上可以将哈希表认为是数组和链表的

直接寻址方式（即数组）也是key-value的结果，但其key和value之间是一对一的映射方式存储数据。但是，当存在大量键值对时，这种方法就存在一个问题：随着存储的记录越来越多，底层存储表会变的越来越大。由于一台典型的计算机上的可用内存是有限的，记录越多，底层存储表就会变的很大，甚至无法将其全部存储。为了避免这个问题，我们使用哈希表。

哈希函数

用一个叫做哈希的函数来解决上述提到的直接寻址的问题。在直接寻址访问中，key-value对被存在索引k槽中（即数组中的索引）。使用hash函数，我们可以将key转换成整个表的索引位置。通过hash函数计算出来的key值被叫做hash值，该hash值代表着能够在底层数组中的索引位置。

h(k) = k % m

• h：哈希函数
• k：决定hash值的key
• m：哈希表的大小（即可用的槽数）。

假设哈希函数是h(k) = k % 20，这里20代表hash表的容量大小。给定一组key，我们就可以根据hansh函数计算出每个key的hash值，以决定应该将key存储在hash表的什么位置。比如我们有下列一组keys，那么其对应的hash值以及hash表索引位置如下：

• 1 -> 1 % 20 -> 1
• 5 -> 5 % 20 -> 5
• 23 -> 23 % 20 -> 3
• 63 -> 63 % 20 -> 3

从最后两个示例可以看到，哈希函数会对不同的key产生相同的哈希值，这被称作是hash冲突。hash冲突一般可以通过选择合适的hash函数以及拉链或开放寻址技术来解决。如果是通过拉链技术来解决哈希冲突，实际上哈希表就可以看做是数组和链表的组合应用。

哈希表的应用

• 用于实现数据库索引
• 用于实现关联数组
• 用于实现“集合”数据结构

06 树

树是一种层级结构，数据按层级存储并关联在一起。这种结构和链表不同，链表是线性存储的。即一个父节点最多只有一个子节点。而树则是一个节点可以有多个子节点，但一个子节点只能有一个父节点。

为了适应不同的应用程序和特定的约束，有很多种类型的树。比如二叉查找树、B-tree、红黑树、平衡二叉树（AVL树）。

二叉查找树

二叉查找树本质是一个二叉树，在该树中按顺序存储数据。该树中的每一个节点都具有以下属性：

• key：存储在该节点中的数据
• left：指向左子树的指针
• left：指向右子树的指针
• p：指向该节点父节点的指针

二叉搜索树区分于其他树的一个属性就是二叉搜索属性。

假设 x 是二叉搜索树中的一个节点。

• 如果 y 是x左子树中的一个节点，那么y.key ≤ x.key
• 如果 y 是x右子树中的一个节点，那么y.key≥ x.key

二叉搜索树的应用

• 二叉树：用于实现表达式解析器和表达式求解器
• 二叉搜索树：文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作
• 堆： JVM用于存储Java对象
• Treap树： 是二叉搜索树和堆的结合体。一般用于无线网络。

07 堆（Heap）

堆是二叉树的一个特例，其特点是某个节点的值总是不大于或不小于其父节点的值。下面我看下堆是如何表示的。堆即可以用树形结构来表示，也可以使用数组来表示。下面两个图分别使用二叉树和数组表示的一个堆。

堆又有两种类型：

• 小顶堆： 父节点的值总是小于或等于它的子节点中的值。根节点中的值将会是整个堆中最小的值。
• 大顶堆： 父节点的值总是大于或等于它的子节点中的值。根节点中的值将会是整个堆中最大的值。

堆的应用

• 用于堆排序算法
• 用于优先级队列
• 用于查找数组中第K大或第K小的值的算法

以上我们简单介绍了7种常见的数据结构以及其在实际中的应用，希望对你所有帮助。