javaScript实现链表结构

说在前面

今天仍是数据结构专题，让我们一起通过 JavaScript 来再一次熟悉一下链表吧。

什么是链表？

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间，而线性表和顺序表相应的时间复杂度分别是 O(logn)和 O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像 Lisp 和 Scheme 这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如 C,C++和 Java 依靠易变工具来生成链表。

实现思路

链表其实就是将一段一段的内存地址通过指针连接起来，我们只需要拿到链表的头结点就可以获取整个链表中的数据。我们可以把每一个节点看出一个对象，指针则是对象里的一个属性，这样我们是不是就可以使用 JavaScript 来快速实现一个链表了？

链表节点结构

一个链表节点需要以下几个属性：

• val：节点的值
• key：节点的键
• pre：上一个节点
• next：下一个节点

const linkLineNode = function (key = "", val = "") {
    this.val = val;
    this.key = key;
    this.pre = null;
    this.next = null;
};

链表初始化

初始化我们可以先分别创建一个头节点和尾节点，然后将两个节点连接起来，这样就有了一个最简单的空链表，然后将需要插入的节点插入即可。

constructor(arr = []){
    this.init(arr);
}
init(arr = []){
    const head = new linkLineNode("head", "head");
    const tail = new linkLineNode("tail", "tail");
    head.next = tail;
    tail.pre = head;
    this.head = head;
    this.tail = tail;
    this.size = 0;
    for(const str of arr){
        this.append(str);
    }
}

判断链表是否为空

判断当前链表是否为空，我们只需要判断当前链表中的头结点和尾节点直接是否有数据节点即可，头结点和尾节点直接相连则说明当前链表是空的。

isEmpty(){
    return this.head.next == this.tail;
}

删除链表节点

链表节点删除的操作如下图：

链表删除节点的过程就是指针重新指向的过程，将要删除的节点的两边的节点使用指针重新连接起来即可，这样中间的节点因为没有指针指向它，所以我们也就无法访问到它，这也就将其从链表中删除了。具体如下代码：

删除头部第一个节点

shift(){
    if(this.isEmpty()) return false;
    const node = this.head.next;
    this.head.next = this.head.next.next;
    this.head.next.pre = this.head;
    this.size--;
    return node.val;
}

删除尾部第一个节点

pop(){
    if(this.isEmpty()) return false;
    const node = this.tail.pre;
    this.tail.pre = this.tail.pre.pre;
    this.tail.pre.next = this.tail;
    this.size--;
    return node.val;
}

删除指定节点

delete(node){
    try{
        node.pre.next = node.next;
        node.next.pre = node.pre;
        this.size--;
    }catch(err){
        return -1;
    }
    return this.size;
}

插入链表节点

链表节点插入的操作如下图：

链表插入节点的过程也是指针重新指向的过程，将要插入的节点分别与要插入位置的两个节点建立指针连接。具体如下代码：

头部插入一个节点

unshift(val){
    if(!val) return -1;
    const node = new linkLineNode('node',val);
    node.next = this.head.next;
    node.pre = this.head;
    this.head.next.pre = node;
    this.head.next = node;
    this.size++;
    return this.size;
}

尾部插入一个节点

append(val){
        if(!val) return -1;
        const node = new linkLineNode('node',val);
        node.next = this.tail;
        node.pre = this.tail.pre;
        this.tail.pre.next = node;
        this.tail.pre = node;
        this.size++;
        return this.size;
    }

获取链表值

我们需要从头节点开始遍历，将遍历到的节点值保存进数组，直到遍历完链表再将数组返回即可，具体代码如下：

getValList(){
    const arr = [];
    let headNode = this.head;
    while(headNode.next != this.tail){
        headNode = headNode.next;
        arr.push(headNode.val);
    }
    return arr;
}

获取指定位置的节点

我们需要从头节点开始遍历，记录遍历到的下标，遍历到指定的下标则将该节点返回即可，具体代码如下：

getNode(index){
    let node = this.head;
    while(index--){
        node = node.next;
        if(!node) return null;
    }
    return node;
}

应用

• Git

git 里面每次 commit 都是创建一个 node，node 包含了删减后的新文件，然后 node 指向前一个 commit 的 node。git checkout、delete branch、merge、rebase 这些基本上都是以链表操作为主。git 应该算是对 linked list 很好的应用。不用 linked list 应该很难高效地实现 git 提供的功能。

• LFU 缓存算法

LFU（Least Frequently Used），即最不经常使用页置换算法。如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰，这就是 LFU 的核心思想。

之前我也有使用 JavaScript 实现过 LFU 缓存算法，感兴趣的可以查看：juejin.cn/post/705642…

• LRU 缓存算法

LRU 是 Least Recently Used 的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

之前我也有使用 JavaScript 实现过 LRU 缓存算法，感兴趣的可以查看：juejin.cn/post/705668…

源码地址

Gitee： gitee.com/zheng_yongt…

使用

目前我已经将代码上传到了 npm 上，大家可以直接npm install @jyeontu/structure-jyeontu进行安装，安装完成之后即可直接使用，如下：

const { LinkLine } = require("@jyeontu/structure-jyeontu");
const list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const linkList = new LinkLine(list);
linkList.pop();
linkList.shift();
linkList.unshift(10);
linkList.append(1);
const node = linkList.getNode(5);
linkList.delete(node);
console.log(linkList.getValList());
//[10, 2, 3, 4, 6, 7, 8, 9, 1]

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，在此谢谢大家的支持，我们下文再见 🙌。