一文带你搞懂前端必备数据结构 – 链表

嘟嘟嘟~~发车啦，快来和博主一起飙车啦！😊文末附上力扣相关题目

不止图文解释，注释也很清晰噢！

1. 什么是链表

链表是一组由节点组成的集合，每个节点都有一个指针指向它的下一个节点。举个栗子来说，就像上图的小火车一样，每一节车厢之间都通过绳索相连接，每节车厢都是一个节点，车厢间的连接就是指针

那了解了什么是链表之后，很多小伙伴就会想，这和数组有什么区别呢？数组操作不是更方便吗？

数组的大小是固定的，从数组的起点或中间插入或移除项的操作成本很高，因为需要移动元素（尽管我们已经学过很多的API，但背后的情况同样是这样）

1.1 链表的优点

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。这样添加、移除操作的时间复杂度就为O(1)。下图就是一个单向链表插入节点的示意图，我们只需要改变前一个节点的next指针并且修改新节点的next指针是链表连接起来即可完成

1.2 链表的缺点

相对于数组而言，数组在访问一个元素的时候，可以直接通过索引来直接访问，而对于链表而言访问其中的一个元素，需要从起点开始迭代整个链表直到找到所需的元素。因此访问的时间复杂度落在O(1)-O(n)之间

1.3 单向链表与数组各个操作时间复杂度对比

链表操作	最大时间复杂度	数组操作	最大时间复杂度
search（访问）	O(n)	search（访问）	O(1)
insert（插入）	O(1)	insert（插入）	O(n)
remove（删除）	O(1)	remove（删除）	O(n)
append （添加）	O(1)	append （添加）	O(1)

1.4 链表的分类

有三种：单向链表、双向链表、循环链表

1.4.1 单向链表

1.4.2 双向链表

1.4.3 循环链表

2. 使用JS实现链表

了解了什么是链表，接下来我们使用js来实现链表的相关操作

2.1 单向链表

2.1.1 创建一个单向链表

以下是一个LinkedList的基本骨架

class LinkedList {
    constructor() {
        // 链表的长度size
        this.size = 0;
        this.head = null;
    }
    //添加链表项
    append(element) { }
    //插入链表项
    appendAt(position, element) { }
    // 删除指定列表项
    remove(element) { }
    //删除指定位置链表项
    removeAt(position) { }
    // 查找指定元素索引
    indexOf(element) { }
    // 翻转链表
    reserve() { }
    // 获取节点
    getNode(index) {}
}
//测试
let l1 = new LinkedList();

链表数据结构还需要一个Node辅助类。Node类表示要加入列表的项。它包含一个element属性，即要添加到列表的值，以及一个next属性，即指向列表中下一个节点
项的指针。

// node类
class Node {
    constructor(element) {
        this.element = element;
        // 添加一个指针
        this.next = null
    }
}

另一个重要的点是，我们还需要存储第一个节点的引用。为此，可以把这个引用存储在一个称为head的变量当中，接下来我们就要来实现LinkedList类中为填写的方法。

• append(element) ：向链表尾部添加一个新的项
• appendAt(position, element) ： 向链表的特定位置插入一个新的项
• remove(element)：从列表中移除一项
• removeAt(position)：从列表的特定位置移除一项
• getNode(index)：获取某个位置的节点
• reserve()：反转链表

2.1.2 获取链表中的节点

先写这个是因为后面的很多方法中都有使用到这个函数！其实也可以不用单独封装成一个函数，存粹个人习惯

传入一个需要查找的节点位置，通过for循环，不断地让current指向下一位，直至到达index的位置，跳出for循环，返回当前current节点:orange:

getNode(index) {
    // 边界判断 传入的参数是否在链表的长度范围之内
    if (index < 0 || index >= this.size) {
        throw new Error('out')
    }
    let current = this.head;
    // 不断的让current移到下一位，直到到达index - 1位置
    // 也就是循环遍历的过程
    for (let i = 0; i < index; i++) {
        current = current.next;
    }
    // 最后返回节点
    return current
}

