基于线性表的查找算法（一道算法题的思考之线性表）

基于线性表的查找算法（一道算法题的思考之线性表）优点：那我们可以总结出线性表的优缺点：但是也会有的时候班长想商量事情需要坐在第二个位置，这个时候我们就需要扩容，让旁边的同学都移动一下给班长空出来一个位置，班长商量完事情走了，所有的同学又移动了一次把班长空出来的位置占用上。这就是线性表的增加和删除过程。那也有的时候虽然帮我们占了三个位置，但是有个女同学不想去上课了，那这个位置就浪费在那了。开发中很多场景我们都不知道真实的数据有多少，因为条件的不同接口返回的数据差别是比较大的，如果扩容到了1.5倍之后没有新的数据加入了，那么这一块内存就被浪费了。

知识回顾

一道算法题的思考之Array数组

一道算法题的思考之List集合

读大学的时候，我们班级只有三个女孩子，每次上课座位都是在一起，有的课人比较多的时候会找男生帮忙占位置，他们喜欢用书本或者水杯占位置。

这就像我们之前学的ArrayList集合，先拿初始值在内存中占个位置，等添加元素的时候就可以直接放到已经占的位置上了，因为所有的数据都是在一起的，所以它是内存中连续的区域。也因为这个原因只需要编个号就能按照这个号取数据了。

但是也会有的时候班长想商量事情需要坐在第二个位置，这个时候我们就需要扩容，让旁边的同学都移动一下给班长空出来一个位置，班长商量完事情走了，所有的同学又移动了一次把班长空出来的位置占用上。这就是线性表的增加和删除过程。

那也有的时候虽然帮我们占了三个位置，但是有个女同学不想去上课了，那这个位置就浪费在那了。

开发中很多场景我们都不知道真实的数据有多少，因为条件的不同接口返回的数据差别是比较大的，如果扩容到了1.5倍之后没有新的数据加入了，那么这一块内存就被浪费了。

那我们可以总结出线性表的优缺点：

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
• 可以快速地存取表中任一个位置的元素。

缺点：

• 插入和删除操作需要移动大量元素。
• 当线性表长度变化比较大时。
• 难以确定存储空间的容量，造成存储空间的碎片。

线性表除了我们前面学习的ArrayList之外，还有栈和队列以及链表结构。

栈、队列、链表的原理和用法比较简单，总结来说都是对数组的操作，我们一篇文章学完哈。

栈

栈是仅限定在表尾进行插入和删除操作的线性表。

把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In first Out）LIFO的线程表。

栈Stack类图：

Stack类提供了出栈和入栈的方法：

push(E e)：添加元素，添加的元素位于栈顶

pop()：从栈顶弹出第一元素，并从栈中删除这个元素

peek()：获取栈顶元素，不从栈中删除元素

empty()：判断栈中是否含有元素，不含有返回true，含有元素则返回false

search(Object o)：判断元素是否在栈中，不在则返回-1，在则返回大于0的值

栈的源码咱们就不看了，Stack都是调用的父类Vector的方法。如果ArrayList的源码能看懂，相信你看Vector源码的时候简直不要太easy！相信自己！

我们通过Leetcode一道算法题了解栈的使用。

“739. 每日温度

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73 74 75 71 69 72 76 73]，你的输出应该是 [1 1 4 2 1 1 0 0]。

提示：气温 列表长度的范围是 [1 30000]。每个气温的值的均为华氏度，都是在 [30 100] 范围内的整数。

”

解题思路：

1）先看返回的数据结构是一个数组，数组的长度与给定的数据长度是相等的。

2）看返回的数据是什么，下一个比当前温度高的是哪天，这两天之间的间隔即下标的差值是我们需要返回的数据

3）返回的数据分析完了，我们接下来分析怎么获取返回的数据。数组我们有三种处理方式，从头开始、从尾部开始或者双指针。双指针明显不合适。我们先假设常见思维从头部开始。73与后面的元素对比74比它高，则它对应的下标位置是1，再74得到75比它高，则它对应的下标位置为1，继续75需要遍历到尾部没有找到比它高的温度，则它对应的下标位置为0，依次类推，最差的数据每一个温度的比较都需要与之后的所有数据做比较。可以实现效果，时间复杂度比较大。

