图解数据结构js篇-链表结构（Linked-list）-一一网

之前我们通过图解数据结构js篇-数组结构介绍了数组结构。

本篇我们来介绍链表结构?

当我写完这篇文章的标题后，我就知道这篇文章不会短。原创码字画图都不易，还请点赞鼓励一下。?

什么是链表（Linked-list）

在计算机科学中，链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer) 引自维基百科

由维基百科给出的链表的定义可知，链表满足：

链表是一种 线性表，采用 链式存储 的方式有序的存储 有限个数量 的元素
链表中每一个节点中存储了到下一个节点的指针

这里引入的几个新的知识点， 线性表、顺序存储、链式存储。我们需要介绍一下

什么是线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表 （linear list） 是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。
引自百度百科

通过上面的定义，我们得出的结论就是：

线性表中的元素是有循序的（注意：这里的循序不是指排序，而是说它们的每一个元素的相对位置是固定的，就像在一根线上打多个结，那么它们每一个结的位置都是有线性顺序可言的）

数组和链表就是非常经典的线性表

顺序存储/链式存储

线性表有两种存储方式，分别是顺序存储和链式存储

线性表的顺序存储就是使用一块连续的内存空间进行存储。最常见的实现就是 [数组] (juejin.cn/post/700361…) 了。如果不了解的话可以看我的另一篇文章图解数据结构js篇-数组结构

链式存储就是采用链表的方式对线性表进行存储。其节点再内存中并不是连续的，而是随机的，通过一个指针指向后继节点（下一个节点）的地址来保证节点之间的循序。如果不了解的话，不用着急，这篇文章讲的就是它。

静态链表/动态链表

链表按存储方式来分也分为 静态链表 和 动态链表，其中静态链表使用 循序存储，动态链表使用 链式存储

一般说的链表都是指动态链表

前驱节点/后继节点

前驱节点：指前一个节点
后继节点：指后一个节点

动态单链表

动态链表是动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。

动态链表中的元素被称为节点（Node），其中每一个节点中包含一个数据域 data 和一个指针域 next

链表节点结构

data 存储的是当前节点的数据， next 存储的是当前节点的下一个节点的引用

n个节点链结成一个链表，即为线性表的链式存储结构。因为此链表的每个节点中包含一个指针域，所以叫动态单链表，结构如下图。

动态单链表

头节点/尾节点

头指针：头指针是指链表指向的第一个结点的指针，若链表有头结点，则是指向头结点的指针，头指针须具有标识作用，所以常用头指针冠以链表的名字，无论链表是否为空，头指针均不为空，头指针是链表的必要元素

头结点（head）：头结点时为了操作的同意和方便而设立的，放在第一元素的头结点之前，其数据域一般无真实意义

真实头结点：其第一个节点用于存储数据

真实头结点

虚拟头结点：其第一个节点不允许存储数据

虚拟头节点

尾指针（rear）：与头指针类似，不过是链表中的最后一个节点的指针

尾指针

代码实现

首先定义一下 Node 的结构

class Node{
    data; // 数据域
    next = null; // 指针域

    constructor(data) {
        this.data = data
    }
}

class LinkedLint{
    head = null;
    rear = null;
    size = 0;
    
    constructor() {
        // 创建虚拟头节点
        let node = new Node("head")
        this.head = node
        this.rear = node
    }
}
复制代码

遍历链表

查询链表的方式非常简单，我们只需要不断的通过 next指针 访问后继节点，直到 next 为 null 时结束。

我们先重写一下 LinkedLint 的 toString 方法


// 从头节点遍历输出到链表末尾
LinkedLint.prototype.toString = function(){
    let head = this.head
    let str = `${head.data}`

    head = head.next
    while(head){// 判断下一个节点是否存在
        str += ` --> ${head.data}`
        head = head.next
    }
    str += ` --> NULL`

    return str
}
复制代码

