线性数据结构 · 浮光笔记

线性表示最常⽤⽽且最为简单的⼀种数据结构，⼀个线性表示 n 个数据元素的有限序列，有以下特点：

存在唯⼀的第⼀个的数据元素
存在唯⼀被称为最后⼀个的数据元素
除了第⼀个以外，集合中每⼀个元素均有⼀个前驱
除了最后⼀个元素之外，集合中的每⼀个数据元素都有⼀个后继元素

线性表包括下⾯⼏种：

数组：查询 / 更新快，查找/删除慢
链表
队列
栈

数组

数组简介

数组（Array） 是一种很常见的数据结构。它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。在Java 中表示为：

数组是⼀种线性的结构，⼀般在底层是连续的空间，存储相同类型的数据，由于连续紧凑结构以及天然索引⽀持，查询数据效率⾼。

假设我们知道数组a 的第 1 个值是地址是 296，⾥⾯的数据类型占 2 个单位，那么我们如果期望得到第 5 个： 296+（5-1）*2 = 304 , O(1) 的时间复杂度就可以获取到。更新的本质也是查找，先查找到该元素，就可以动⼿更新了：但是如果期望插⼊数据的话，需要移动后⾯的数据，⽐如下⾯的数组，插⼊元素6，最差的是移动所有的元素，时间复杂度为O(n) ⽽删除元素则需要把后⾯的数据移动到前⾯，最差的时间复杂度同样为O(n) 总结：数组的特点是：提供随机访问 并且容量有限。

时间复杂度

假如数组的长度为 n。

访问：O（1）//访问特定位置的元素
插入：O（n ）//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
删除：O（n）//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时

数组的增删改查实现

链表

链表简介

链表（LinkedList） 虽然是一种线性表，但是并不会按线性的顺序存储数据，使用的不是连续的内存空间来存储数据。

我们可以看到数组是需要连续的空间，这⾥⾯如果空间⼤⼩只有 2，放到第 3 个元素的时候，就不得不扩容，不仅如此，还得拷⻉元素。⼀些删除，插⼊操作会引起较多的数据移动的操作。

链表，也就是链式数据结构，由于它不要求逻辑上相邻的数据元素在物理位置上也相邻，所以它没有顺序存储结构所具有的缺点，但是同时也失去了通过索引下标直接查找元素的优点。

链表的插入和删除操作的复杂度为 O(1)，只需要知道目标位置元素的上一个元素即可。但是，在查找一个节点或者访问特定位置的节点的时候复杂度为 O(n) 。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但链表不会节省空间，相比于数组会占用更多的空间，因为链表中每个节点存放的还有指向其他节点的指针。除此之外，链表不具有数组随机读取的优点。

时间复杂度

查询： O(n)，需要遍历链表
插⼊： O(1)，修改前后指针即可
删除： O(1)，同样是修改前后指针即可
修改：不需要查询则为O(1)，需要查询则为O(n)

链表分类

常见链表分类：

单链表：链表中的每⼀个结点，都有且只有⼀个指针指向下⼀个结点，并且最后⼀个节点指向空。
双向链表：每个节点都有两个指针（为⽅便，我们称之为前指针，后指针），分别指向上⼀个节点和下⼀个节点，第⼀个节点的前指针指向NULL，最后⼀个节点的后指针指向NULL
循环链表：每⼀个节点的指针指向下⼀个节点，并且最后⼀个节点的指针指向第⼀个节点（虽然是循环链表，但是必要的时候还需要标识头结点或者尾节点，避免死循环）
双向循环链表：同时满足双向链表和循环链表的能力

单链表

单链表 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。单向链表的查找更新⽐较简单，我们看看插⼊新节点的具体过程（这⾥只展示中间位置的插⼊，头尾插⼊⽐较简单）：那如何删除⼀个中间的节点呢？下⾯是具体的过程：或许你会好奇， a5 节点只是指针没有了，那它去哪⾥了？

如果是Java 程序，垃圾回收器会收集这种没有被引⽤的节点，帮我们回收掉了这部分内存，但是为了加快垃圾回收的速度，⼀般不需要的节点我们会置空，⽐如 node = null , 如果在C++ 程序中，那么就需要⼿动回收了，否则容易造成内存泄漏等问题。

循环链表

循环链表 其实是一种特殊的单链表，和单链表不同的是循环链表的尾结点不是指向 null，而是指向链表的头结点。

双向链表

双向链表 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。

双向循环链表

双向循环链表 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。

应用场景

