# 链表的Java语言实现

***

> 这不是各种算法竞赛来了嘛，毕竟卷算法的大佬们走的都是C赛道，有言曰“人卷我逃，人逃我卷”，于是果断选择Java赛道。但是确实没打过Java赛道啊，赶紧用Java实现几个常用的算法和数据结构练练手。

在打C赛道的竞赛时，算法书都推荐使用结构体来实现链表，毕竟C语言还没有类，都是这么搞的。

但都1202年了，当然要用上~~现代化~~的面向对象了。毕竟古典的结构体实现方法和类很像，都有独立的多个对象和内置属性。而且java不需要指针了，好耶！

所以，开始吧\~

## 一、定义节点类

```java
class Node{
        int v;//节点值
        Node next;//下一个节点
    }
```

定义Node类，支持单向指向，包含一个携带的值和下一个节点的引用。

作为类，可以添加构造方法来初始化：

```java
Node(int value){
            v = value;
        }
```

写完以后就可以实操了。

## 二、创建链表

创建一个包含6个节点的链表：

```java
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. 遍历

```java
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. 插入节点

具体操作是先遍历到目标节点，然后新建节点使老节点指向它，然后再设置它的下一节点重新接回链表。

单独开个新方法实现比较好。

```java
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;
    }
```

然后在主程序里调用：

```java
insert(233 ,2,node_first);
```

输出效果：

> 0 1 2 233 3 4 5

### 3. 替换节点

把目标节点的下一个节点给它的前一个节点即可。

```java
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.删除节点

类似替换，只不过不建新节点了。

```java
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));` 根据索引获取元素

......


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/shu-ju-jie-gou/lian-biao-de-java-yu-yan-shi-xian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.