然后测试一下,没有问题

let linkedLint = new LinkedLint();

// 插入数据(这里暂时用这种方式插入，后面写了插入的方法后再换回去)
t = linkedLint.head
t.next = new Node('a1')
t = t.next
t.next = new Node('a2')
t = t.next
t.next = new Node('a3')
t = t.next
t.next = new Node('a4')

console.log(linkedLint.toString()) // head --> a1 --> a2 --> a3 --> a4 --> NULL
复制代码

有没有觉得动态单链表有点像 JavaScript 的迭代器呢？不断的调用next来获取下一个结构。

查询链表

查询链表中第i个元素，我们最常用的方法是从头节点开始遍历，当遍历到第i个元素即返回，时间复杂度为 O(n)

代码实现

/**
 * 获取索引为 index 的元素，下标从0开始
 * @param index 下标
 */
LinkedLint.prototype.get = function (index){
    // 当index超出链表长度范围，返回null
    if(index >= this.size) return null
    // 获取的下标为0的节点，i为当前head节点的下标
    let head = this.head.next, i = 0

    while (i < index){
        head = head.next
        i++
    }

    return head
}

console.log(linkedLint.get(0)) // Node { data: 'a5', next: ... }
console.log(linkedLint.get(6)) // Node { data: 'a7', next: null }
console.log(linkedLint.get(7)) // null
复制代码

插入-头插法

所谓头插法就是插入节点的位置是在头节点后进行插入（如果是真实头结点，那么就是在头节点之前插入），我们这里以虚拟头节点为例

头插法生成的链表中结点的顺序与输入插入的顺序相反

头插的步骤分为3步

特殊情况：如果链表为空链表，需要将尾指针指向被插入的节点
将插入的节点 next 指向头节点的 next
将头节点的 next 指向插入的节点

其时间复杂度为 n(1)

空链表头插入

空链表头插法

非空链表头插入

将插入的节点 next 指向头节点的 next

将头节点的next指向插入的节点

代码实现

为 LinkedLint 类添加 addHead 方法

/**
 * 头插法插入节点
 * @param node 被插入的节点
 */
LinkedLint.prototype.addHead = function(node){
    // 如果当前只有一个节点，那么需要将尾指针移动到新节点上面
    if( this.size === 0) this.rear = node
    // 将插入的节点 next 指向头节点的 next
    node.next = this.head.next
    // 将头节点的next指向插入的节点
    this.head.next = node
    // 维护 size字段
    this.size++
        
    return true
}


let linkedLint = new LinkedLint();
console.log(linkedLint.toString()) // head --> NULL

linkedLint.addHead(new Node("a4"))
linkedLint.addHead(new Node("a3"))
linkedLint.addHead(new Node("a2"))
linkedLint.addHead(new Node("a1"))
console.log(linkedLint.toString()) // head --> a1 --> a2 --> a3 --> a4 --> NULL

linkedLint.addHead(new Node("a5"))
console.log(linkedLint.toString()) // head --> a5 --> a1 --> a2 --> a3 --> a4 --> NULL
复制代码

插入-尾插法

尾插法插法就是将要插入的节点插入到当前单链表的表尾后，尾插法生成的链表中结点的顺序与输入插入的顺序相同

其思路很简单：

将尾指针的 next 指向被插入的节点
让尾指针指向被插入的节点

虽然很简单，但是依然要上图

尾插法过程

代码实现

/**
 * 尾插法插入节点
 * @param node 被插入的节点
 */
LinkedLint.prototype.addRear = function (node){
    // 将尾指针的 next 指向被插入的节点
    this.rear.next = node
    // 让尾指针指向被插入的节点
    this.rear = node
    // 增加size
    this.size++
    
    return true
}

