# 迷人的链表（bushi）

> 今天开始算法专栏，从链表开始，每日一栏
> if not now,when?
> if not me,who?
> 此时此刻，非我莫属！

算法的基础是数据结构，数据结构的基础是`创建` + `CURD`

## 什么是链表？

顾名思义，链表就是一个链状表，是一种常见的基础的数据结构，是一种线性表，但是无序，因此，插入时间复杂度是O（1），查找的话，需要遍历，时间复杂度为O（n）。

## 为什么会存在链表这个数据结构呢？

因为数组的声明需要声明数据空间大小，于是链表这一个不用声明大小的数据结构就出来了，优点就是可以充分利用计算机存储空间，实现内存动态管理；缺点就是失去了数组随机读取的功能，同时链表还增加了结点指针，增加了空间开销。

## 链表的分类？

链表又划分为单向链表、双向链表、循环链表以及不常见的块状链表。

不再赘述，见维基百科：

![单向链表](https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202403021118814.png)

![双向链表](https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202403021118705.png)

![循环链表](https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202403021118706.png)

![块状链表](https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202403021118708.png)

![其他扩展](https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202403021118710.png)

## 链表的创建

Java 中规范的链表创建方法：
```java
public class ListNode {
    private int data;
    private ListNode next;
    public ListNode(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }
}
```

或许有点过于麻烦了，我们看力扣中是怎么定义的：
```txt
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
```

还有一种常见的定义，经常用于算法比赛中：
```java
public class ListNode {
    public int val;
    public ListNode next;

    ListNode(int x) {
        val = x;
        //这个一般作用不大，写了会更加规范
        next = null;
    }
}
ListNode listnode=new ListNode(1);
```

ok，以上就是链表的创建了。

## 链表的CRUD

### 先来链表的查询，也就是链表的遍历
```java
public static int getListLength(Node head){

    int length = 0;
    Node node = head;
    while(node != null) {
        length++;
        node = node.next;
    }
    return length;
} 
```

### 链表的插入
分三种情况，分别是从链头插入、中间插入、链尾插入

1. 链头插入
```java
Node node = head;
node.next = head;
head = node; 
```

2. 中间插入
中间插入要注意一个顺序，就是不能使链表断开；
正确的顺序应该是先new.next = node.next; 然后node.next = new;

3. 尾部插入
