theme: juejin

链表本质

链表也是线性数据结构，和数组（一块连续的内存空间）不同的是，链表是一组零散的内存块，内存块之间使用“指针”相连。

⨳ 线性数据结构：和数组一样，数据只有前后两个方向

⨳ 零散的内存块：我们把内存块称为链表的节点，节点除了存储数据之外，还需要记录链上的下一个节点（后继节点）的地址。

class Node{
    E e; // 存储数据
    Node next; // 后继指针，指向下一个节点
}

我们习惯性地把链表的第一个节点叫作头节点，最后一个节点叫作尾节点。

▪ 头节点用来记录链表的基地址，有了它，我们就可以遍历得到整条链表；

▪ 尾节点的指针不是指向下一个节点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

前面我们使用数组的时候，必须要指明容量，添加的元素个数超过数组容量时，还要再声明一个更大容量的新数组，这都是因为数组是需要一块连续的内存。

比如我们申请一个 100MB 大小的数组，当内存中没有连续的的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。

而链表才是真正的动态结构，链表容量不需要提前声明，随用随声明内存空间，完全不需要考虑容量问题。

如果内存中没有连续 100MB 的空间，没关系只要剩余空间加起来够用，就可以使用链表将零散的内存块串起来。

虽然链表更加灵活，但是也失去了数组的随机访问能力，毕竟谁知道节点地址是个什么规律，节点可能存储在任意地方。

自定义链表 IntList

数组那篇，模仿 ArrayList 自定义了只能存储整型的 IntArray，现在模仿 LikedList 自定义只能存储整型的 IntList，通过它来熟悉链表的增删改查。

链表初始化

因为链表是用节点存储数据的，在链表内部声明一个内部类 Node：

public class IntList {
    // 节点
    private class Node{
        public int e;
        public Node next;

        public Node(int e, Node next){
            this.e = e;
            this.next = next;
        }

    }

    private Node head; // 头节点
    private int size;  // 链表长度
    
    public IntList(){
        head = null;
        size = 0;
    }
    
}

除了节点的结构之外，还有两个成员属性：

⨳ Node head：链表的头节点，毕竟拿到头节点才能将整个链表串起来

⨳ int size：链表的长度，虽然非必须，有它还是方便点

在指定位置添加元素