console.log(linkedLint.toString()) // head --> a5 --> a1 --> a2 --> a3 --> a4 --> NULL
linkedLint.addRear(new Node("a6"))
linkedLint.addRear(new Node("a7"))
console.log(linkedLint.toString()) // head --> a5 --> a1 --> a2 --> a3 --> a4 --> a6 --> a7 --> NULL
复制代码

插入-中间插入

头插法和尾插法一般用于初始化链表，相比于实际应用的中，再指定位置插入值的方式更加常见。

思路：

新插入的节点的 next 指向 index 位置的节点
将 index 位置前驱节点的 next 指向新插入的节点
特殊情况:如果 index 为 0 或者 size，分别采取 头插法 或者 尾插法 即可

因为要通过 get 获取插入位置的前驱节点，所以时间复杂度为 O(n)

中间插入节点

代码依然很简单

/**
 * 将节点插入到指定位置
 * @param node 被插入的节点
 * @param index 被插入的索引位置
 * @return {Boolean} 是否插入成功
 */
LinkedLint.prototype.add = function (node, index){
    if(index < 0 || index > this.size) return false
    if(index === 0) return this.addHead(node)
    if(index === this.size) return this.addRear(node)

    // 获取index位置的前驱节点
    let previousNode = this.get(index-1)
    // 被插入的节点指向前驱节点的next（之前这个位置的节点）
    node.next = previousNode.next
    // 前驱节点指向新插入的节点
    previousNode.next = node
    this.size++

    return true
}

console.log(linkedLint.toString()) // head --> a5 --> a1 --> a2 --> a3 --> a4 --> a6 --> a7 --> NULL

linkedLint.add(new Node('add1'), 1)
linkedLint.add(new Node('add2'), 5)

console.log(linkedLint.toString()); // head --> a5 --> add1 --> a1 --> a2 --> a3 --> add2 --> a4 --> a6 --> a7 --> NULL
复制代码

删除

删除节点是最简单的操作了

将被删除位置的前驱节点的 next 指向被删除位置的后继节点即可。

/**
 * 移除链表中某个元素
 * @param index
 * @return {boolean}
 */
LinkedLint.prototype.delete = function (index){
    if(index < 0 || index > this.size) return false

    let previousNode = this.get(index-1)
    previousNode.next = previousNode.next.next
    
    return true
}
复制代码

呼~~~ 码了这么多字和图居然才介绍一种链表。码字不易，还请点赞鼓励。

静态单链表

静态链表并不常用，但是我还是打算拿出一个来说一说。因为考试会考（划重点）。

静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。

当我们使用数组中固定位置的元素作为头节点时，我们可以将头节点当作第一个数据节点使用。如果第一个数据节点的位置是变化的，那么我们就需要使用头节点来指向第一个数据节点的位置，所以静态单链表中我们使用的是真实头结点（头节点中存储数据）

我们先来看看静态链表再内存中的存储结构。

静态链表

静态链表使用两个大小一致的数组配合，其中一个（data）用于存储数据元素，一个（cur）用于存储游标。

备用链表

上图中显示的静态链表还不够完整，静态链表中，除了数据本身通过游标组成的链表外，还需要有一条连接各个空闲位置的链表，称为备用链表。

备用链表的作用是回收数组中未使用或之前使用过（目前未使用）的存储空间，留待后期使用。也就是说，静态链表使用数组申请的物理空间中，存有两个链表，一条连接数据，另一条连接数组中未使用的空间。

通过上图中发现，链表节点在数组中并不一定是紧凑存储的，中间可能会有空闲的数组项，为了合理的利用数组的空间，我们每次插入节点时就要在数组中寻找一个空闲的节点进行插入。如果使用遍历数组的方法来寻找空闲空间，那么时间复杂度将为 O(n)。

所以我们使用另一个链表来存储数组中所有空闲的空间，我们称这个链表为 备用链表 ，当我们需要插入一个节点时，只需要摘抄备用链表的头节点的下一个节点即可，时间复杂度降为 O(1)。

