08.数据结构：第一个动态结构-链表

大家好，我是王有志。

今天我们一起学习线性表中的第二种数据结构：链表，也是真正意义上的第一个动态数据结构。

今天的内容分为3个部分：认识链表，链表的形式和单向链表的实现。

什么是链表

在07.数据结构：线性表入门中，我们知道数组使用连续的内存，可如果程序已经运行了很久，内存中没有足够的连续内存，这时需要一个线性表结构，除了使用360安全卫士清理内存外，该怎么办呢？

早在1955年就有人想到了这个问题，从而诞生了一种影响深远的数据结构-链表。

链表开发于1955-56，由当时所属于兰德公司（英语：RAND Corporation）的艾伦纽维尔（Allen Newell），克里夫肖（Cliff Shaw）和赫伯特西蒙（Herbert Simon）在他们编写的信息处理语言（IPL）中做为原始数据类型所编写。IPL被作者们用来开发几种早期的人工智能程序，包括逻辑推理机，通用问题解算器和一个计算机象棋程序。

以上来源于维基百科的链表。

在02.预备知识：概念和存储结构
中，我们讲到链式存储结构，链表正是这样一种结构：

链式分配内存.png
可以看到，链表使用分散在内存各个角落的内存块，通过“一根线”将内存块”串“起来。

得益于链式存储结构，我们可以很容易的为链表动态扩缩容，通常我们会称这种为动态数据结构，而像数组那样顺序存储的数据结构称为静态数据结构。

链表的概念

链表中，如果每块内存只存储数据元素的话，内存之间就无法形成线性结构。

为了使链表“串起来”，除了存储数据元素外，还需要存储直接后继节点的内存地址，通过“无形的线”将内存块“串”起来。

链表的节点.png
我们将存储后继节点内存地址的变量称为指针（即图中next）；存储着数据元素和指针的组合称为链表的节点；链表中第一个节点称为头节点，最后一个节点称为尾节点。

可能很多小伙伴听到指针就头疼，从C语言就开始折磨，好不容易到了Java，Python中没有了指针，可学个数据结构还要遭受指针的折磨。

其实指针的概念很简单，指针实际上是一个变量，存储的是某个对象的内存地址。

链表的特点

对于链表来说，插入和删除很简单，因为不需要使用连续的内存，所以也不需要在插入和删除后“整理”内存，得益于这种链式的存储结构，链表具有时间复杂度为的插入和删除操作。

插入和删除

链表的插入.png

如图，我们在节点B和D之间插入节点C，只需要2步操作即可：

• 节点C的指针指向节点D
• 节点B的指针指向节点C

删除操作也是类似的：

链表的删除.png

如果要删除节点C，需要3步操作：

• 存储节点D
• 删除节点C的指针
• 节点B指向节点D

可以看到，链表的插入和删除操作仅需要有限的操作步骤即可完成，在这个意义上时间复杂度为。

查询操作

对于链表来说，因为不具备顺序存储结构的特点，无法通过简答的计算查找到指定下标的数据元素，我们只能从链表的头节点出发，依次向后查询，直到查询到需要的数据元素位置。

这种情况下，链表查询操作的时间复杂度为。

链表的形式

到目前为止，我们对链表有了一定的认识，接下来我们来看看都有哪些常用链表的实现。

单向链表

单向链表是最简单的链表，也是我们在学习链表的概念中使用到的形式。

链表的节点.png
特点是，每个节点中只存储数据元素和指向直接后继节点的指针。下面会和大家实现一个简单的单向链表。

双向链表

双向链表是单向链表的升级版，除了存储数据元素和指向直接后继节点的指针外，还存储了指向直接前驱节点的指针。

双向链表.png
假设我们已知链表中的某个节点，我们希望在链表中删除这个节点。

如果是单向链表，我们需要遍历整个链表，查找到该节点的直接前驱节点后再进行删除，而在双向链表中，我们可以通过该节点获取到直接前驱节点。

实际上，我们经常使用的LinkedList.java就是双向链表，可谓是商业应用中，双向链表的最佳实现。

循环链表

除此之外，循环链表也是链表的一种实现，它的特点是尾节点的指针指向头节点，形成环状。

循环链表.png
在循环链表中，我们可以从任意节点开始向同一方向出发，访问到链表中的全部节点，这是单向链表和双向链表无法完成的。