2.1.3 向链表尾部追加元素

有两种场景：

1. 列表为空，添加的是第一个元素
2. 列表不为空，向其追加元素

下面是我们实现的append方法，通过上一部分的getNode方法，获取到链表的最后一个节点，让最后一个节点的next指针指向新创建的节点node，使得链表串联起来，最后让链表长度size自加，即可实现 :shamrock:

append(element) {
    // 通过实例化添加属性
    let node = new Node(element);
    // 添加操作
    if (this.head === null) {
        this.head = node;
    } else {
        let current = this.getNode(this.size - 1);
        // 最后一个节点的next指向新创建的节点
        current.next = node
    }
    //添加链表项后，size自增
    this.size++;
}

注意：这里的节点创建是通过new操作符实现的，构造出来的node是一个对象，带有了自身的值element和next指针，新创建的节点next指针默认指向null

2.1.4 向链表的任意位置插入一个元素

因为是通过位置来插入元素，所以首先要判断该位置是否越界。如果越界了，可以直接抛出错误。同样的有2种场景：

第一种场景：需要在列表的起点添加一个元素，也就是第一个位置，让新创建的节点next指针指向头节点，也就是this.head，再将新创建的节点设为头节点:tada:

第二种场景：非起点插入。首先需要找到插入位置的前一个节点pre，让新创建的节点指向pre的下一个节点pre.next，再让pre节点的next指针指向新创建的节点:apple:

//插入链表项
appendAt(position, element) {
    // 边界判断
    if (position < 0 || position > this.size) {
        throw new Error('position out range')
    }
    // 实例化创建节点
    let node = new Node(element);
    //起点插入
    if (position === 0) {
        node.next = this.head;
        this.head = node;
    } else {
        // 找到需要插入位置的前一个节点
        let pre = this.getNode(position - 1);
        // 让新创建的节点指向当前前一个节点的下一个节点
        node.next = pre.next;
        // 让前一个节点指向新创建的节点
        pre.next = node;
    }
}

2.1.5 从链表中移除元素（根据特定位置移除）

移除元素也有两种场景：第一种是移除第一个元素，第二种是移除第一个以外的任一元素。同样的我们需要先进行边界判断，在链表长度外的抛出错误即可。

第一种场景非常简单，由于移除的是第一个节点，只需要让head指向列表的第二个元素

现在，假设我们要移除列表的最后一项或者中间某一项。首先我们需要获取到被删除节点的前一个节点，让该节点的next指针指向被删除节点的下一个节点。这样，被遗弃的元素就会被丢弃在计算机内存中，等着被垃圾回收器清除。

//删除指定位置链表项
removeAt(position) {
    // 边界判断，超出链表长度，抛出错误
    if (position < 0 || position >= this.size) {
        throw new Error('position out range')
    }
    let current = this.head
    if (position === 0) {
        // 如果删除的是第一个节点，则让head指向下一位即可
        this.head = current.next;
    } else {
        // 获取删除位置的前一个节点
        let pre = this.getNode(position - 1); 
        // current为被删除节点
        current = pre.next;
        // 让前一个节点指向删除节点的下一个节点
        pre.next = current.next;
    }
    // 长度自减
    this.size--;
}

2.1.6 查找元素在链表的位置

我们需要一个变量来帮助我们循环访问列表，也就是代码中的current，它的初始值是head。通过for循环来遍历链表，判断当前位置的值是否等于查找值，如果是，就返回它的位置；如果不是，就继续向下访问。如果for循环结束还未弹出，说明到达了链表的尾部，也就是说链表中不存在该元素，返回-1。

// 查找指定元素索引
indexOf(element) {
    // 当前链表头节点
    let current = this.head; 
    // 遍历整个链表
    for (let i = 0; i < this.size; i++) {
        if (current.element === element) {
            return i
        }
        // 依次向下移动
        current = current.next; 
    }
    return -1;
}