通常，备用链表的表头位于数组下标为 0（data[0]）的位置，而数据链表的表头位于数组下标为 1（data[1]）的位置。

备用链表和数据链表

静态链表中设置备用链表的好处是，可以清楚地知道数组中是否有空闲位置，以便数据链表添加新数据时使用。比如，若静态链表中数组下标为 0 的位置上存有数据，则证明数组已满。

但是我们一般不会在 data[0] 和 data[1] 上插入数据，以为这会让我们丢失备用链表和数据链表的头节点

代码实现
先把上面说到的功能先做好了吧，后面一点点添加

我们先定义好 LinkedList 类中的数据，然后对其所有元素挂载到备用链表上

你也可以像上面的动态单链表一样来维护一个 size 字段记录数据链表的长度，但是我觉得它太麻烦了且并不容易维护，后面的内容中我并不打算继续维护它。

class LinkedList{
    data;
    cur;
    constructor(length){
        // 备用链表和数据链表的头结点会各占一个空间
        length += 2
        // 初始化，构建备用链表
        this.data = Array(length)
        this.cur = Array(length)

        // 构建备用链表头节点
        this.cur[0] = 2
        // 数据链表头节点
        this.cur[1] = -1
        this.data[1] = "head"
        // 2 到 length-2 之间的空间全部挂载到备用链表上
        for(let i=2; i<length-1; ){
            this.cur[i] = ++i
        }
        // 备用链表尾节点
        this.cur[length-1] = -1
    }
}
复制代码

遍历静态单链表

然后我们对其添加一个遍历链表和打印链表内容的方法

遍历的思路非常简单，我们只需要从开始遍历的节点不断获取其游标（下一个节点的位置），直到其游标为-1结束

数据链表的遍历也是一样的（画得有点乱，将就着看一下吧）

// 打印备用链表和数据链表
toString(){
    return `备用链表：${!this.data[0] && this.through(0)}\n数据链表：${this.data[1] && this.through(1)}`
}

// 从下标为index的位置遍历链表
through(index){
    let str = `${this.data[index]}:${index}` // 当前节点

    let next = this.cur[index] //获取到当前节点的下一个节点的下标
    // 遍历
    while(next !== -1){
        str += ` ---> ${this.data[next]}:${next}`
        next = this.cur[next]
    }

    return str
}
复制代码

插入-头插法

上面已经介绍过上面是头插法了，但是相对于动态单链表来说，静态单链表的头插法如何实现呢?

思路：

取备用链表中第一个节点存储数据（这是一个链表的删除节点操作）
将新节点的游标改为数据链表头节点的游标(即新节点指向原来的第一个数据节点)
将头节点的游标改为新节点的下标（即将新节点作为第一个数据节点）

其实与动态链表中的思路和步骤是一致的

摘除备用链表第一个节点

摘除备用链表节点

这样我们就得到了一个空闲的节点，下标为4，然后我们对其数据域复制，并将其游标指向和头节点相同的下标

最后我们将头节点的游标指向我们插入的这个节点的下标

代码:

// 从备用链表中摘除节点，返回数组中节点对应下标
getNode(){
    if(this.cur[0] === -1) return -1

    let next = this.cur[0]// 被摘除的节点下标
    this.cur[0] = this.cur[next]// 头节点指向下一个节点

    return next 
}

// 头插法
addHead(data){
    let index = this.getNode()

    if(index !== -1){
        this.data[index] = data
        // 与动态链表头插法中 node.next = this.head.next 对应
        this.cur[index] = this.cur[1]
        // 与 this.head.next = node 对应
        this.cur[1] = index

        return true
    }

    return false
}
复制代码

测试一波，没啥问题

let linkedList = new LinkedList(5);

console.log(linkedList.toString());
/*
* 备用链表：undefined:0 ---> undefined:2 ---> undefined:3 ---> undefined:4 ---> undefined:5 ---> undefined:6
* 数据链表：head:1
*/

