单向链表 – 玩算法

链表（Linked list）是一种物理存储单元上非连续的数据结构、数据元素的逻辑顺序是通过链表中的指针实现的。由于不必按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，但链表查找的时候由于不能通过索引查找，所以查找的时间复杂度是 O(n) 。常见的链表有单向链表，双向链表，以及环形链表。

单向链表

单向链表是最简单的一种链表，一般只包含存储的数据和指针（这里的指针不是 C 语言中的地址指针，他是下一个节点的引用），每个指针指向下一个节点，最后一个节点指向空，如下图所示。为了方便在尾部添加节点，我们新增一个 tail 变量，指向链表的尾节点。

单向链表的节点类如下：

private class LinkNode {
    int val;// 节点中存储的数据。
    LinkNode next;// 指向下一个节点的指针。

    public LinkNode(int val, LinkNode next) {
        this.val = val;
        this.next = next;
    }
}

单向链表的插入

链表的插入分 3 种情况，一种是在头部插入，一种是在尾部插入，一种是在中间插入。在头部插入完之后要更新 head 节点，在尾部插入完之后要更新 tail 节点，如下图所示。

插入节点之前必须要找到插入位置的前一个节点，来看下代码：

// 在链表中插入节点。
public void insert(int index, int val) {
    if (index == 0) {// 插入的是头节点。
        head = new LinkNode(val, head);// 创建头节点赋值给 head 。
        if (size == 0)// 如果之前链表为空，让 tail 也指向 head 。
            tail = head;
    } else if (index == size) {// 在链表末尾添加
        tail.next = new LinkNode(val, null);// 创建尾节点。
        tail = tail.next;// 更新尾节点。
    } else {// 在中间添加。
        LinkNode preNode = findPre(index);// 查找 index 节点的前一个节点。
        preNode.next = new LinkNode(val, preNode.next);// 添加新节点。
    }
    size++;// 节点个数加 1 。
}

对于链表的头和尾插入比较简单，我们来分析下链表中间节点的插入。

单向链表的删除

链表的删除和插入类似，也分 3 种情况，如果是在头部或者尾部删除要记得更新 head 或者 tail 节点。在删除节点之前要找到待删除节点的前一个节点，让待删除节点的前一个节点指向待删除节点的下一个节点即可。

来看下代码：

// 删除节点。
public int remove(int index) {
    if (size == 0)
        throw new IllegalStateException("链表是空的，没法删除……");
    LinkNode delete;// 待删除的节点。
    if (index == 0) {// 删除的是头节点。
        delete = head;// 记录待删除的节点。
        head = head.next;// 更新 head 节点。
        if (head == null)// 如果链表为空，让 tail 也为空。
            tail = null;
    } else {// 删除的不是头节点。
        LinkNode preNode = findPre(index);// 查找删除节点的前一个节点。
        if (index == size - 1) {// 删除的是尾节点。
            delete = preNode.next;
            preNode.next = null;// 删除尾节点。
            tail = preNode;// 更新尾节点。
        } else {// 删除的是中间节点。
            delete = preNode.next;
            preNode.next = delete.next;// 删除节点。
        }
    }
    delete.next = delete;// gc，自己指向自己。
    size--;// 节点个数减 1 。
    return delete.val;// 返回删除节点的值。
}

最后我们再来看下单链表的完整代码。

private LinkNode head;// 头节点。
private LinkNode tail;// 尾节点。
private int size;// 链表的长度。

// 在尾部添加节点。
public void add(int val) {
    insert(size, val);
}

// 删除头节点
public int poll() {
    return remove(0);
}

// 在链表中插入节点。
public void insert(int index, int val) {
    if (index == 0) {// 插入的是头节点。
        head = new LinkNode(val, head);// 创建头节点赋值给 head 。
        if (size == 0)// 如果之前链表为空，让 tail 也指向 head 。
            tail = head;
    } else if (index == size) {// 在链表末尾添加
        tail.next = new LinkNode(val, null);// 创建尾节点。
        tail = tail.next;// 更新尾节点。
    } else {// 不在末尾添加。
        LinkNode preNode = findPre(index);// 查找 index 节点的前一个节点。
        preNode.next = new LinkNode(val, preNode.next);// 添加新节点。
    }
    size++;// 节点个数加 1 。
}

