链表|手写一个泛型双向链表 java|数据结构

前言在当前大环境的背景下面试不问点算法都不算个合格的面试了（卷），而与算法紧密相关的数据结构也是经常问到的，像集合、链表、树、图、栈、堆、队列、矩阵 等等等等。
是不是感觉难度如下：

集合：有手就行
链表：简简单单
队列：基础操作
二叉树：也还行吧
平衡二叉树：普普通通
红黑树：有点难度了
堆/栈：难度提升了
图：今天是高端局

这么一套组合拳下来，还是有点难度的，本篇就先手写简简单单的链表，链表里有单向链表跟双向链表，会双向链表还能不会单向链表吗，直接上双向链表。
属性定义双向链表的属性内容上节点prev跟下节点next是肯定要有的，data属性我们使用泛型定义，这样一个双向链表的属性内容如下：

private class Node{private Node prev; private T data; private Node next; public Node(LinkedTable.Node prev,T data,LinkedTable.Node next){ this.prev = prev; this.data = https://www.it610.com/article/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 =https://www.it610.com/article/= data){ now.prev.next = now.next; return; } now = now.next; } }

GET方法既然放了数据肯定要原封不动的取出来，定义一个get方法，代码跟上面的删除一样，无非是把第三步修改一下

private T get(T data){ Node now = headNode; while (now != null){ if (now.data =https://www.it610.com/article/= data){ return now.data; } now = now.next; } return null; }

SET方法 set方法就当做覆盖更新，set指定位置的内容，这一步需要index标识。

private boolean set(Integer index, T data){ Node now = headNode; AtomicInteger i = new AtomicInteger(0); while (now != null){ if (i.getAndAdd(1) == index){ now.data = https://www.it610.com/article/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