2.1.7 根据元素值移除元素

现在有了indexOf方法，我们可以传入元素的值，找到它的位置，然后调用removeAt方法并传入找到的位置，就能实现移除元素

remove(element) {
    // 获取需要删除元素在链表的位置
    let index = this.indexOf(element)
    if(index!= -1 ) {
        // 通过下面的removeAt方法删除指定位置节点
        this.removeAt(index)
    }else {
        // 删除不存在的元素，抛出错误
        throw new Error('element no found')
    }
}

2.1.8 反转链表

反转链表在leetcode中经常会遇到，在各个面试题中也都会发现它的身影。所以，这里就顺带写以下

首先定义两个指针：prev 和 current,current 在前 prev 在后。每次让 current的 next指针指向prev，实现一次局部反转，局部反转完成之后，prev 和current同时往前移动一个位置，循环这个过程，直到current到达链表尾部，实现动画如下

reserve() {
    let prev = null;
    let current = this.head;
    while (current) {
        // 保存当前的下一位
        let next = current.next;
        // 让当前节点指向前面的节点prev
        current.next = prev;
        // 交换完之后，让prev移到下一位也就是current
        prev = current;
        current = next;
    }
    //返回翻转的链表
    this.head = prev
}

2.2 双向链表

双向链表和单向链表的区别在于，单向链表一个节点只有链向下一个节点的指针，而在双向链表中，有两个指针，一个指向前一个元素，一个指向下一个元素，示意图如下：

2.2.1 创建一个双向链表

相较于单向链表多了一个指向前一个元素的指针，所以在代码中要进行一些修改

//一个链表节点
class Node {
    constructor(element) {
        this.element = element
        this.next = null
        this.prev = null//新增
    }
}
//双向链表
class doubleLinkedList {
    constructor () {
        this.size = 0
        this.head = null
        this.tail = null//新增
    }
    // 这里是接下来写的方法
}

双向链表的优点：可以访问一个特定节点的下一个或==前一个==元素。在单向链表中，如果迭代链表时错过了要查找的元素，就需要回到链表的起点重新开始迭代

注意：在doubleLinedList类中有保存对列表最后一项的引用的tail属性。

2.2.2 获取链表中的节点

根据位置获取链表的方法和单向链表中的是相同，忘记了记得跳回去看看噢！

// 获取某个位置的节点，和单向链表相同
getNode(index) {
    if (index < 0 || index >= this.size) {
        throw new Error('out')
    }
    let current = this.head
    for(let i = 0;i < index;i++) {
        current = current.next
    }
    return current
}

2.2.3 向链表尾部追加节点

相信看到这里的你，应该知道要先干嘛了吧！分两种情况

第一种情况：链表为空

第二种情况：链表不为空

对于第一种情况而言，我们只需要让head和tail指向新创建的节点即可

对于第二种情况，相对于单向链表而言，有一点不一样的地方，我们需要设置前驱指针。

首先我们需要让最后一个节点的next指针指向新节点，再让新节点的prev指针指向前一个节点（也就是连接前的最后一个节点），最后记得将tail移向最后一个节点，同时size也要自增！下面是示意图，清晰明了

append(element) {
    // 创建节点
    let node = new Node(element)
    // 保存当前指向最后一个元素的指针
    let tail = this.tail
    // 如果链表为空则新节点将作为第一个
    if(this.head === null) {
        // head和tail都为node
        this.head = node
        this.tail = node
    }else {
        // 常规尾插，让最后一个元素的next指针指向node  
        tail.next = node
        // 再让node的前驱指针指向最后一个节点tail
        node.prev = tail
        // 最后更新tail指向最后一个元素node
        this.tail = node
    }
    this.size++
}

2.2.4 向链表中插入节点

