链表

是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。它通过“指针”将一组零散的内存块串联起来使用。

//单向链表基本结构
int value;        //值
ListNode next;    //下一个结点的引用，指向下个结点的value，next指向NULL代表链表尾部

private ListNode head;//头节点
private int size = 0;//大小
//头指针————指向第一个结点的指针，无论链表空或不空，头指针皆不为空（是链表的必要元素）
//头节点————用来方便操作同步所设立，在第一个元素之前，能同步第一个结点的删除和插入操作（不是所有的链表都有）

链表的应用场景
LRU[缓存淘汰策略]
维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1. 如果此数据之前表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：
   1. 如果此时缓存未满，则将此结点直接插入到链表的头部；
   2. 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

链表的分类

• 单向链表

单链表存在两个比较特殊的节点，分别是头节点和尾节点，他们的“指针”并不是指向下一个节点的位置，头指针则是记录了整个链表的基地址，尾指针则是指向 null。

• 双向链表 —— 在单向链表的基础上增加了向前的结点

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。

B+ 中的应用为，双向链表，在查询范围时，可自某一结点向前进行遍历。

进行删除，添加等操作时，注意结点书写顺序，以避免之后的结点遍历不到。

• 循环链表 —— 尾部 next 指向头节点

和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的 约瑟夫问题。

• 双向循环链表 —— 双向链表和循环链表的结合

优缺点

• 查询需从头开始遍历链表时间复杂度为 O(n)，不如顺序结构的数组
• 插入和删除操作时间复杂度为 O(1)，前提是找到那个结点。（头插法和头删除整体时间复杂度为 O（1））
• 空间上多使用了一个 next 结点（双向链表还多了一个 pre 结点），链表长度不受限制（小于内存）

链表的插入

public void insertHead(int data) {        //插入链表的头部    头插法
    ListNode newNode = new ListNode(data);
    //无需考虑链表是否为null，或后面是否有数据
    newNode.next = head;        //栈内存的引用
    head = newNode;
    //插入O(1)
}

public void insertNth(int data, int position) {        //插入链表的中间 假设定义在第N个插入 O(n)
    if (position == 0) {        //这个表示插入在头部了
        insertHead(data);
    } else {
        ListNode cur = head;
        for (int i = 1; i < position; i++) {//遍历到要插入结点的前一个结点
            cur = cur.next;        //一直往后遍历   p=p->next;  ->是c++里面的往后找指针
        }
        ListNode newNode = new ListNode(data);
        //最核心的两行
        newNode.next = cur.next;        //新加的点指向后面 保证不断链
        cur.next = newNode;            //把当前的点指向新加的点
    }
}

在单向链表一节点前插入节点
在单项链表中往一个节点前面插入节点的时候的时候需要额外获取当前节点节点的前驱节点，仅仅拿到当前节点无法将链表重新链接起来。

链表的删除

public void deleteHead() {//删除头节点 O(1)
    head = head.next;//直接将头节点的指针指向本结点的next
}

public void deleteNth(int position) {//删除指定位置的结点 O(n)
    if (position == 0) {
        deleteHead();
    } else {
        ListNode cur = head;
        for (int i = 1; i < position; i++) {//遍历到指定结点的前一个结点
            cur = cur.next;
        }
        cur.next = cur.next.next; //cur.next 表示的是删除的点，后一个next就是我们要指向的
    }
}

单向链表删除节点的注意事项
在单项链表中删除一个节点的时候需要额外获取所删除节点的前驱节点，仅仅拿到需要删除的节点无法将链表重新链接起来。

链表的查询

public void find(int data) {//自头节点向后一个接一个的查询比较 O(n)
    ListNode cur = head;
    while (cur != null) {
        if (cur.value == data) {
            break;
        }
        cur = cur.next;
    }
}