我正在参加创作者训练营第6期，点击了解活动概况
前语
在当时大环境的背景下面试不问点算法都不算个合格的面试了（卷），而与算法严密相关的数据结构也是经常问到的，像集合、链表、树、图、栈、堆、行列、矩阵 等等等等。
是不是感觉难度如下：
- 集合：有手就行
- 链表：简简单单
- 行列：根底操作
- 二叉树：也还行吧
- 平衡二叉树：普普通通
- 红黑树：有点难度了
- 堆/栈：难度提升了
- 图：今天是高端局
这么一套组合拳下来，仍是有点难度的，本篇就先手写简简单单的链表，链表里有单向链表跟双向链表，会双向链表还能不会单向链表吗，直接上双向链表。
特点界说
双向链表的特点内容上节点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办法进行验证，如下图：
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
评论(0)