循环链表最著名的应用就是约瑟夫问题。

单向链表的实现

今天的最后一部分，我们就一起来实现单向链表。

首先，我们定义单向链表的节点，节点主要包含两部分：数据元素和直接后继节点的指针。

public class Node<E> {  
    private E element;  
  
    private Node<E> next;  
  
    public Node(E data, Node<E> next) {  
        this.data = data;  
        this.next = next;  
    }
}

实际上，仅有Node也已经足够我们构建链表了，比如说：

Node<Integer> node = new Node<>(0, new Node<>(1, new Node<>(2, null)));

但是这样的链表看着有点闹心，并且非常“丑陋”，而且需要手动实现诸如插入删除等操作，因此我们要对它进行简单的包装：

public class SinglyLinkedList<E> {  

    // 头节点
    private Node<E> first;  

    // 尾节点
    private Node<E> last;
  
    private int size; 

    // 检查下标
    private void checkIndex(int index) {  
        if (index >= this.size || index < 0) {  
            throw new IndexOutOfBoundsException();  
        }  
    }

    private static class Node<E> {  
        private E element;  
  
        private Node<E> next;  
  
        public Node(E data, Node<E> next) {  
            this.data = data;  
            this.next = next;  
        }  
    }  
}

将Node封装到单向链表SinglyLinkedList中，同时添加了私有变量first，last和size为了方便后续的操作，同时添加了检查下标的私有方法。

新增操作非常简单，只需要处理好链表为空的情况，其余直接在链表尾部添加即可，代码实现如下：

public void add(E element) {  
    Node<E> newestNode = new Node<>(element, null);  
    if(this.first == null) {  
        this.first = this.last = newestNode;  
    } else {  
        this.last.next = newestNode;  
        this.last = newestNode;  
    }  
    this.size++;  
}

我们再来实现查找指定下标数据元素的方法，实现的思想也非常简单，只需要从链表的头部开始，不断的向后移动，直到到达指定下标为止，代码实现如下：

public E get(int index) {  
    checkIndex(index);  
    int i = 0;  
    Node<E> current = this.first;  
    while (i < index) {  
        current = current.next;  
        i++;  
    }  
    return current.element;
}

最后，我们实现删除指定数据元素的方法，实现也并不复杂，不过要处理比较多的情况：

• 头节点符合，并且链表中全部元素都符合，删除整个链表，并更新头尾节点
• 头节点不符合，链表中间包含或者尾节点符合，删除指定元素/更新尾节点

代码实现如下：

while (this.size != 0 && this.first.element.equals(element)) {  
    Node<E> oldFirst = this.first;  
    if(oldFirst == this.last) {  
        this.first = this.last = null;  
    } else {  
        this.first = oldFirst.next;  
        oldFirst.next = null;  
    }  
    this.size--;  
}  
if (this.size == 0) {  
    return;  
}  
Node<E> prev = this.first;  
while (prev.next != null) {  
    if (prev.next.element.equals(element)) {  
        Node<E> delNode = prev.next;  
        if(delNode == this.last) {  
            this.last = prev;  
        }  
        prev.next = delNode.next;  
        delNode.next = null;  
        this.size--;  
    } else {  
        prev = prev.next;  
    }  
}

这样我们就实现了一个单向链表，并为其添加了查找，新增和删除的操作。这样的链表我们拿来学习，“娱乐”是可以的，但是在商业应用中使用，就显得远远不足了。诸如，在指定位置添加，删除指定位置数据元素等，就留个小伙伴们自行实现了。

结语

今天，我们一起学习了第一个真正意义上的动态数据结构-链表，了解了它的3种实现，并一起动手实现了简单的单向链表。

相较于数组而言，链表对内存的要求相当低，这位链表带来优势，同时也使其失去了随机存取的能力。

练习

动手实现下自己的链表吧：

• 单向链表
• 双向链表
• 21.合并两个有序链表
• 剑指 Offer 24.反转链表
• 206.反转链表
• 剑指 Offer 22.链表中倒数第k个节点
• 剑指 Offer 06.从尾到头打印链表

本篇内容的代码仓库：

• Gitee代码仓库
• Github代码仓库

---

好了，今天就到这里了，Bye~~