4）通过从头开始的分析我们了解到，每一次的对比都是找到第一个比它大的就停了，假如我们创建一个数据结构，存储比较大的数据的下标，通过两个下标的差值就得到了我们的数据了。从头开始肯定不行，我们不知道后面还有没有更大，只能从尾部开始。这个数据结构头部的元素是第一个需要判断的，不满足的话第一个就不要了取下一个，那不就是栈结构。

现在我们假设有个栈，73的时候发现栈是空的，那就没有比它大的，下标位置放个0，把7放入栈。76发现栈中有元素，但是栈的元素比自己小，说明要取代它作为最大的温度存在，自己的下标位置放0，7出栈，6入栈。72发现栈比自己大用6-5得到1，不需要出栈，5入栈。依次类推，直到数组第一个元素。

接下来我们实现上述两个方法，耗时时间差的还是蛮多的。

/** *第一种方法：执行用时1902ms，内存46.9M *@paramT *@return */ publicstaticint[]test01(int[]T){ //先知道要返回什么样的数据 intlength=T.length; int[]res=newint[length]; //从头到尾部遍历 for(inti=0;i<length;i ){ //第二个指针 for(intj=i 1;j<length;j ){ if(T[i]<T[j]){ res[i]=j-i; //发现比自己大的就退出 break; }else{ //直到最后还没发现，就给个0 if(j==length-1){ res[i]=0; } } } } returnres; }

/** *第二种方法：执行用时29ms，内存46.1M *@paramT *@return */ publicstaticint[]test02(int[]T){ intlength=T.length; int[]res=newint[length]; //定义一个栈 Stack<Integer>stack=newStack<>(); for(inti=length-1;i>=0;i--){ //栈中的元素比自己小，把栈中的元素弹出去 while(!stack.empty()&&T[stack.peek()]<=T[i]){ stack.pop(); } //如果栈为空，说明自己是最大的，给个0 if(stack.empty()){ res[i]=0; }else{ //栈不为空，说明栈顶的元素比自己大，不要弹出，用它的下标计算值即可 res[i]=stack.peek()-i; } stack.push(i); } returnres; } 队列

队列是之允许在一端进行插入操作、而在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）FIFO的线性表。允许插入端称为队尾，允许删除的一端称为队头。

队列queue类图：

这里面有我们熟悉的阻塞队列，不熟悉的小朋友可以查看之前的文章。

阻塞队列BlockingQueue

Queue接口最常用的实现类是PriorityQueue优先级队列，默认升序排列，也可以在初始化时指定排序规则，所以队列中的元素并不是按照存入的顺序存储的。

PriorityQueue常用方法：

offer(E e)：从队列尾部添加元素

peek()：获取队列头部的第一个元素，不从队列中删除元素

poll()：从队列头部获取元素，并从队列中删除元素

我们以Leetcode一道算法题了解PriorityQueue的应用：

“215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3 2 1 5 6 4] 和 k = 2 输出: 5 示例 2:

输入: [3 2 3 1 2 4 5 5 6] 和 k = 4 输出: 4

”

解题思路：

1）这道题目虽然设置为中等难度但还是比较简单。我们先来看返回值是数组中第k个最大的元素。

2）那是不是我们只需要对数组排好序，取出来第k个最大的就可以。这当然可以，除了排序还可以有其他方法吗？

3）我们不对数组排序，就需要其他可以排序的数据结构来做，那是不是就可以选择PriorityQueue，PriorityQueue中最多存k 1元素，只把大的放进去，如果小于队首的元素就不存进去，如果里面存的元素超过了k个就把队首最小的元素弹出。这样队首的元素就是第k个最大的了。

接下来我们代码实现：

/** *方法1：耗时2ms，内存消耗38.8 *@paramnums *@paramk *@return */ publicstaticintfindKthLargest01(int[]nums intk){ if(nums.length==0){ return0; } //默认升序排序 Arrays.sort(nums); returnnums[nums.length-k]; }

/** *方法2：耗时5ms，内存消耗38.9 *@paramnums *@paramk *@return */ publicstaticintfindKthLargest02(int[]nums intk){ if(nums.length==0){ return0; } //优先队列默认按照升序排列 PriorityQueue<Integer>queue=newPriorityQueue<>(k 1); for(intitem:nums){ //如果队列中的元素小于2个或者当前元素比队列头部的元素大，则放进队列 if(queue.size()<k||item>=queue.peek()){ queue.offer(item); } //队列中的元素已经超过了k个了，则将较小的元素出队，即队列头部的元素 if(queue.size()>k){ queue.poll(); } } //最后队列头部的元素即是我们要的元素 returnqueue.peek(); }

这里是不是有疑问，第一个方法又简单又快，为啥要用第二个。那我们再看一题，这道题目是类似的，但是用第一种方法就实现不了了。

这道题目中勾勾用到了下一篇要学习的知识点Map结构，下一篇文章再给勾勾的解题思路！大家可以先看看有没有好的解题思路！

“692. 前K个高频单词

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

输入: ["i" "love" "leetcode" "i" "love" "coding"] k = 2
输出: ["i" "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: ["the" "day" "is" "sunny" "the" "the" "the" "sunny" "is" "is"] k = 4
输出: ["the" "is" "sunny" "day"]
解析: "the" "is" "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4 3 2 和 1 次。
”

Queue还有一个比较常用的子接口Deque，因为它两端都可以插入和删除元素，我们又将其称为双端队列。

我们前面学习的ArrayList、Stack、Queue元素都是顺序的，即是线性表的顺序存储结构，线性表还有一个是链式存储结构。最常用的实现类LinkedList。

链表

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着这些数据元素可以存在内存中未被占用的任意位置。

链表又可以分为单链表、循环链表、双链表、静态链表。我们今天学习的LinkedList是双链表的结构。

那我们现在就抽象模型：

我们存放一个元素的时候，我需要知道它的下一个元素的地址，那就可以根据这个地址找到这个元素了。所以需要有两块内存区域：一块用来存储数据，一块用来存储指针，指针可以是一个称为单链表，也可以是两个称为双链表。

有了这个抽象模型，我们看看LinkedList里面是怎么定义节点的信息的：

privatestaticclassNode<E>{ //存储的数据 Eitem; //指向前一个节点的指针，我们称为前驱节点 Node<E>next; //指向后一个节点的指针，我们称为后继节点 Node<E>prev; //构造函数 Node(Node<E>prev Eelement Node<E>next){ this.item=element; this.next=next; this.prev=prev; } }

现在线性链表的模型有了，我们怎么操作这个线性链表呢？怎么查找元素？怎么添加一个元素？怎么删除一个元素？接下来我们一个一个的分析。

链表在内存中不连续，通过下标肯定拿不到了。但是节点之间是有指针关联的，那是不是我知道了其中一个节点的地址就可以顺着链路找到其他的节点了。最好这个节点是头节点的地址或者尾节点的地址也可以两个都知道，这样就可以顺着头或者尾取数据了。

那我们看看LinkedList是怎么做的，它定义了两个Node对象分别指向链表的头节点和尾节点。

publicclassLinkedList<E> extendsAbstractSequentialList<E> implementsList<E> Deque<E> Cloneable java.io.Serializable { //容器中元素的多少 transientintsize=0; /** *头节点指针 *Invariant:(first==null&&last==null)|| *(first.prev==null&&first.item!=null) */ transientNode<E>first; /** *尾节点指针 *Invariant:(first==null&&last==null)|| *(last.next==null&&last.item!=null) */ transientNode<E>last; } 添加元素

添加元素的思想：

• 如果是链表尾部添加元素，那么新添加的节点就是尾节点，它的后继节点指针为null。新增节点即是尾节点，再把之前尾节点的后继节点指向新增节点。

voidlinkLast(Ee){ finalNode<E>l=last; //新建节点，前驱节点是尾节点，后继节点为null finalNode<E>newNode=newNode<>(l e null); //将新节点设置为尾节点 last=newNode; //如果只有一个节点，那么头节点和尾节点都是新增节点 if(l==null) first=newNode; else //否则，将之前的尾节点的下一个指针指向新节点 l.next=newNode; size ; modCount ; }

• 如果是链表头部添加元素，那么新增节点的前驱节点是null，后继节点是头节点。新增节点即是头节点，再把原来的头节点的前驱节点指针指向新节点。

privatevoidlinkFirst(Ee){ finalNode<E>f=first; //新建节点，前驱节点为null，后继节点为头节点 finalNode<E>newNode=newNode<>(null e f); //将新节点设置为头节点 first=newNode; //如果只有一个节点，那么尾节点和头节点都是这个新的节点 if(f==null) last=newNode; else //否则，原来的头节点的前驱节点就是新节点 f.prev=newNode; size ; modCount ; }

add(E e)：链表尾部添加元素。

offer(E e)：链表尾部添加元素。可以选择不同的方法将节点添加在链表的尾部或者是头部。添加成功返回true，可以根据结果判断元素是否添加成功。

push(E e)：链表头部添加元素，返回值为void。

publicbooleanadd(Ee){ linkLast(e); returntrue; } publicbooleanoffer(Ee){ returnadd(e); } publicvoidpush(Ee){ addFirst(e); } 获取元素

get(int index)：获取链表中指定位置的元素。

publicEget(intindex){ checkElementIndex(index); returnnode(index).item; }

peek()：从链表头部的元素，不从链表中删除。

publicEpeek(){ finalNode<E>f=first; return(f==null)?null:f.item; }

poll() ：从链表中获取头部元素，并从链表中删除。链表可以为空，如果删除的元素不存在，则返回null。

pop()：从链表中获取头部元素，并从链表中删除。链表不能为空，否则抛出NoSuchElementException。

publicEpoll(){ finalNode<E>f=first; return(f==null)?null:unlinkFirst(f); } publicEpop(){ returnremoveFirst(); }

删除元素的思想：

• 删除元素需要将元素的值置为null，并且将其指向其他节点的指针置为null，方便GC回收。
• 如果删除的元素是头节点，则获取它的下一个节点设置为新的头节点，并将新的头节点的前驱指针置为null。

privateEunlinkFirst(Node<E>f){ //assertf==first&&f!=null; finalEelement=f.item; finalNode<E>next=f.next; //将头节点的元素值和指针都置为null，方便gc回收 f.item=null; f.next=null;//helpGC //将下一个节点置为头节点 first=next; if(next==null) last=null; else next.prev=null; size--; modCount ; returnelement; }

• 如果删除的是尾节点，则获取它的前驱节点为尾节点，并将新的尾节点的后继指针置为null。

privateEunlinkLast(Node<E>l){ //assertl==last&&l!=null; finalEelement=l.item; finalNode<E>prev=l.prev; l.item=null; l.prev=null;//helpGC last=prev; if(prev==null) first=null; else prev.next=null; size--; modCount ; returnelement; }

我们现在已经了解了LinkedList的常用方法，现在通过一道算法题熟悉其使用。

“剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 2 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5 和 k = 2.
返回链表 4->5.
”

解题思路：

1）返回值为最后k个节点。

2）那么第一步我们需要找到这个节点。怎么找这个节点呢，链表结构只能一个个的找。也即是遍历所有节点。

3）那什么情况下算是找到了，这个时候我们采用常用的双指针法，一个先走k步，然后再两个一起走，那么第一个指针走到最后的时候，第一个指针正好在倒数k个元素那里。

publicListNodegetKthFromEnd(ListNodehead intk){ ListNodep1=head; ListNodep2=head; //指针先走k步 while(k>0&&p2!=null){ p2=p2.next; k--; } //两个指针一起走，先走的指针到最后结束 while(p2!=null){ p1=p1.next; p2=p2.next; } returnp1; } 总结

今天学习了栈、队列和链表三种数据结构。栈和队列底层都是数组，对栈和队列的操作其实就是对数组的操作，源码上来说不复杂，大家还是主要掌握他们基本概念和常用的方法。栈结构常用来记录中间的状态，队列的应用范围就比较广，比如MQ中间件一些三方框架里面，我们在代码中也比较常用。

勾勾举个在开发中的实际例子，在一个高并发的场景下，如果需要保证比较大QPS，类似数据库落库操作是比较耗时的，大部分落库的操作勾勾都是定时去落库，这个时候就需要把相关的数据先存在队列中，然后一个线程定时扫描这个队列批量落库。当然考虑线程安全性，勾勾使用的阻塞队列。

链表结构主要适用于插入和修改比较频繁的场景，如果经常查询的元素如果不是第一个或者最后一个元素，不建议大家用这种数据结构。开发中大部分都是读大于写的场景，所以ArrayList的使用场景更多一点。

我是勾勾，一直在努力的程序媛，感谢您的点赞、转发和关注！

我们下篇文章见！