向双向链表中插入一个新节点和单向链表非常相似。区别在于，单向链表只需要控制一个next指针，而双向链表则要同时控制next和prev两个指针

首先来分析第一种场景：在链表的第一个位置插入一个新节点。如果链表为空，只需要把head和tail都指向这个新节点。如果不为空，current变量将保存的是链表中第一个元素的引用，那么只需让新节点的next指针指向current，让current节点的prev指针指向新节点，最后让head指向第一个节点即可，演示过程如下：

接下来是第二种场景：在尾部插入，这个和上一个方法有点类似，可以查看上一小节，这里就不重复赘述了

最后一个场景也是相对复杂一点点的：在链表的中间部分插入

通过前面写的getNode方法，获取到需要插入位置的前一个节点preNode以及下一个节点current，我们将在current和preNode元素之间插入新元素。首先，node节点的next指针指向current，再让node的prev指针指向preNode节点，再处理剩下两个指针分别指向node即可，演示图如下：

// 插入节点
insert(position, element) {
    // 边界判断，输入的position需要在范围之内
    if (position < 0 || position > this.size) {
        throw new Error('position out range')
    }
    // 创建节点
    let node = new Node(element)
    // 保存第一个节点，为一个变量
    let current = this.head
    // 第一种情况，在最头部插入
    if (position === 0) {
        // 链表为空的情况
        if (!this.head) {
            this.head = node
            this.tail = node
        } else {
            // 链表不为空
            // 让node的next指针指向第一个节点
            node.next = current
            // 第一个节点的前驱指针指向node
            current.prev = node
            // head指向新的第一个节点
            this.head = node
        }
        this.size++
    } else if (position === this.size) {
        // 在最后插入
        // current变量保存最后一个节点
        current = this.tail
        // 最后一个节点的next指针指向新节点
        current.next = node
        // 新节点的前驱指针指向前一个节点
        node.prev = current
        // tail移至node
        this.tail = node
        this.size++
    } else {
        // 在中间插入
        // 获取插入位置的前一个节点
        let preNode = this.getNode(position - 1)
        // current变量保存preNode节点的下一个节点
        current = preNode.next
        // 1. 让node节点的next指针指向后一个节点current
        node.next = current
        // 2. 让node节点的prev指针指向前一个节点preNode
        node.prev = preNode
        // 3. 让preNode节点的next指针指向新节点
        preNode.next = node
        // 4. 让current节点的prev指针指向新节点
        current.prev = node
        this.size++
    }
}

注意：在我们封装的getNode方法中，无论如何都是从头开始遍历的，实际上我们可以优化这个过程，当我们要找的position大于size的一半时，我们可以从尾部开始遍历，这样可以提高性能。

2.2.5 从链表中的特定位置删除元素

双向链表的操作其实都和单向链表相似，只是多了一个前驱指针，要多操作一个指针而已，对于这个删除特定位置元素的方法，我们需要知道最重要的一点就是将被删除的节点从链表中移出，再将链表连接完好即可

同样的我们需要分成3种情况

第一种情况：删除第一个节点

用current变量保存链表中第一个节点的引用，也就是我们想要移除的第一个节点。首先要改变的是 head 的引用，将其从current改为current.next。但我们还需要更新current.next指向上一个元素的指针，因此需要判断链表的长度是否为1，如果为1说明删除第一个节点之后链表就为空了，这时候就需要将tail设为null，如果不为1，则把head.prev的引用改为null即可。演示图如下：

第二种情况：删除最后一个节点

因为有了最后一个节点的引用tail，我们不需要通过getNode来获取最后一个节点，这样我们也就可以把tail的引用赋给current变量。接下来，需要把tail的引用更新为列表中倒数第二个元素，同时将next指针指向null，这个过程可以展示为下图：

第三种情况：删除中间的节点

首先我们需要通过getNode方法找到要删除的节点，用current变量保存，再用preNode表示要删除节点的前一个节点，。那么要移除它，我们可以通过更新prev.next和current.next.prev的引用，在链表中跳过它，因此，将prev的next指针指向current.next，而current.next的prev指针指向prev，如下图演示：

