史上最全的数据结构讲解 ---- 线性结构 （2）

分析：

• 第一种方式：相当于先删除对应索引的旧结点，再往对应索引处插入新结点即可。（效率较慢）

//替换步骤：相当于删除i节点，再往i插入新的节点E data=remove(i);add(i,e);第二种方式：//[1]先得到对应索引处的结点元素Node<E> node = getNode(i);//[2]保存结点旧的数据E oldVal = node.data;//[3]替换成新的数据node.data=e;return oldVal;

• 第二种方式：

        //[1]先得到对应索引处的结点元素Node<E> node = getNode(i);//[2]保存结点旧的数据E oldVal = node.data;//[3]替换成新的数据node.data=e;return oldVal;		

1）根据索引获取元素get(i)

	@Overridepublic E get(int i) {return getNode(i).data;}

2）获取元素第一次出现的位置indexOf(e)

	@Overridepublic int indexOf(E e) {//没有则返回-1，否则返回该节点的索引int index=-1;for(int i=0;i<=size-1;i++){//获取索引对应的结点E data=get(i);//比较内容，不能用==,否则比较的是地址if(data.equals(e)){index=i;break;}}return index;}

3）获取元素最后一次出现的位置lastIndexOf(e)

    @Overridepublic int lastIndexOf(E e) {//没有则返回-1，否则返回该节点的索引int index=-1;for(int i=0;i<=size-1;i++){//获取索引对应的结点E data=get(i);//比较内容，不能用==,否则比较的是地址if(data.equals(e)){index=i;}}return index;}

通过public Node getNode(int i)该方法可以定位到对应索引的结点对象---->first为第一个结点（不存在head头结点这种概念）:

例如：

i=0, 获取第一个结点
i=1，获取第二个结点
依次类推 …

知识拓展：查找运用折半查找法，提高效率

      /*** 获取对应索引处的结点对象，运用折半查找法，提高效率* @param i 索引处* @return 结点对象*/private Node<E> getNode(int i){Node<E> node=null;if(i<=(size>>1)){//size>>1:相当于size/2//[1]从第一个结点开始找node=first;for(int j=0;j<i;j++){//[2]将指针移向下一个结点node=node.next;}}else{//[1]从最后一个开始找node=last;for(int j=size-1;j>i;j--){//[2]将指针移向上一个结点node=node.prev;}}return node;}

（1）addBefore(E obj, E e)：将一个元素插入到另一个元素的前面 ，范围：[0,size-1]，相当于在obj对应的索引i处插入数据e。

• 代码：

//将e插入到obj的前面@Overridepublic boolean addBefore(E obj, E e) {//判断obj是否存在if(contains(obj)){add(indexOf(obj),e);return true;}return false;}

（2）addAfter(E obj, E e)：将一个元素插入到另一个元素的后面，范围：[0,size-1]，相当于在obj对应的索引i后面i+1处插入数据e。

• 代码：

@Overridepublic boolean addAfter(E obj, E e) {//[1]获取obj的索引int i=indexOf(obj);if(obj!=null&&i!=-1){//[2]在i+1处插入e节点add(i+1,e);return true;}return false;}

前提：obj必须存在的情况下。

（3）一个带有泛型的结点类（作为实现类的一个静态内部类）：

  /*** 结点:一个结点（增加泛型）包括三个部分* 		1.数据域* 		2.上一个结点指针域 prev*      3.下一个结点指针域 next 	* @author HKM**/private static class Node<E> {//数据域E data;//下一个结点指针域Node<E> next;//上一个结点指针域Node<E> prev;Node(Node<E> prev,E data, Node<E> next) {super();this.data = data;this.next = next;this.prev = prev;}}

PS：增删改操作会涉及到链表的第一个结点first和最后一个结点last概念（非常重要）。

什么是单向循环链表？

如果把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表，通俗讲就是把尾节点的下一跳指向头结点。

单向链表的循环带头结点的空链表：

单向链表的循环带头结点的非空链表：

为什么要使用单向循环链表？

在单向链表中，头指针是相当重要的，因为单向链表的操作都需要头指针，所以如果头指针丢失或者破坏，那么整个链表都会遗失，并且浪费链表内存空间，因此我们引入了单向循环链表这种数据结构。

单向循环链表我们需要注意一个问题：

在单链表中我们使用的是虚拟头结点，但是在循环链表中我们在遍历的时候就会遇到麻烦，因此在单向循环链表中我们使用的是真实头结点。

只有一个头节点head的时候next就指向自己。

和单向链表差不多，区别就是最后一个节点的next指向的是head。

直接让新插入节点的next指向下一个节点就行。在最后的位置插入也是不矛盾的，因为已经构成了一个环，最后位置的next就是指向的头节点。

什么是双向循环链表？

最后一个节点的next指向head，而head的prior指向最后一个节点，构成一个环。

双向链表的循环带头结点的空链表：

双向链表的循环带头结点的非空链表：

初始化：只有一个头节点head，就让prior和next都指向自己。

与单向循环链表类似的，只是多了一个prior要考虑。

与单向循环链表类似，只是多了一个prior要考虑。这里就不需判断插入的位置是不是在最后了，已经构成一个环了。

什么是态链表？

静态链表是借助数组来描述线性表的链式存储结构，节点也有数据域和指针域，这里的指针是节点的相对地址（数组下标），也需要预先分配一块连续的内存空间。

特点：

• 插入删除和动态链表一样，以next==-1为结束标志。
• 静态链表中指针表示数组下标或下一个元素的下标。
• 静态链表既有顺序存储的优点，又有动态链表的优点，因为其用游标cur来指示下一个数据元素的存储位置，所以存取数据时静态链表同线性链表(单链表)是相似的。也就是说，静态链表在存取表中第i个元素的时间同i是相关的。
• 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
• 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

优点：

缺点：

数组的特点是：寻址容易，插入和删除困难；

而链表的特点是：寻址困难，插入和删除容易。

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把hash值映射到表中一个位置来访问记录，以加快查找的速度。

这个映射函数叫做散列函数，存放记录的数组叫做散列表。

对比之前博客讨论的二叉排序树，二叉平衡树，红黑树 B， B+树，它们的查找都是先从根节点进行查找，从节点取出数据或索引与查找值进行比较。那么，有没有一种函数H，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个比较。这样就“预先知道”key所在的位置，直接找到数据，提升效率。
即:

地址index=H（key）

说白了，hash函数就是根据关键字(key)计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表。

• Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值， 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。

• 查找：哈希表，又称为散列，是一种更加快捷的查找技术。我们之前的查找，都是这样一种思路：集合中拿出来一个元素，看看是否与我们要找的相等，如果不等，缩小范围，继续查找。而哈希表是完全另外一种思路：当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！

举一个例子，假如我的数组A中，第i个元素里面装的key就是i，那么数字3肯定是在第3个位置，数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想，建立一个从key到位置的函数，然后进行直接计算查找。

• Hash表在海量数据处理中有着广泛应用。

Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。

hash就是找到一种数据内容和数据存放地址之间的映射关系。

散列法： 元素特征转变为数组下标的方法。

我想大家都在想一个很严重的问题：“如果两个不同字符串在哈希表中对应的位置相同怎么办？”，毕竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用“链表”。我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。

• 当存储记录时，通过散列函数计算出记录的散列地址。
• 当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录。

关键字——散列函数（哈希函数）——散列地址

优点： 一对一的查找效率很高。

缺点：一个关键字可能对应多个散列地址；需要查找一个范围时，效果不好。

散列冲突： 不同的关键字（key）经过散列函数的计算得到了相同的散列地址。

好的散列函数=计算简单+分布均匀（计算得到的散列地址分布均匀）

元素特征转变为数组下标的方法就是散列法。

• 除法散列法 （比较常用）：

最直观的一种，上图使用的就是这种散列法，公式：

hash = hashcode % (位桶数组长度-1)

PS：位桶数组长度必须是2的整次幂，计算得到的散列地址分布均匀， hash表示对应在位桶数组中的索引。

学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。

• 平方散列法：

求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：

hash = (value * value) >> 28 （右移，除以2^28。记法：左移变大，是乘。右移变小，是除。）

如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。

• 斐波那契（Fibonacci）散列法：

平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。

1、对于16位整数而言，这个乘数是40503
2、对于32位整数而言，这个乘数是2654435769
3、对于64位整数而言，这个乘数是11400714819323198485

这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。
对我们常见的32位整数而言，公式：

hash = (value * 2654435769) >> 28

如果用这种斐波那契散列法的话，那上面的图就变成这样了：

注：用斐波那契散列法调整之后会比原来的取摸散列法好很多。

优点：

• 不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即O(1）的时间级。实际上，这只需要几条机器指令。
• 哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。
• 如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点：

• 它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

适用范围：

快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。

基本原理及要点：

hash函数选择，针对字符串，整数，排列，具体相应的hash方法。
碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。

• 建立一个缓冲区，把凡是拼音重复的人放到缓冲区中。当我通过名字查找人时，发现找的不对，就在缓冲区里找。
• 进行再探测。就是在其他地方查找。探测的方法也可以有很多种。

（1）在找到查找位置的index的index-1，index+1位置查找，index-2，index+2查找，依次类推。这种方法称为线性再探测。

（2）在查找位置index周围随机的查找。称为随机在探测。

（3）再哈希。就是当冲突时，采用另外一种映射方式来查找。

总结：

• 这个程序中是通过取模来模拟查找到重复元素的过程。对待重复元素的方法就是再哈希：对当前key的位置+7。最后，可以通过全局变量来判断需要查找多少次。
• 我这里通过依次查找26个英文字母的小写计算的出了总的查找次数。显然，当总的查找次数/查找的总元素数越接近1时，哈希表更接近于一一映射的函数，查找的效率更高。

模拟HashMap底层通过哈希表进行实现，先要更深入了解下HashMap底层是如何实现的小伙伴请参考这篇博客【史上最全的集合框架讲解 ----- Java 集合框架（3）---- Map 相关类最全解析】

Entry存储过程结构图：

Entry[]:位桶数组，长度必须为2的整次幂。

一个Entry对象包括：

• hash:哈希值，存放到位桶数组的索引, 计算key的hascode码&位桶数组长度-1。
• key：键名。
• value：键映射的值。
• next：下一个结点Entry对象。
  

分析：

• 插入：
  （1）向哈希表中插入键值对元素的原理：当向集合中插入键值对元素时，首先会计算根据插入的key的hashCode来进行计算出hash值，计算规则：

 static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

（2）然后根据该值来作为索引去确定存放到位桶数组的位置，此时，要进行判断该索引处是否已久存在键值对元素（也就是是否发生了hash碰撞）:

• 如果不存在，则直接插入到该位置上。
• 如果存在，则再进行判断新插入的键值对元素的key和当前位置上链表中已经存在的键值对元素的key是否等价，（等价的条件是： 不同的引用变量指向同一个对象或不同的引用变量指向的对象的equals（）方法返回true）。

怎么进行比较呢？就是将新插入的键值对元素的key与该位置上的链表中的键值对元素的key逐一进行equals方法比较:

• 如果该equals方法都返回false,那么说明该位置上的链表中不存在该键值对元素，将新添加的键值对元素追加到链表末尾。
• 如果有一个equals方法返回true，那么认为该位置上的链表已经存在该键值对元素了，则将原来的键值对元素的value替换成新插入的键值对元素的value。

PS：在哈希表中判断两个键值对元素的key是否重复要：使用到hashCode()和equals()。hashCode决定键值对元素在位桶数组的存储位置，而equals判断该位置上链表中是否已经存在该键值对元素。

• 代码：

//添加结点private boolean putVal(int hash, K key, V value) {/*[2]判断该位置是否已经有Node了(即该索引上的链表不为空)，如果有：则根据equals()判断是否存在key重复的情况，否则直接加到链表中，如果key存在重复：则覆盖key映射的旧value,否则追加到链表的末尾*/Node<K, V> currNode = tables[hash];//[3]新建一个结点Node<K, V> newNode=new Node<>(hash,key,value,null);//定义key是否重复的标志位boolean isKeyRepeated=false;//正在遍历的最后一个结点Node<K, V> lastNode=null;if(currNode==null){//[2.1]将新Node加到链表中tables[hash]=newNode;//数组的容量-1residueCap--;System.out.println("位桶数组剩余容量"+residueCap);}else{//[2.2]判断是否存在key重复的情况,需要逐一遍历链表while(currNode!=null){//[2.3]如果相同，则覆盖key映射的旧valueif(currNode.key.equals(key)){currNode.value=value;isKeyRepeated=true;return isKeyRepeated;}//[2.4]记录正在遍历的最后一个结点lastNode=currNode;//[2.5]将指针移向下一个NodecurrNode=currNode.next;}//如果不存在key重复的情况，则将新节点追加到链表末尾if(!isKeyRepeated){//[4]将添加新结点之前的链表最后一个结点的next指向新结点lastNode.next=newNode;}}//[5]结点个数+1size++;return isKeyRepeated;}

• 插入步骤：
     （1）判断是否需要扩容？
     （2）根据哈希函数计算出来的hash值，判断位桶数组存储位置是否有结点存在？

  • 如果没有，则进行直接插入即可。
  • 如果有，与当前存储位置的链表的结点使用equals(key)比较，相同则替换，都不同，追加到链表末尾即可。

   （3）结点元素+1。

分析：

• 删除： 根据要删除的键值对元素的key的hash值和key来确定要删除的键值对元素，因为这个条件可以唯一确定一个键值对元素。

• 代码：

      /*** 删除结点的情况--要考虑释放删除节点的空间* 	1.是第一个结点，且该索引处链表只存在一个结点* 		操作：[1]将位桶数组该索引处的值置为null* 			 *  2.是第一个结点，且该索引处链表存在多个结点*  	操作：[1]将当前结点的后驱结点变成链表的第一个结点，即tables[i]=后驱结点*   		 [2]将当前结点置为null*  *  3.是中间的结点*  	操作：[1]将当前结点的前驱结点的next指向当前结点的后驱结点*  		 [2]将当前结点置为null*  *  4.是最后一个结点*  	操作：[1]将当前结点的前驱结点的next置为null*  		 [2]将当前结点置为null*/private void removeNode(Node<K, V> node) {//索引处链表的第一个结点Node<K, V> firstNode = tables[node.hash];//[2]获取当前结点的后继结点,以便判断删除的结点位置Node<K, V> nextNode = node.next;//[3]判断删除节点的位置//[3.1]删除的是第一个结点,且该索引处的链表只存在一个结点,或是最后一个结点if(nextNode==null){//[3.1.1]删除的是第一个结点,且该索引处的链表只存在一个结点if(firstNode==node){//[3.1.1.1]将位桶数组该索引处的值置为nulltables[node.hash]=null;}//[3.1.2]删除的是最后一个结点else{//[3.1.2.1]将当前结点的前驱结点的next置为nullgetBeforeNode(node).next=nextNode;//[3.1.2.2]将当前结点置为nullnode=null;}}//[3.2]删除是第一个结点，且该索引处链表存在多个结点,或是中间的结点else{//[3.2.1]删除的是第一个结点,且该索引处链表存在多个结点if(firstNode==node){//[3.2.1.1]将当前结点的后驱结点变成链表的第一个结点，即tables[i]=后驱结点tables[node.hash]=getAfterNode(node);//[3.2.1.2]将当前结点置为nullnode=null;}//[3.2.2]删除的是最后一个结点else{//[3.2.2.1]将当前结点的前驱结点的next指向当前结点的后驱结点getBeforeNode(node).next=getAfterNode(node);//[3.2.2.2]将当前结点置为nullnode=null;}}//[5]结点个数—1size--;}

• 删除步骤：
     （1）找出currNode ，根据hash值和key进行寻找。
     （2）找出prevNode和nextNode，以便判断删除的结点位置。
     （3）判断删除的结点位置：

  • 是第一个结点，且该索引处链表只存在一个结点：

    [1]将位桶数组该索引处的值置为null。

  • 是第一个结点，且该索引处链表存在多个结点：

    [1]将nextNode变成链表的第一个结点，即tables[i]=nextNode。

    [2]将currNode置为null。

  • 是中间的结点：

    [1]将prevNode的next指向nextNode。

    [2]将currNode置为null。

  • 是最后一个结点：

    [1]将prevNode的next置为null。

    [2]将currNode 置为null。

       （4）结点个数-1。

PS：删除的结点：currNode ； 删除结点的前驱结点：prevNode ；删除结点的后继结点：nextNode。

注意一点： 需要将删除结点占用的空间释放掉，也就是将对象置为null，防止内存泄漏。

分析：

• 第一种方式： 相当于先删除对应索引的旧结点，再往对应索引处插入新结点即可。（效率较慢）。

//替换步骤：相当于删除i节点，再往i插入新的节点E data=remove(i);add(i,e);

• 第二种方式：

       /*** 删除key映射的结点*/@Overridepublic V remove(K key) {//[1]根据key的hash值和key获取结点Node<K, V> node = getNode(myHash(key),key);//[2]存在该键，则返回key映射的valueif(node!=null){//[3]移除该结点removeNode(node);return node.value;}//[4]不存在，返回nullreturn null;}

1）调用entrySet()获取键值对集合Set>：

	public Set<Map.Entry<K,V>> entrySet() {Set<Map.Entry<K,V>> es;return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;}

2）调用keySet()获取key集合Set：

	 public Set<K> keySet() {Set<K> ks = keySet;if (ks == null) {ks = new KeySet();keySet = ks;}return ks;}

3）调用values()获取值集合Collection：

public Collection<V> values() {Collection<V> vs = values;if (vs == null) {vs = new Values();values = vs;}return vs;}

（1）扩容操作：

什么时候扩容？当 位桶数组剩余容量==0或插入的hash值>位桶数组长度-1。

• 代码：

    //扩容步骤：private void resize(){//[1]重新定义一个按照规律扩容后的位桶数组,且长度必须是2的整数幂,<<1:表示扩大一倍Node<K, V>[] newTables=new Node[tables.length<<1];System.out.println("扩容后的数组长度为"+newTables.length);//[2]将旧位桶数组的值拷贝到新的位桶数组中Node<K, V> oldNode=null;Node<K, V> newNode=null;for(int i=0;i<=tables.length-1;i++){//[2.1]获取旧位桶数组对应索引处的链表oldNode= tables[i];//[2.2]将索引处的链表的第一个结点赋给新位桶数组newTables[i]=oldNode;//[2.3]对应索引处的链表正在遍历的下一个结点newNode=newTables[i];//[2.4]判断旧位桶数组对应索引处的链表是否还有下一个while(oldNode!=null){//[2.5]将旧位桶数组对应索引处的链表指针移向下一个NodeoldNode=oldNode.next;/*[2.6]将新位桶数组对应索引处的链表的上一个结点的next指向旧位桶数组对应索引处的链表的下一个结点,从而形成链表*/newNode.next=oldNode;//将新位桶数组对应索引处的链表指针移向下一个NodenewNode=oldNode;}}//[3]将指针指向新位桶数组tables=newTables;}

• 扩容步骤：
     （1）重新定义一个按照一定规律扩容后的数组。
     （2）将旧数组的数据拷贝到新的数组中。
     （3）将指针指向新的数组。

（2）带有泛型的Entry类（作为实现类的一个静态内部类）：

/*** 结点:一个结点（增加泛型）包括四个部分* 		1.hash值=key的hashcode码%位桶数组长度-1* 		2.key* 		3.value*     		4.下一个结点指针域 nxet* @author HKM**/private static class Node<K,V> {//keyK key;//valueV value;//hash值int hash;//下一个结点指针域Node<K,V> next;public Node( int hash,K key, V value, Node<K, V> next) {super();this.key = key;this.value = value;this.hash = hash;this.next = next;}public Node() {super();}public Node(int hash,K key, V value) {super();this.key = key;this.value = value;this.hash = hash;}}

（3）getNode(int hash,K key)：获取当前节点对象

• 代码：

      //根据hash值和key返回Node结点private Node<K, V> getNode(int hash,K key){//[1]通过key的hash值来获取到对应位置链表的第一个结点Node<K, V> currNode=tables[hash];//[2]根据equlas()比较keyif(currNode!=null){//是否是对应索引处的链表的最后一个结点while(currNode!=null){//[3]有该key，返回对应的Node结点if(currNode.key.equals(key)){return currNode;}//[3]将指针移向下一个NodecurrNode=currNode.next;}}//[3]没有该key，返回nullreturn null;}

• 获取步骤：
      [1] 找通过key的hash值定到位桶数组的存储位置，如果该位置的链表为空，直接返回null即可。
      [2] 再使用equals(key)与该位置链表的结点逐一进行比较。
      [3] 若为true，返回该结点，否则返回null。
  

（4）myHash(K key)：获取hash值

   /*** 获取hash值* @param key 键名* @return*/public int myHash(K key){//计算hash规则:hashCode值%位桶数组长度-1return (key.hashCode())%(tables.length-1);}

（5）getBeforeNode(Node node)；获取指定结点的前一个结点

/*  获取当前结点的上一个结点* 如果是索引处链表第一个结点，则返回null*/private Node<K, V> getBeforeNode(Node<K, V> node){//索引处链表当前指向的结点Node<K, V> currNode = tables[node.hash];//存在链表while(currNode!=null){//判断当前结点的next是否指向指定的结点,存在即返回上一个结点，否则返回nullif(currNode.next==node){return currNode;}currNode=currNode.next;}//如果是索引处链表第一个结点，则返回nullreturn null;}

（6）getAfterNode(Node node)；获取指定结点的后一个结点

/** 获取当前结点的下一个结点* 如果是索引处链表最一个结点，则返回null*/private Node<K, V> getAfterNode(Node<K, V> node){//索引处链表当前指向的结点Node<K, V> currNode = tables[node.hash];//存在链表while(currNode!=null&&node!=null){//判断当前结点的next是否指向指定的结点,存在即返回上一个结点，否则返回nullif(node.next==currNode){return currNode;}currNode=currNode.next;}//如果是索引处链表最后一个结点，则返回nullreturn null;}

链表结构和顺序存储结构的对比：

顺序表和链表的比较：

• 顺序表可以顺序存取，也支持随机存取；链表只能顺序存取。
• 顺序表逻辑上相邻的物理上也相邻；而链表不一定，它是用指针来描述元素之间的关系。
• 顺序表插入和删除要移动大量元素；链表只需修改指针即可。
• 随机存取就是直接存取，可以通过下标直接访问的那种数据结构，与存储位置无关，例如数组。非随机存取就是顺序存取了，不能通过下标访问了，只能按照存储顺序存取，与存储位置有关，例如链表。
• 顺序存取就是存取第N个数据时，必须先访问前（N-1）个数据 （list），随机存取就是存取第N个数据时，不需要访问前（N-1）个数据，直接就可以对第N个数据操作 （array）。
• 线性结构都是有索引的，因为链表存储结构分配的空间是不连续的，底层不是用数组存储的，索引不能通过索引进行查找元素，只能通过头结点依次寻找。而顺序表就可以。

栈（stack ）又称堆栈，它是运算受限的线性表。
其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。
表中进行插入、删除操作的一端称为 栈顶（top） ，栈顶保存的元素称为栈顶元素。 相对的，表的另一端称为栈底（bottom）。

当栈中没有数据元素时称为空栈；
向一个栈插入元素又称为进栈或 入栈；
从一个栈中删除元素又称为 出栈或 退栈；
由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出栈。
所以又把堆栈称为 后进先出表（Last In First Out，简称 LIFO）。

生活案例： 摞盘子和取盘子、一摞书、酒杯塔（各层之间可以简单理解为栈，每层内部不是栈） 。

技术案例： Java的栈内存和堆内存详解：【（2020史上最全总结，跳槽必看），一篇带你立马搞定jvm内存，类加载机制全过程，java内存模型，分代垃圾回收机制，垃圾回收算法和垃圾收集器】

应用举例： 请参考：【数据结构与算法】 栈——栈的应用举例】

和线性表类似，堆栈也有两种基本的存储结构：顺序存储结构和链式存储结构。

顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈中的数据元素。

由于堆栈是一种特殊的线性表，因此在线性表的顺序存储结构的基础上，选择线性表的一端作为栈顶即可。

根据数组操作的特性，选择数组下标大的一端，即线性表顺序存储的表尾来作为栈顶，此时入栈、出栈等操作可以在Ο(1)时间完成。

由于堆栈的操作都在栈顶完成，因此在顺序栈的实现中需要附设一个指针 top 来动态的指示栈顶元素在数组中的位置。

通常 top 可以用栈顶元素所在数组下标来表示，top= -1 时表示空栈。

链栈即采用链表作为存储结构实现的栈。

当采用单链表存储线性表后，根据单链表的操作特性选择单链表的头部作为栈顶，此时，入栈、出栈等操作可以在Ο(1)内完成。

由于堆栈的操作只在线性表的一端进行，在这里使用带头结点的单链表或不带头结点的单链表都可以。

使用带头结点的单链表时，结点的插入和删除都在头结点之后进行。

使用不带头结点的单链表时，结点的插入和删除都在链表的首结点上进行。

双向栈共享存储空间示意图：

栈接口，定义了栈的主要操作 ：

记住针对栈的专业词汇：push、pop、peek

public interface Stack { // 返回堆栈的大小 public int getSize(); // 判断堆栈是否为空 public boolean isEmpty(); // 数据元素 e 入栈 public void push(Object e); // 栈顶元素出栈 public Object pop(); // 取栈顶元素 public Object peek(); 
} 

队列（queue ）简称队，它同堆栈一样，也是一种运算受限的线性表， 其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

在队列中把插入数据元素的一端称为 队尾（rear） ），删除数据元素的一端称为 队首（front） ）。

向队尾插入元素称为 进队或入队，新元素入队后成为新的队尾元素； 从队列中删除元素称为离队或出队，元素出队后，其后续元素成为新的队首元素。

由于队列的插入和删除操作分别在队尾和队首进行，每个元素必然按照进入的次序离队， 也就是说先进队的元素必然先离队，所以称队列为 先进先出表（First In First Out,简称FIFO）。

生活案例： 排队打饭，排队进地铁站，上地铁 。

技术案例： 多线程中就绪队列和阻塞队列。

方法1：使用普通数组作为存储结构：

缺点：

通过出队操作将数据弹出队列后，front之前的空间还能够再次得到吗？
不能。所以使用普通数组实现队列，就再也不能使用front之前的空间了，这会导致大量空间丢失 。

方法2：使用循环数组作为存储结构：

为了解决这个问题，将普通数组换成循环数组。在循环数组中，末尾元素的下一个元素不是数组外，而是数组的头元素。
这样就能够再次使用front之前的存储空间了 （相当于解决了假溢出现象）。

队列的链式存储可以使用单链表来实现。

为了操作实现方便，这里采用带头结点的单链表结构。

根据单链表的特点，选择链表的头部作为队首，链表的尾部作为队尾。

除了链表头结点需要通过一个引用来指向之外，还需要一个对链表尾结点的引用，以方便队列的入队操作的实现。

为此一共设置两个指针，一个队首指针和一个队尾指针，队首指针指向队首元素的前一个结点，即始终指向链表空的头结点(不存放任何的数据元素，next指向首元素即可)，队尾指针指向队列当前队尾元素所在的结点。 当队列为空时，队首指针与队尾指针均指向空的头结点 。

如图所示：

（1）所谓双端队列是指两端都可以进行进队和出队操作的队列，如下图所示，将队列的两端分别称为前端和后端，两端都可以入队和出队。其元素的逻辑结构仍是线性结构 。

在双端队列进队时：前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论前端出还是后端出，先出的元素排列在后出的元素的前面。

（2）输出受限的双端队列，即一个端点允许插入和删除，另一个端点只允许插入的双端队列。

（3）输入受限的双端队列，即一个端点允许插入和删除，另一个端点只允许删除的双端队列。

PS： 双端队列既可以用来队列操作，也可以用来实现栈操作（只操作一端就是栈了） 。

Stack类：栈类 ，过时

public class Stack<E> extends Vector<E> 

Queue：队列类

// 扩展了java.util.Collection接口 
public interface Queue<E> extends Collection<E>   

Deque：双端队列（栈操作建议使用）

//继承于Queue类
public interface Deque<E> extends Queue<E>  

特别注意： Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否。add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用element()或者peek()方法。

所以Java中实现栈和队列操作都可以通过使用LinkedList类实现，当然底层使用的链表，而ArrayDeque是Deque 接口的大小可变数组的实现 。

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, 
Cloneable, Serializabl

模拟生活中罗盘子案例 :

/** 
* 功能：模拟生活中罗盘子案例 
* 技能：LinkedList 
* 
* LinkedList既可以当做线性表处理，也可以当做栈、队列使用 
* @author Administrator* 
*/ 
public class TestDeque { public static void main(String[] args) { //创建一个栈 Deque deque =  new LinkedList();                 //罗盘子:入栈 
//                deque.addFirst("盘子1"); 
//                deque.addFirst("盘子2"); 
//                deque.addFirst("盘子3"); deque.push("盘子1"); deque.push("盘子2"); deque.push("盘子3");                 //获取最上面的盘子：获取栈顶元素 
//                System.out.println(deque.getFirst()); 
//                System.out.println(deque.getFirst()); 
//                System.out.println(deque.getFirst()); System.out.println(deque.peek()); System.out.println(deque.peek()); System.out.println(deque.peek());                 //拿走盘子：出栈 
//                System.out.println(deque.removeFirst()); 
//                System.out.println(deque.removeFirst()); 
//                System.out.println(deque.removeFirst()); System.out.println(deque.pop()); System.out.println(deque.pop()); System.out.println(deque.pop()); } } 

模拟生活中超市购物排队结算：

/** 
* 功能：模拟生活中超市购物排队结算 
* 技能：使用LinkedList实现队列的操作 
* 
* @author Administrator 
* 
*/ 
public class TestQueue { public static void main(String[] args) { //创建一个队列 java.util.Queue queue = new LinkedList();                 //入队 queue.offer("张三"); queue.offer("李四"); queue.offer("王五"); //获取队头元素 System.out.println(queue.element()); System.out.println(queue.element()); System.out.println(queue.element()); //出队 System.out.println(queue.remove()); System.out.println(queue.poll()); queue.offer("赵六"); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); } 
} 

借助栈实现进制转换（10----2）：

/** 
* 借助栈实现进制转换（10----2） 
* @author Administrator 
* 
*/ 
public class TestConversion { public static void main(String[] args) {                 int n = 13; int t = n; //String str = ""; Deque<Integer>  deque = new LinkedList<Integer>(); while(t>0){ //除以2得到余数作为二进制位 int mod = t%2; //System.out.print(mod); //str = mod + str; deque.push(mod); //除以2得到商作为被除数继续 int result = t/2; t = result; } System.out.print(n+"--------->"); while(!deque.isEmpty()){ System.out.print(deque.pop()); }                 } 
} 

好了，这篇文章我们大概了解到了线性结构相关的概念，下篇文章我们将继续探讨 非线性结构相关的知识。

如果博客中有什么不正确的地方，还请多多指点。如果这篇文章对您有帮助，请不要吝啬您的赞，欢迎继续关注本专栏。

谢谢观看。。。

友情提示：本博主纯手写的数据结构的源码我已上传到我的github：https://github.com/hkmhso/DataStructure.git