链表的学习：链表的头插法和尾插法以及HashMap中链表结点的插入方式
前言
从前面的HashMap和ConcurrentHashMap的源码分析我们可以得知，其内部的数据结构都用到了链表，所以，对链表的深入掌握非常有必要。本文将重点介绍单链表数据结构，然后通过代码实现单链表的头插法和尾插法。
单链表的介绍
我们都知道数组是需要一块连续的内存空间来存储的，而链表只需要零散的内存碎片，通过指针相连即可。首先我们来看看最简单的链表-----单链表。
如上图所示，分别是一个长度为6的数组，和一个长度为6的单链表。链表中的每个内存块成为“结点（Node）” ，每个结点Node包含两部分，数据域data和后继指针next，数据域用于存储数据，next指针用于指向下一个结点的地址。单链表中的第一个结点成为头结点，头结点记录了链表的基地址，通过头结点可以遍历整个链表，最后一个结点称之为尾结点，尾结点的特殊之处在于其next指针指向的不是下一个结点地址，而是空地址NULL。
链表和数组的时间复杂度
插入、删除操作时，为了保存数据的连续性，需要进行数据的搬移，时间复杂度是o(n),链表中插入和删除一个元素，不需要搬移结点，只需要考虑相邻结点的指针改变。时间复杂度是O(1)。但是在查找数据的时候数组可以通过地址的索引快速找到某个元素，所以查找的时间复杂度是O(1)。而链表由于是不连续的，所以查找某个元素时必须从头结点开始遍历链表，所以查找的时间复杂度是O(n)。如下图片：
单链表的实现
定义单链表的数据结构
class Node {
/**
* 数据域
*/
Object value;
/**
* 下一个结点对象的引用
*/
Node next;
public Node(Object value, Node next) {
this.value = value;
this.next = next;
}
public Node(Object value) {
this.value = value;
}
public Node(Node next) {
this.next = next;
}
}
如上定义了Node类有两个属性，一个是value，存储数据，一个是next用于存储下一个节点的引用。
单链表的操作
public class SingleLinkList {
/**
* 头结点
*/
private Node head;
/**
* 当前节点
*/
private Node current;
/**
* 大小
*/
private int size;
public SingleLinkList() {
//默认头结点为null
head = current = new Node(null);
size = 0;
}如上定义了头结点head和当前节点current。当初始化链表时，默认头结点为null。作为一个基地址。并将current节点赋值给head。
插入节点
尾插法
尾插法的逻辑比较简单，就是遍历链表，条件是current.next!=null，即找到尾节点。然后，将current的next指针指向要插入的结点。通过要插入结点的next指针指向空地址null。
public void addLast(Object value) {
Node newNode = new Node(value);
while (current.next != null) {
//获取尾结点
current = current.next;
}
current.next = newNode;
newNode.next = null;
++size;
}头插法
头插入的逻辑与尾插法相反，头插法只需要找到头结点，然后将要插入结点的next指针指向current结点。并将头结点的next指针指向要插入的结点。
public void addHead(Object value) {
Node newNode = new Node(value);
int j = 0;
//后一个结点
current = head;
if (current.next != null && j == 0) {
//获取尾结点
current = current.next;
}
newNode.next = current;
head.next = newNode;
++size;
}指定位置插入元素
在指定位置插入元素的，主要就是遍历找到需要插入结点的位置。如下，比如要想位置i上插入一个新结点。那么首先需要找到位置i的前后两个节点。如下，前一个节点是pre,后一个结点是current结点。找到之后，只需要将pre的next指针指向newNode。然后，将新结点的next指针指向current结点。
public void insert(int i, Object value) {
Node newNode = new Node(value);
//前一个结点
Node pre = head;
//后一个结点
current = head.next;
int j = 0;
while (current != null && j < i) {
pre = current;
current = current.next;
j++;
}
pre.next = newNode;
newNode.next = current;
++size;
}删除节点
删除指定位置的结点与向指定位置插入结点类似，只需要找到指定位置的前一个节点和后一个节点，然后将前一个节点的next指针指向后一个节点的next引用。
public void delete(int i) {
Node pre = head;
current = head.next;
int j = 0;
while (current != null && j < i) {
pre = current;
current = current.next;
j++;
}
pre.next = current.next;
size--;
}
查找指定位置的值
同样的首先确定头结点，然后遍历链表，条件是current.next != null && j < i，在循环里不断的将current节点向前移。
public Object getValue(int i) {
current = head.next;
int j = 0;
while (current.next != null && j < i) {
current = current.next;
j++;
}
return current.value;
}测试
如下，分别进行了 1.初始化一个长度为6的链表 2.在Node3和Node4结点之间插入Node7 3.在链表头部插入元素Node8 4.删除第Node3结点 5.获取第五位的节点
public static void main(String[] args) {
SingleLinkList singleLinkList = new SingleLinkList();
//初始化一个长度为6的链表
for (int i = 1; i < 7; i++) {
singleLinkList.addLast("Node" + i);
}
System.out.println("初始化一个长度为6的链表之后\n"+singleLinkList.printLinkList());;
//在Node3和Node4结点之间插入Node7
singleLinkList.insert(2, "Node7");
System.out.println("在Node3和Node4结点之间插入Node7之后\n"+singleLinkList.printLinkList());;
//在链表头部插入元素Node8
singleLinkList.addHead("Node8");
System.out.println("在链表头部插入元素Node8之后\n"+singleLinkList.printLinkList());;
//删除第Node3结点
singleLinkList.delete(2);
System.out.println("删除第Node3结点之后\n"+singleLinkList.printLinkList());;
//获取第五位的节点
String value = (String) singleLinkList.getValue(4);
System.out.println("*******第五位的获取到的节点是"+value);
}测试结果
HashMap中链表是头插法还是尾插法
JDK1.7以前的版本
如果遍历链表都没法发现相应的key值的话，则会调用addEntry方法在链表添加一个Entry，重点就在于addEntry方法是如何插入链表的，addEntry方法源码如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
这里构造了一个新的Entry对象（构造方法的最后一个参数传入了当前的Entry链表），然后直接用这个新的Entry对象取代了旧的Entry链表，可以猜测这应该是头插法，为了进一步确认这个想法，我们再看一下Entry的构造方法：
Entry( int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}从构造方法中的nexrt=n可以看出确实是把原本的链表直接链在了新建的Entry对象的后边，可以断定是插入头部。
JDK1.8 版本
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}如上代码，遍历链表，当找到尾节点之后，就将p节点的next指针指向新插入的节点。所以，可以判定JDK1.8版本下，链表的插入是尾插入的。
参考
06 | 链表（上）：如何实现LRU缓存淘汰算法?[1] 单链表---java实现[2] HashMap到底是插入链表头部还是尾部[3]
源码地址
https://github.com/XWxiaowei/ConcurrencyDemo/blob/master/concurrency-demo/src/main/java/chapter_4/linkList/SingleLinkList.java
References
[1] 06 | 链表（上）：如何实现LRU缓存淘汰算法?: https://time.geekbang.org/column/article/41013
[2] 单链表---java实现: https://www.jianshu.com/p/8c6bf1b37ea1
[3] HashMap到底是插入链表头部还是尾部: https://blog.csdn.net/qq_33256688/article/details/79938886
腾讯云开发者