removeAt(position) {
    // 边界判断，输入的position需要在范围之内
    if (position < 0 || position > this.size) {
        throw new Error('position out range')
    }
    let current = this.head
    // 如果删除的是第一个节点
    if (position === 0) {
        // 让head指向下一位
        this.head = current.next
        // 如果链表的长度为1，删除后末尾应当为null
        if(this.size === 1) {
            this.tail = null
        }else {
            // 不为1 删除节点后第一个节点（current.next)指向null
            this.head.prev = null
        }
        this.size--
    }else if (position === this.size -1) {
        // 删除最后一个节点
        // 先让current保存我们要删除的节点
        current = this.tail
        // 让tail移向删除节点的前一位
        this.tail = current.prev
        // 再让tail的next指针指向null，这样最后一个节点就被丢弃了
        this.tail.next = null
        this.size--
    }else {
        // 被删除的节点
        let current = this.getNode(position)
        // 删除节点的前一个节点
        let preNode = current.prev
        // 删除节点的前一个节点next指向它的后一个节点
        preNode.next = current.next
        // 后一个节点的prev指向preNode
        current.next.prev = preNode
        this.size--
    }
}

2.2.6 查找元素在链表中的位置

和单向链表的处理方式相同，没有做什么改动:hamburger:

indexOf(element) {
    // 当前链表头节点
    let current = this.head; 
    // 遍历整个链表
    for (let i = 0; i < this.size; i++) {
        if (current.element === element) {
            return i
        }
        // 依次向下移动
        current = current.next; 
    }
    return -1;
}

2.2.7 根据元素值移除节点

在前面根据位置删除链表节点的基础上，这部分的代码和单向链表相同，但也不完全相同噢，毕竟removeAt方法是一个新的方法噢！

// 根据元素值删除元素
remove(element) {
    let index = this.indexOf(element)
    if (index != -1) {
        // 通过下面的removeAt方法删除指定位置节点
        this.removeAt(index)
    } else {
        // 删除不存在的元素，抛出错误
        throw new Error('element no found')
    }
}

2.2.8 打印双向链表

通过遍历整个链表，将每个节点的值拼接起来，这样看起来会清晰很多

输出示例：NULL<->1<->2<->3<->NULL

print() {
    let str = 'NULL<->';
    let current = this.head
    while (current !== null) {
        str += current.element + '<->';
        current = current.next;
    }
    return str += 'NULL';
}

2.3 单向循环链表

循环链表和单向链表相似，节点类型都是一样，唯一的区别是，在创建循环链表的时候，需要让其最后一个节点的 next 指针指向第一个节点

// 假定lastItem为最后一个节点
lastItem.next = this.head

2.3.1 创建一个单向循环链表

大体的结构和单向链表一致

class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}
class CircleLinkedList {
    constructor() {
        this.size = 0
        this.head = null
    }
    // 在末尾添加节点
    append(element) {}
    // 在任意位置插入节点
    insert(position,element) {}
    // 根据位置删除节点
    removeAt(position){}
    // 查找元素对应索引，与单向链表相同
    indexOf(element) {}
    // 根据元素值删除节点，与单向链表相同
    remove(element) {}
    // 获取节点，与单向链表相同
    getNode(index) {}
}

2.3.2 在链表尾部追加节点

第一种情况：链表为空，直接让head指向新节点node即可

第二种情况：链表不为空，通过getNode方法获取到链表的最后一个节点，让该节点的next指针指向新节点node

注意：在执行完if判断后都需要将最后一个节点的next指针指向第一个节点head

append(element) {
    // 创建节点
    let node = new Node(element)
    // 链表为空情况
    if (this.head === null) {
        this.head = node
    } else {
        // 获取最后一个节点
        let current = this.getNode(this.size - 1)
        current.next = node
    }
    // 不管哪种情况，都要保持首尾相连
    node.next = this.head
    this.size++
}