// 在链表 index 位置添加新的元素e
public void add(int index, int e){

    if(index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Illegal index.");

    // 在链表头部插入节点
    if(index == 0){
        // 创建一个数据节点，后继指针指向 null
        Node new_node = new Node(e,null);
        // 将新创建的节点，指向原头节点
        new_node.next = head;
        // 新创建的节点，作为新的头节点
        head = new_node;
        // 链表长度加一
        size ++;
        return;
    }

    // 在链表非头部添加元素
    // 创建一个数据节点，后继指针指向 null
    Node new_node = new Node(e,null);
    // 从头节点开始遍历，找到插入的位置 index 前一个节点 和 index 原位置上的节点
    Node prev_node = head; // index 前一个节点（用于挂载新节点）
    for(int i = 0 ; i < index - 1 ; i ++)
        prev_node = prev_node.next;
    
    Node index_node = prev_node.next; // 原 index 位置的节点（要挂载到新节点上）
    new_node.next = index_node; // index 前一个节点，指向新节点
    prev_node.next = new_node;  // 新节点 指向 原 index 位置的节点
    size ++;
    
}

添加逻辑分成了两部分，都很好理解：

⨳ 在链表头部插入节点：将新创建的节点的后继指针指向原head节点，新创建的节点成为为新的head节点

head = new Node(e,head); // 三合一

⨳ 在链表非头部添加节点：将新创建的节点的后继指针指向原index位置节点，原index位置上一个节点指针指向新节点

prev_node.next = new Node(e, prev_node.next); // 三合一

怎么感觉逻辑不统一呢？能不能将在链表头部插入节点，统一到在链表非头部添加节点逻辑中呢？

这就需要引入一个虚拟头部节点（dummyHead），虚拟头部节点不存储数据，只占位置，虚拟头部节点下一个节点才是真正存储数据的头部节点，这样操作头部节点就像操作其他非头部节点一样了。

public class IntList {
    // 节点
    private class Node{
        public int e;
        public Node next;

        public Node(int e, Node next){
            this.e = e;
            this.next = next;
        }

    }

    private Node dummyHead; // 虚拟头节点
    private int size;  // 链表长度

    public IntList(){
        dummyHead = new Node(0,null);
        size = 0;
    }

    // 在链表 index 位置添加新的元素e
    public void add(int index, int e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        // 在链表非头部添加元素
        // 从头节点开始遍历，找到插入的位置 index 前一个节点 和 index 原位置上的节点
        Node prev_node = dummyHead; 
        for(int i = 0 ; i < index ; i ++)
            prev_node = prev_node.next;
        prev_node.next = new Node(e, prev_node.next);
        size ++;

    }

在链表头部添加节点，就是 add(0,e)；在数组尾部添加节点，就是 add(size,e)。

在指定位置删除元素

    ```
// 删除链表index位置上的元素，返回删除的元素
public int remove(int index){
    if(index < 0 || index >= size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");

    Node prev = dummyHead;      // index 位置前置节点
    for(int i = 0 ; i < index ; i ++)
        prev = prev.next;

    Node index_node = prev.next; // index位置节点
    prev.next = index_node.next; // 将 index_node 前置节点的指针，指向 index_node 的后继节点
    index_node.next = null; // 重置 index_node 的指针
    size --;
    return index_node.e;
}

无论是在链表中添加元素还是在链表中删除元素，都不像数组那样要进行数据的搬移，仅仅移动几个指针即可，时间复杂度为 O(1)。

所以有种说法是，链表的插入和删除是比数组快的，但这样说是不严谨的，毕竟链表不支持随机寻址，要找到插入或删除位置，都需要从头到尾遍历链表，而遍历操作的时间复杂度还是 O(n)。

下面看一下使用链表的遍历，来查询与修改元素。

在指定位置获取和修改元素

// 获得链表 index 位置上的元素
public int get(int index){

    if(index < 0 || index >= size)
        throw new IllegalArgumentException("Get failed. Illegal index.");

    Node cur = dummyHead.next;
    for(int i = 0 ; i < index ; i ++)
        cur = cur.next;
    return cur.e;
}

// 修改链表 index 位置上的元素 
public void set(int index, int e){
    if(index < 0 || index >= size)
        throw new IllegalArgumentException("Set failed. Illegal index.");

    Node cur = dummyHead.next;
    for(int i = 0 ; i < index ; i ++)
        cur = cur.next;
    cur.e = e;
}

以上，关于链表的增删改查讲完了，上述链表只能称之为单向链表，单向链表顾名思义，就是只能一个方向进行遍历的链表，另外还有其他不同的链表：循环链表、双向链表 和 双向循环链表。

循环链表

循环链表是单向链表的变体，它与单链表唯一的区别就是，尾节点（最后一个节点）的指针指向头节点（第一个节点），形成了一个环状结构。

循环链表在链表中间添加或删除节点和单向链表是一模一样的，只是有个特例就是当链表只有头节点的时候，需要自己指向自己，但是一旦循环链表成型，即使在头部插入节点，也相当于在链表中间插入节点，只不过头部节点的前一个节点是尾节点：

prev_node.next = new Node(e, prev_node.next);

因为头部节点的特殊性（一个节点的时候自己指向自己，多个节点的是尾节点指向自己），所以再使用虚拟头节点就显得不必要了，但增加一个尾节点属性还是不错的，方便在头部插入节点：

public class IntCircleList {

    private class Node {
        public int e;
        public Node next;

        public Node(int e, Node next) {
            this.e = e;
            this.next = next;
        }
    }


    private Node head; // 头节点
    private Node tail; // 尾节点
    private int size;  // 链表长度

}

这时在链表指向位置插入元素为：

// 在链表 index 位置添加新的元素e
public void add(int index, int e){

    if(index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Illegal index.");

    Node new_node = new Node(e,null);
    // 空链表插入
    if(head == null){
        head = new_node;
        tail = new_node;  // 头节点也是尾节点
        head.next = head; // 自己指向自己
        size ++;
        return;
    }
    // 在头节点插入
    if(index==0){
        tail.next = new_node;
        new_node.next = head;
        head = new_node;
        size ++;
        return;
    }
    // 在链表非头部添加元素
    // 从头节点开始遍历，找到插入的位置 index 前一个节点 和 index 原位置上的节点
    Node prev_node = head; // index 前一个节点（用于挂载新节点）
    for(int i = 0 ; i < index - 1 ; i ++)
        prev_node = prev_node.next;

    Node index_node = prev_node.next; // 原 index 位置的节点（要挂载到新节点上）
    new_node.next = index_node; // index 前一个节点，指向新节点
    prev_node.next = new_node;  // 新节点 指向 原 index 位置的节点
    // 如果在链表尾部添加，还要更新一下尾节点
    if(index==size){
       tail = new_node;
    }
    size ++;

}

实现起来看起来挺复杂的，这主要是分了几种情况的原因。

使用循环链表可以很方便的解决约瑟夫问题（Josephus problem）：

问题描述如下：假设有n个人（编号从1到n）围坐在一起，从第一个人开始报数，报到m的人离开座位，剩下的人继续从1开始报数，直到最后只剩下一人时游戏结束。问题通常是求最后剩下的那个人的编号。

我们可以创建一个循环链表，其中每个节点表示一个人，然后不断循环删除第m个节点，直到只剩下一个节点。这个最后留下来的节点即为问题的解。

具体代码就不写了。

双向链表

单向链表只有一个方向，节点只有一个后继指针 next 指向后面的节点。而双向链表支持两个方向，每个节点不止有一个后继指针 next 指向后面的节点，还有一个前驱指针 prev 指向前面的节点。

将双向链表和循环链表结合起来就是双向循环链表：

具体代码就不写了，总的来说，不管链表怎么变，处理链表问题都要注意维护节点的指针指向，指针指来指去，一定要谨慎，特别是链表为空的时候，处理链表头尾节点的时候，如果想不清楚，画个图帮助理解是个很好的方法。