迷人的链表（bushi）

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

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

什么是链表？

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

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

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

链表的分类？

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

不再赘述，见维基百科：

链表的创建

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

或许有点过于麻烦了，我们看力扣中是怎么定义的：

/**
 * 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; }
 * }
 */

还有一种常见的定义，经常用于算法比赛中：

public class ListNode {
    public int val;
    public ListNode next;

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

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

链表的CRUD

先来链表的查询，也就是链表的遍历

public static int getListLength(Node head){

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

链表的插入

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

1. 链头插入

Node node = head;
node.next = head;
head = node; 

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

3. 尾部插入