2.3.3 在链表中插入节点

同样的有两种场景

• 当插入的位置是第一个时，不同于单向链表的操作是，需要额外的将链表的最后一个节点的next指针指向新节点node
• 在其他地方插入时，可以通过三元运算符来判断，新节点的next指向是不是null如果是null说明新节点插在最后一个节点，需要将该节点的next指针指向第一个节点，否则就正常插入即可

insert(position, element) {
    // 边界判断
    if (position < 0 || position > this.size) {
        throw new Error('position out range')
    }
    // 实例化创建节点
    let node = new Node(element);
    if (position === 0) {
        // node指向先前的第一个节点
        node.next = this.head;
        // 头节点改变为新节点node
        this.head = node;
        let current = this.getNode(this.size - 1)
        current.next = this.head
        this.size++
    } else {
        // 找到需要插入位置的前一个节点
        let prev = this.getNode(position - 1);
        // 如果prev.next 为null就指向head否则就指向下一个
        node.next = prev.next == null ? this.head : prev.next
        // 让前一个节点指向新创建的节点
        prev.next = node;
        this.size++
    }
}

2.3.4 在链表中删除特定位置的节点

区别于单向链表，删除第一个节点时，需要改变最后一个节点的next指向，指向新的第一个节点，删除其他节点时，需要判断以下被删除节点的前一个节点的next指向是否为null从而进行下一步的操作

// 根据位置删除节点
removeAt(position) {
    // 边界判断，超出链表长度，抛出错误
    if (position < 0 || position >= this.size) {
        throw new Error('position out range')
    }
    let current = this.head
    if (position === 0) {
        // 如果删除的是第一个节点，则让head指向下一位即可
        let last = this.getNode(this.size - 1); 
        this.head = current.next;
        last.next = this.head
    } else {
        // 获取删除位置的前一个节点
        let pre = this.getNode(position - 1); 
        // current为被删除节点
        current = pre.next;
        // 让前一个节点指向删除节点的下一个节点
        pre.next = current.next == null ? this.head : current.next;
    }
    // 长度自减
    this.size--;
}

2.4 双向循环链表

双向循环链表区别于单向循环链表，双向链表有多一个从第一个节点指向最后一个节点的prev指针

双向循环链表与前面的差别都不是很大，本文就不展开写了，相信看了前面的详解，一定能够自己完成的

3. 相关题目

leetcode上关于链表的几道题目，附上ac代码

3.1 反转链表（链接直达噢！）

var reverseList = function(head) {
    let prev = null;
    let current = head;
    while (current) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev
};

3.2 合并K个升序链表

var mergeKLists = function (lists) {
    if (!lists || !lists.length) return null;
    let end = lists[0]
    let i = 1;
    while (i != lists.length) {
        end = mergeTwoLists(lists[i++], end)
    }
    return end
};

function mergeTwoLists(l1, l2) {
    // 如果其中一个为空，直接返回另一个链表
    if (!l1) return l2
    if (!l2) return l1
    // 依次比较链表的值
    if (l1.val > l2.val) {
        // 如果l2的值大，则从l2开始，l2的next通过递归再次判断是谁 
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    } else {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    }
};

3.3 删除链表的倒数第 N 个结点

var removeNthFromEnd = function (head, n) {
    let node = head;
    let count = 0 ;
    //计算链表长度
    while(node) {
        node = node.next;
        count++;
    }
    count = count - n - 1
    if(count == -1) {
        return head.next
    }else {
        node = head;
        while(count > 0) {
        node = node.next;
        count--;
    }
    }
    node.next = node.next.next
    return head
};

4. 小结

以上就是本文JavaScript实现链表的全部内容了，希望你能从中学到好多好多东西噢~

今天的分享就到这里结束啦！

参考文献：javascript数据结构与算法