// 删除节点。
public int remove(int index) {
    if (size == 0)
        throw new IllegalStateException("链表是空的，没法删除……");
    LinkNode delete;// 待删除的节点。
    if (index == 0) {// 删除的是头节点。
        delete = head;// 记录待删除的节点。
        head = head.next;// 更新 head 节点。
        if (head == null)// 如果链表为空，让 tail 也为空。
            tail = null;
    } else {// 删除的不是头节点。
        LinkNode preNode = findPre(index);// 查找删除节点的前一个节点。
        if (index == size - 1) {// 删除的是尾节点。
            delete = preNode.next;
            preNode.next = null;// 删除尾节点。
            tail = preNode;// 更新尾节点。
        } else {// 删除的是中间节点。
            delete = preNode.next;
            preNode.next = delete.next;// 删除节点。
        }
    }
    delete.next = delete;// gc，自己指向自己。
    size--;// 节点个数减 1 。
    return delete.val;// 返回删除节点的值。
}

// 查找 index 节点的前一个节点。
LinkNode findPre(int index) {
    // index 必须是有效的，不能越界。查找前一个，index可以等于size。
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("越界了……");
    if (index == 0)// 头节点的前一个是空节点。
        return null;
    LinkNode preNode = head;
    for (int i = 0; i < index - 1; i++)
        preNode = preNode.next;
    return preNode;
}

// 节点的个数。
public int size() {
    return size;
}

// 清空链表。
public void clear() {
    while (head != null) {
        LinkNode next = head.next;
        head.next = head;// 自己指向自己。
        head = next;
    }
    tail = null;
    size = 0;
}

上面代码在节点删除和添加的时候有可能会导致头节点不停的变动，我们还可以在链表的前面添加一个哑节点 dummy ，这个哑节点不存储任何数据，他的 next 指针始终指向原链表的头节点，如下图所示。

这样在添加和删除的时候就不需要在判断是否是头节点了，来看下代码：

private LinkNode dummyNode = new LinkNode(-1, null);// 哑节点。
private int size;// 链表的长度。

// 在尾部添加节点。
public void add(int val) {
    insert(size, val);
}

// 删除头节点
public int poll() {
    return remove(0);
}

// 在链表中插入节点。
public void insert(int index, int val) {
    LinkNode preNode = findPre(index);// 查找 index 节点的前一个节点。
    preNode.next = new LinkNode(val, preNode.next);// 添加新节点。
    size++;// 节点个数加 1 。
}

// 删除节点。
public int remove(int index) {
    if (size == 0)
        throw new IllegalStateException("链表是空的，没法删除……");
    LinkNode preNode = findPre(index);// 查找删除节点的前一个节点。
    LinkNode delete = preNode.next;// 记录待删除的节点。
    preNode.next = delete.next;// 删除节点。
    delete.next = delete;// gc，自己指向自己。
    size--;// 节点个数减 1 。
    return delete.val;// 返回删除节点的值。
}

// 查找 index 节点的前一个节点。
LinkNode findPre(int index) {
    // index 必须是有效的，不能越界。查找前一个，index可以等于size。
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("越界了……");
    LinkNode preNode = dummyNode;
    for (int i = 0; i < index; i++)
        preNode = preNode.next;
    return preNode;
}

// 节点的个数。
public int size() {
    return size;
}

// 清空链表。
public void clear() {
    LinkNode cur = dummyNode.next;
    while (cur != null) {
        LinkNode next = cur.next;
        cur.next = cur;// 自己指向自己。
        cur = next;
    }
    dummyNode.next = null;
    size = 0;
}

相关链接

数组	数组，滚动数组，差分数组，树状数组
链表	链单向表，双向链表，循环链表，跳表，异或链表
队列	队列，循环队列，双端队列
栈	栈
散列表	散列表
树	二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树
堆	堆
图	图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序