console.log(linkedList.addHead("哈哈哈")); // true

console.log(linkedList.toString());
/*
* 备用链表：undefined:0 ---> undefined:3 ---> undefined:4 ---> undefined:5 ---> undefined:6
* 数据链表：head:1 ---> 哈哈哈:2
*/
复制代码

其他方法我就不讲解了，其实过程都是和动态链表一样的。例如下标为 index 的节点。通过 cur[index] 就能获取到其 next 的下标，一个 data[index] 就能获取到其 data 域的数据。

无意中了解到静态链表好像是一个考验会考的题目，题目一般会给你一张类似上面的内存图，告诉你头节点的内存地址，让你计算链表中第 i 个元素的内存地址。?

双链表

双链表顾名思义，就是链表由单向的链变成了双向链。使用这种数据结构，我们可以不再拘束于单链表的单向创建于遍历等操作，大大减少了在使用中存在的问题。

这里指的是动态双链表，双链表与单链表一样，只是多了一个存储上一个节点的指针，所以双链表的节点结构图有两个指针域

在单链表中，我们有一个数据域，还有一个指针域，数据域用来存储相关数据，而指针域则负责链表之间的“联系”。而在双向链表中，我们需要有两个指针域，一个负责向后连接(next)，一个负责向前连接(front)。

双向链表节点结构图

其中 front 指向前驱节点， next 指向后继节点。最终构成一个双向的链表。

双链表

插入操作

伪代码

e3.next = e2
e3.front = e1

e1.next = e3
e2.front = e3
复制代码

移除操作

移除操作与插入操作过程相反

伪代码

e1.next = e3.next
e2.front = e3.front
复制代码

单循环链表

单循环链表 将 单链表 的 头结点 和 尾结点 链接起来也能构成 循环链表 ，其称为 单循环链表

双循环链表

双向循环链表 将 双向链表 的 头结点 和 尾结点 链接起来也能构成 循环链表，其称为 双向循环链表。

循序表和链表的优缺点

顺序表

优点：

空间利用率高，数据是连续存放，命中率比较高
存取速度高效，通过下标来直接访问。

缺点：

插入和删除比较慢，在插入或者删除一个元素的时候，需要遍历整个顺序表移动前后的数据
需要预先分配足够大的空间，估计的过大，会导致顺序表后的大量空间被闲置；但是估计的过小，又会造成溢出。

时间复杂度 : 查找操作为O(1) ,插入和删除操作为O(n)。

链表

优点：

插入和删除速度快，保留原有的物理顺序，在插入或者删除一个元素的时候，只需要改变指针指向即可。
没有空间限制,存储元素无上限,只与内存空间大小有关.
动态分配内存空间，不用事先开辟内存
使内存的利用率变高

缺点：

占用额外的空间以存储指针，比较浪费空间，不连续存储，开辟空间碎片比较多
查找速度比较慢，因为在查找时，需要循环遍历链表。

时间复杂度 : 查找操作为O(n) ,插入和删除操作为O(1)。

结语

可能是因为写的时间太长了（整整写了一天），后面画的图比较潦草，但是码字不易，给孩子 **点个赞吧~~~**?

文章版权归作者所有，未经允许请勿转载。

THE END

前端

饿了么天猫超市零元购

用canvas制作一个刻有你女神的名字中秋月饼吧

Nginx location 和 proxy_pass

phpBB 跨站脚本攻击漏洞

【月更第20篇】签名验证反爬，反反爬第二篇博客，Python爬虫120例

Kotlin中?和!!的区别

图解数据结构js篇-链表结构（Linked-list）

什么是链表（Linked-list）

动态单链表

遍历链表

查询链表

插入-头插法

插入-尾插法

插入-中间插入

删除

静态单链表

备用链表

遍历静态单链表

插入-头插法

双链表

单循环链表

双循环链表

循序表和链表的优缺点

结语