如果需要支持随机访问的话，链表没办法做到。
如果需要存储的数据元素的个数不确定，并且需要经常添加和删除数据的话，使用链表比较合适。
如果需要存储的数据元素的个数确定，并且不需要经常添加和删除数据的话，使用数组比较合适。

数组 vs 链表

数组支持随机访问，而链表不支持。
数组使用的是连续内存空间对 CPU 的缓存机制友好，链表则相反。
数组的大小固定，而链表则天然支持动态扩容。如果声明的数组过小，需要另外申请一个更大的内存空间存放数组元素，然后将原数组拷贝进去，这个操作是比较耗时的！

链表的性能问题，详情可以看这篇文章：LinkedList 存在的性能问题

单向链表的增删改查实现

扩展：跳表

链表如果搜索，是很麻烦的，如果这个节点在最后，需要遍历所有的节点，才能找到，查找效率实在太低，有没有什么好的办法呢？

办法总⽐问题多，但是想要绝对的” 多快好省“是不存在的，有舍有得，计算机的世界⾥，充满哲学的味道。既然搜索效率有问题，那么我们不如给链表排个序。排序后的链表，还是只能知道头尾节点，知道中间的范围，但是要找到中间的节点，还是得⾛遍历的⽼路。如果我们把中间节点存储起来呢？存起来，确实我们就知道数据在前⼀半，还是在后⼀半。⽐如找7，肯定就从中间节点开始找。如果查找4 ,就得从头开始找，最差到中间节点，就停⽌查找。但是如此，还是没有彻底解决问题，因为链表很⻓的情况，只能通过前后两部分查找。不如回到原则：空间和时间，我们选择时间，那就要舍弃⼀部分空间,我们每个节点再加⼀个指针，现在有 2 层指针（注意：节点只有⼀份，都是同⼀个节点，只是为了好看，弄了两份，实际上是同⼀个节点，有两个指针，⽐如 1，既指向2，也指向5）：两层指针，问题依然存在，那就不断加层，⽐如每两个节点，就加⼀层：这就是跳表了，跳表的定义如下：

跳表(SkipList，全称跳跃表)是⽤于有序元素序列快速搜索查找的⼀个数据结构，跳表是⼀个随机化的数据结构，实质就是⼀种可以进⾏⼆分查找的有序链表。跳表在原有的有序链表上⾯增加了多级索引，通过索引来实现快速查找。跳表不仅能提⾼搜索性能，同时也可以提⾼插⼊和删除操作的性能。它在性能上和红⿊树，AVL树不相上下，但是跳表的原理⾮常简单，实现也⽐红⿊树简单很多。

主要的原理是⽤空间换时间，可以实现近乎⼆分查找的效率，实际上消耗的空间，假设每两个加⼀层，1 + 2 + 4 + … + n = 2n-1 ,多出了差不多⼀倍的空间。你看它像不像书的⽬录，⼀级⽬录，⼆级，三级 …

如果我们不断往跳表中插⼊数据，可能出现某⼀段节点会特别多的情况，这个时候就需要动态更新索引，除了插⼊数据，还要插⼊到上⼀层的链表中，保证查询效率。redis 中使⽤了跳表来实现zset , redis 中使⽤⼀个随机算法来计算层级，计算出每个节点到底多少层索引，虽然不能绝对保证⽐较平衡，但是基本保证了效率，实现起来⽐那些平衡树，红⿊树的算法简单⼀点。

在跳表中，每个节点包含以下几个组成部分：

值（value）：节点存储的数据
前进指针数组（forward array）：指向不同层级的后继节点
层高（level）：该节点的最大层级

跳表核心特性：

多层结构：由最底层的原始有序链表，以及若干层索引组成
概率平衡：通过随机函数决定节点的层数，无需复杂的平衡操作
快速查找：能够跳过大量节点，实现对数级别的查找效率
有序性：所有节点按关键字排序
空间换时间：使用额外的索引指针提高查询速度

基本操作

查找（Search）：查找过程从最高层开始，沿着当前层前进，直到遇到大于或等于目标值的节点：
1. 如果找到目标值，返回该节点
2. 如果当前节点的下一个值大于目标值，则降至下一层继续查找
3. 如果到达最底层仍未找到，则目标值不存在
插入（Insert）
1. 查找新值的插入位置，同时记录每一层的"插入点"
2. 随机生成新节点的层高
3. 从底层到该节点的最高层，逐层调整指针，将新节点插入到每层链表中
删除（Delete）
1. 查找待删除节点的位置，同时记录每一层的前驱节点
2. 如果找到该节点，从该节点的最高层到底层，逐层调整前驱节点的指针，绕过待删除节点

基础实现

栈

栈简介

