这不是各种算法竞赛来了嘛，毕竟卷算法的大佬们走的都是C赛道，有言曰“人卷我逃，人逃我卷”，于是果断选择Java赛道。但是确实没打过Java赛道啊，赶紧用Java实现几个常用的算法和数据结构练练手。
在打C赛道的竞赛时，算法书都推荐使用结构体来实现链表，毕竟C语言还没有类，都是这么搞的。
但都1202年了，当然要用上现代化的面向对象了。毕竟古典的结构体实现方法和类很像，都有独立的多个对象和内置属性。而且java不需要指针了，好耶！
所以，开始吧~
一、定义节点类
class Node{
int v;//节点值
Node next;//下一个节点
}
定义Node类，支持单向指向，包含一个携带的值和下一个节点的引用。
作为类，可以添加构造方法来初始化：
Node(int value){
v = value;
}
写完以后就可以实操了。
二、创建链表
创建一个包含6个节点的链表：
class Node{
int v;//节点值
Node next;//下一个节点
Node(int value){
v = value;
}
}
class node_in_java {
public static void main(String[] args){
Node node_first = new Node(0); //新建起始点
Node node_now = node_first; //
for(int i =1;i<=5;i++){ //新建几个node连在一起
Node new_node = new Node(i); //新建Node对象
node_now.next = new_node; //连接新节点
node_now = new_node; //重设下一个要连接的节点
}
}
}
注意Node类要写在程序主类的外面，否则main函数是没法直接创建非静态子类的对象的。
另外还要注意起始点一定要存下来，用起点来代表整个列表，不然没有引用了整个列表就找不到了。
三、链表的基本操作
创建完链表以后，下面对链表进行一些基本操作。
1. 遍历
node_now = node_first;
System.out.println(node_now.v); //首节点单独输出
while(node_now.next != null){
node_now = node_now.next; //切目标节点为下一个
System.out.println(node_now.v); //输出当前节点值
}
遍历结束的条件是当前Node的next为null，即没有被分配下一个的点，就是结尾了。
输出结果：
0 1 2 3 4 5
2. 插入节点
具体操作是先遍历到目标节点，然后新建节点使老节点指向它，然后再设置它的下一节点重新接回链表。
单独开个新方法实现比较好。
static void insert(int v,int num,Node start){
//插入节点，在第n个节点（0开始）后插入值为v的点
int count = 0;
Node now = start;
while(count != num){
now = now.next;
count++; //找到目标节点
}
Node target_next = now.next; //存下目标节点的下一个节点等待接回
Node new_node = new Node(v);
now.next = new_node;
new_node.next = target_next;
}
然后在主程序里调用：
insert(233 ,2,node_first);
输出效果：
0 1 2 233 3 4 5
3. 替换节点
把目标节点的下一个节点给它的前一个节点即可。
static void replace(int v, int num, Node start){
//替换节点，把num号节点换成值为v的新节点
int count = 0;
Node now = start;
while(count != num-1){ //注意到目标前一个就可以停了
now = now.next;
count++;
}
Node new_node = new Node(v); //建新节点
new_node.next = now.next.next; //先改被替换点前面那个点的指针
now.next = new_node; //再把目标节点换掉
new_node.v = v; //记得赋值
}
4.删除节点
类似替换，只不过不建新节点了。
static void delete(int num, Node start){
//删除节点
int count = 0;
Node now = start;
while(count != num-1){ //注意到目标前一个就可以停了
now = now.next;
count++;
}
now.next = now.next.next; //优雅而简洁
}
其他
链表的意义在于删除/替换/插入节点效率相较于普通数组更快。如果要遍历的话，效率反而更慢。
Java其实自带了LinkedList类，可以直接使用。那我为什么还要手写
用法：
LinkedList<String> sites = new LinkedList<>(); 声明链表
sites.add("mcyou.cn"); 添加元素
System.out.println(sites.get(1)); 根据索引获取元素
......
