手写一个泛型双向链表
前言
在当前大环境的背景下面试不问点算法都不算个合格的面试了（卷），而与算法紧密相关的数据结构也是经常问到的，像集合、链表、树、图、栈、堆、队列、矩阵 等等等等。
是不是感觉难度如下：
- 集合：有手就行
- 链表：简简单单
- 队列：基础操作
- 二叉树：也还行吧
- 平衡二叉树：普普通通
- 红黑树：有点难度了
- 堆/栈：难度提升了
- 图：今天是高端局
这么一套组合拳下来，还是有点难度的，本篇就先手写简简单单的链表，链表里有单向链表跟双向链表，会双向链表还能不会单向链表吗，直接上双向链表。
属性定义
双向链表的属性内容上节点prev跟下节点next是肯定要有的，data属性我们使用泛型定义，这样一个双向链表的属性内容如下：
private class Node<T>{
private Node prev;
private T data;
private Node next;
public Node(LinkedTable.Node prev,T data,LinkedTable.Node next){
this.prev = prev;
this.data = data;
this.next = next;
}
}上面是存储节点的结构，实际对外的类要设置头部节点跟尾部节点，这样可以直接选择从头或者从尾遍历。
public Node headNode;
public Node tailNode;ADD方法
add方法没有返回值，在没有有参构造函数的情况下第一次进入add时类的属性内容都是空的，就是上面的headNode跟tailNode。
add的第一步：要先根据add的内容创建Node对象，前节点是当前的尾部节点，下一个节点没有
private void add(T data) {
Node node = new Node<>(tailNode,data,null);
}add的第二步：判断headNode跟tailNode都为空时进行初始化
private void add(T data) {
Node node = new Node<>(tailNode,data,null);
if (headNode == null && headNode == null){
headNode = node;
tailNode = node;
}
}add的第三步：判断尾部节点是否为空，不为空将尾部节点的next指向创建节点，替换尾部节点为当前节点
private void add(T data) {
Node node = new Node<>(tailNode,data,null);
if (headNode == null && headNode == null){
headNode = node;
tailNode = node;
}else{
if (tailNode != null){
tailNode.next = node;
}
tailNode = node;
}
}循环100次add方法进行验证，如下图：
尾部节点记录了循环最后一次的99，头部节点记录了循环第一次的0
DELETE方法
delete的第一步：定义局部变量引用头部节点，不影响头部跟尾部的节点位置
private void delete(T data) {
Node now = headNode;
}delete的第二步：while循环判断now节点非空
private void delete(T data) {
Node now = headNode;
while (now != null){
}
}delete的第三步：循环内判断now节点data值是否等于参数值，如果是将上个节点的next指针指向当前的下个节点，意思就是爷爷直接指向孙子，爸爸被删除了，然后直接返回。否则当前节点指向下个节点继续循环。
private void delete(T data) {
Node now = headNode;
while (now != null){
if (now.data == data){
now.prev.next = now.next;
return;
}
now = now.next;
}
}GET方法
既然放了数据肯定要原封不动的取出来，定义一个get方法，代码跟上面的删除一样，无非是把第三步修改一下
private T get(T data){
Node<T> now = headNode;
while (now != null){
if (now.data == data){
return now.data;
}
now = now.next;
}
return null;
}SET方法
set方法就当做覆盖更新，set指定位置的内容，这一步需要index标识。
private boolean set(Integer index, T data){
Node<T> now = headNode;
AtomicInteger i = new AtomicInteger(0);
while (now != null){
if (i.getAndAdd(1) == index){
now.data = data;
return true;
}
now = now.next;
}
return false;
}验证：
先add一个Map对象再add一个int值，这样链表的第一位为Map对象，再执行set方法将第一位Map对象修改为int值8546
public static void main(String[] args) {
LinkedTable table = new LinkedTable();
HashMap hashMap = new HashMap(){{
put("哈喽","xxx");
}};
table.add(hashMap);
table.add(1);
System.out.println(table);
table.set(0,8546);
System.out.println(table);
}第一个断点：目前第一个节点对象属性还是Map
第二个断点：现在第一个节点对象属性就变成了Integer
以上完成了一个双向链表基础的crud