栈 (Stack) 只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out） 的原理运作。**在栈中，push 和 pop 的操作都发生在栈顶。**就像是⼀个桶，只能不断的放在上⾯，取出来的时候，也只能不断的取出最上⾯的数据。要想取出底层的数据，只有等到上⾯的数据都取出来，才能做到。当然，如果有这种需求，我们⼀般会使⽤双向队列。栈常用一维数组或链表来实现，用数组实现的栈叫作 顺序栈，用链表实现的栈叫作 链式栈 。JDK 底层的栈，是⽤数组实现的，封装之后，通过API 操作的永远都只能是最后⼀个元素，栈经常⽤来实现递归的功能。

元素加⼊称之为⼊栈（压栈），取出元素，称之为出栈，栈顶元素则是最后⼀次放进去的元素。使⽤数组实现简单的栈(注意仅供参考测试，实际会有线程安全等问题)

时间复杂度

假设堆栈中有n个元素。

访问：O（n）//最坏情况
插入删除：O（1）//顶端插入和删除元素

栈的常见应用场景

当我们我们要处理的数据只涉及在一端插入和删除数据，并且满足 后进先出（LIFO, Last In First Out） 的特性时，我们就可以使用栈这个数据结构。

实现浏览器的回退和前进功能

我们只需要使用两个栈(Stack1 和 Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面，我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看 2 这个页面的时候，你点击回退按钮，我们依次把 4,3 这两个页面从 Stack1 弹出，然后压入 Stack2 中。假如你又想回到页面 3，你点击前进按钮，我们将 3 页面从 Stack2 弹出，然后压入到 Stack1 中。

检查符号是否成对出现

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断该字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

比如 “()"、”()[]{}"、"{[]}" 都是有效字符串，而 “(]"、”([)]" 则不是。

这个问题实际是 Leetcode 的一道题目，我们可以利用栈 Stack 来解决这个问题。

首先我们将括号间的对应规则存放在 Map 中，这一点应该毋容置疑；
创建一个栈。遍历字符串，如果字符是左括号就直接加入stack中，否则将stack 的栈顶元素与这个括号做比较，如果不相等就直接返回 false。遍历结束，如果stack为空，返回 true。

反转字符串

将字符串中的每个字符先入栈再出栈就可以了。

维护函数调用

最后一个被调用的函数必须先完成执行，符合栈的 后进先出（LIFO, Last In First Out） 特性。例如递归函数调用可以通过栈来实现，每次递归调用都会将参数和返回地址压栈。

深度优先遍历（DFS）

在深度优先搜索过程中，栈被用来保存搜索路径，以便回溯到上一层。

栈的实现

栈既可以通过数组实现，也可以通过链表来实现。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。

下面我们使用数组来实现一个栈，并且这个栈具有push()、pop()（返回栈顶元素并出栈）、peek() （返回栈顶元素不出栈）、isEmpty()、size()这些基本的方法。

提示：每次入栈之前先判断栈的容量是否够用，如果不够用就用Arrays.copyOf()进行扩容；

验证

单调栈

栈本来就是一种受限的数据结构了，单调栈在此基础上又受限了一次，单调栈要求栈中的元素是单调递增的或者单调递减的。

‌单调栈是 O(n) 复杂度解决“找最近更大/更小元素（下一个大于 xxx或者下一个小于 xxx这种题目）”的高效算法，核心是维护栈内元素单调性。

怎么选择栈类型，记住一句口诀：‌找最近更大用递减栈，找最近更小用递增栈‌‌‌‌

单调递减栈‌：栈底到栈顶元素越来越小，适合找右边第一个比当前大的数。
单调递增栈‌：栈底到栈顶元素越来越大，适合找右边第一个比当前小的数。
‌遍历方向‌：找左侧元素正着遍历，找右侧元素通常也正着遍历，出栈时即找到答案

主要解决需要快速确定元素边界或距离的问题，典型场景包括：

‌每日温度‌：计算需要等几天才有更高温度。
接雨水/柱状图‌：确定左右边界以计算面积或积水量。
区间最值‌：寻找序列中每个元素左边或右边第一个满足大小关系的元素。‌‌

写代码注意啥

‌存下标不存值‌：栈里存数组下标，既能拿到值，又方便计算距离和区间长度。
‌效率极高‌：每个元素最多入栈和出栈一次，整体时间复杂度为线性 O(n)。
‌维护逻辑‌：新元素入栈前，先弹出破坏单调性的栈顶元素，再入栈。‌‌

队列

队列简介

队列（Queue） 是 先进先出 (FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue

队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。⼀般只要说到先进先出（ FIFO ）,全称First In First Out ,就会想到队列，但是如果你想拥有队列即可以从队头取出元素，⼜可以从队尾取出元素，那就需要⽤到特殊的队列（双向队列），双向队列⼀般使⽤双向链表实现会简单⼀点。

时间复杂度

假设队列中有n个元素。

访问：O（n）//最坏情况
插入删除：O（1）//后端插入前端删除元素

队列分类

单队列

单队列就是常见的队列, 每次添加元素时，都是添加到队尾。单队列又分为 顺序队列（数组实现） 和 链式队列（链表实现）。

顺序队列存在“假溢出”的问题也就是明明有位置却不能添加的情况。

假设下图是一个顺序队列，我们将前两个元素 1,2 出队，并入队两个元素 7,8。当进行入队、出队操作的时候，front 和 rear 都会持续往后移动，当 rear 移动到最后的时候,我们无法再往队列中添加数据，即使数组中还有空余空间，这种现象就是 ”假溢出“ 。除了假溢出问题之外，如下图所示，当添加元素 8 的时候，rear 指针移动到数组之外（越界）。

为了避免当只有一个元素的时候，队头和队尾重合使处理变得麻烦，所以引入两个指针，front 指针指向对头元素，rear 指针指向队列最后一个元素的下一个位置，这样当 front 等于 rear 时，此队列不是还剩一个元素，而是空队列。——From 《大话数据结构》

循环队列

循环队列可以解决顺序队列的假溢出和越界问题。解决办法就是：从头开始，这样也就会形成头尾相接的循环，这也就是循环队列名字的由来。

顺序队列中，我们说 front==rear 的时候队列为空，循环队列中则不一样，也可能为满，如上图所示。解决办法有两种：

可以设置一个标志变量 flag,当 front==rear 并且 flag=0 的时候队列为空，当front==rear 并且 flag=1 的时候队列为满。
队列为空的时候就是 front==rear，队列满的时候，我们保证数组还有一个空闲的位置，rear 就指向这个空闲位置，如下图所示，那么现在判断队列是否为满的条件就是：(rear+1) % QueueSize==front 。

双端队列

双端队列 (Deque) 是一种在队列的两端都可以进行插入和删除操作的队列，相比单队列来说更加灵活。

一般来说，我们可以对双端队列进行 addFirst、addLast、removeFirst 和 removeLast 操作。

优先队列

优先队列 (Priority Queue) 从底层结构上来讲并非线性的数据结构，它一般是由堆来实现的。

在每个元素入队时，优先队列会将新元素其插入堆中并调整堆。
在队头出队时，优先队列会返回堆顶元素并调整堆。

关于堆的具体实现可以看堆这一节。

总而言之，不论我们进行什么操作，优先队列都能按照某种排序方式进行一系列堆的相关操作，从而保证整个集合的有序性。

虽然优先队列的底层并非严格的线性结构，但是在我们使用的过程中，我们是感知不到堆的，从使用者的眼中优先队列可以被认为是一种线性的数据结构：一种会自动排序的线性队列。

队列的常见应用场景

当我们需要按照一定顺序来处理数据的时候可以考虑使用队列这个数据结构。

阻塞队列： 阻塞队列可以看成在队列基础上加了阻塞操作的队列。当队列为空的时候，出队操作阻塞，当队列满的时候，入队操作阻塞。使用阻塞队列我们可以很容易实现“生产者 - 消费者“模型。
线程池中的请求/任务队列： 线程池中没有空闲线程时，新的任务请求线程资源时，线程池该如何处理呢？答案是将这些请求放在队列中，当有空闲线程的时候，会循环中反复从队列中获取任务来执行。队列分为无界队列(基于链表)和有界队列(基于数组)。无界队列的特点就是可以一直入列，除非系统资源耗尽，比如：FixedThreadPool 使用无界队列 LinkedBlockingQueue。但是有界队列就不一样了，当队列满的话后面再有任务/请求就会拒绝，在 Java 中的体现就是会抛出java.util.concurrent.RejectedExecutionException 异常。
栈：双端队列天生便可以实现栈的全部功能（push、pop 和 peek），并且在 Deque 接口中已经实现了相关方法。Stack 类已经和 Vector 一样被遗弃，现在在 Java 中普遍使用双端队列（Deque）来实现栈。
广度优先搜索（BFS），在图的广度优先搜索过程中，队列被用于存储待访问的节点，保证按照层次顺序遍历图的节点。
Linux 内核进程队列（按优先级排队）
现实生活中的派对，播放器上的播放列表;
消息队列
等等……