链表的Java语言实现

---

这不是各种算法竞赛来了嘛，毕竟卷算法的大佬们走的都是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)); 根据索引获取元素

......