AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

前端算法基础-链表

2023-12-20 68
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 前端算法基础-链表

链表

在计算机科学中, 一个 链表 是数据元素的线性集合, 元素的线性顺序不是由它们在内存中的物理位置给出的。 相反, 每个元素指向下一个元素。它是由一组节点组成的数据结构,这些节点一起,表示序列。

简单的说， 链表由无数个节点组成，而节点=当前节点内容+下一个节点，当到了结尾，下一个节点指向null空指针。

image.png

分类

单向链表

一般为了标识链表的头部，会在第一个节点加上head标识：

image.png

双向链表

在计算机科学中, 一个 双向链表(doubly linked list) 是由一组称为节点的顺序链接记录组成的链接数据结构。每个节点包含两个字段，称为链接，它们是对节点序列中上一个节点和下一个节点的引用。开始节点和结束节点的上一个链接和下一个链接分别指向某种终止节点，通常是前哨节点或null，以方便遍历列表。如果只有一个前哨节点，则列表通过前哨节点循环链接。它可以被概念化为两个由相同数据项组成的单链表，但顺序相反。

image.png

循环链表

循环链表同时又可以区分为 单向循环链表、双向循环链表

image.png

优缺点

  • 优点：适合动态插入和删除的应用场景
  • 缺点：不能快速的定位和随机访问数据

应用场景（非前端）

从网上搜索来的几种应用场景：

  • LRU 缓存淘汰算法。
  • 各类缓冲池 和 栈 的实现。
  • 使用链接来解决哈希冲突的哈希表。
  • 简单的内存分配器。
  • FAT文件系统中大文件的元数据。

基本上，前端都没有场景可以应用到链表数据结构，所以很多时候前端开发者学习链表

代码实现

在JavaScript，并没有直接以链表为结构的数据类型，所以如果我们要在JavaScript实现一个链表，需要自己去实现。

一个完整链表结构LinkNode 包括几块：

  1. 属性：节点内容+下一个节点指向next
  2. 方法：新增、删除等方法

单向链表

class LinkNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
    toString() {
        return this.value;
    }
}
class LinkList {
    // 构造函数
    constructor() {
        this.head = null;
        this.length = 0;
    }
    // 追加
    append(value) {
        const node = new LinkNode(value);
        if (this.head === null) {
            this.head = node;
        } else {
            let current = this.head;
            // 将当前节点挪到最后
            while (current.next) {
                current = current.next;
            }
            current.next = node;
        }
        this.length++;
        return this;
    }
    // 在指定对象插入链表节点
    insert(existValue, insertValue) {
        const node = new LinkNode(insertValue);
        const existNode = this.find(existValue);
        if (existNode === null) {
            throw new Error("插入的节点值不存在");
        }
        const nextNode = existNode.next;
        existNode.next = node;
        node.next = nextNode;
        this.length++;
        return this;
    }
    // 删除指定对象 返回删除节点
    remove(value) {
        if (this.head === null) {
            throw new Error("链表为空，无法删除");
        }
        // 第一个删除
        if (this.head.value === value) {
            const current = this.head;
            this.head = this.head.next;
            current.next = null;
            this.length--;
            return current;
        }
        // 查找前一个
        const preNode = this.findPre(value)
        if (preNode !== null) {
            const removeNode = preNode.next;
            const nextNode = removeNode.next;
            preNode.next = nextNode;
            removeNode.next = null;
            this.length--;
            return removeNode;
        }
    }
    // 查询
    find(value) {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        while (current.next && current.value !== value) {
            current = current.next
        }
        if (current.value === value) {
            return current;
        }
        return null;
    }
    // 查询值的前一个
    findPre(value) {
        let current = this.head;
        let prevNode = null;
        while (current.next && current.next.value !== value) {
            current = current.next;
        }
        if (current.next && current.next.value === value) {
            prevNode = current;
        }
        return prevNode
    }
    toString() {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        const array = [];
        while (current.next) {
            array.push(current.value);
            current = current.next;
        }
        array.push(current.value);
        return array.join('->');
    }
}
// 测试案例
const linkList = new LinkList();
linkList.append("1");
linkList.append("2");
linkList.append("3");
// 预期输出1->2->3
console.log(linkList.toString());
linkList.insert("2", "4");
// 预期输出1->2->4->3
console.log(linkList.toString());
linkList.remove("2");
// 预期输出1->4->3
console.log(linkList.toString());

双向链表

相比较单向链表，多了一个指向前者对象 prev。

class LinkNode {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
    toString() {
        return this.value;
    }
}
class LinkList {
    // 构造函数
    constructor() {
        this.head = null;
        this.length = 0;
    }
    // 追加
    append(value) {
        const node = new LinkNode(value);
        if (this.head === null) {
            this.head = node;
        } else {
            let current = this.head;
            // 将当前节点挪到最后
            while (current.next) {
                current = current.next;
            }
            current.next = node;
            node.prev = current;
        }
        this.length++;
        return this;
    }
    // 在指定对象插入链表节点
    insert(existValue, insertValue) {
        const node = new LinkNode(insertValue);
        const existNode = this.find(existValue);
        if (existNode === null) {
            throw new Error("插入的节点值不存在");
        }
        const nextNode = existNode.next;
        existNode.next = node;
        node.next = nextNode;
        node.prev = existNode;
        nextNode.prev = node;
        this.length++;
        return this;
    }
    // 删除指定对象 返回删除节点
    remove(value) {
        if (this.head === null) {
            throw new Error("链表为空，无法删除");
        }
        // 第一个删除
        if (this.head.value === value) {
            const current = this.head;
            this.head = this.head.next;
            current.next = null;
            this.length--;
            return current;
        }
        // 查找前一个
        const preNode = this.findPre(value)
        if (preNode !== null) {
            const removeNode = preNode.next;
            const nextNode = removeNode.next;
            const prevNode = removeNode.prev;
            preNode.next = nextNode;
            nextNode.prev = preNode;
            removeNode.next = null;
            removeNode.prev = null;
            this.length--;
            return removeNode;
        }
    }
    // 查询
    find(value) {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        while (current.next && current.value !== value) {
            current = current.next
        }
        if (current.value === value) {
            return current;
        }
        return null;
    }
    // 查询值的前一个
    findPre(value) {
        let current = this.head;
        let prevNode = null;
        while (current.next && current.next.value !== value) {
            current = current.next;
        }
        if (current.next && current.next.value === value) {
            prevNode = current;
        }
        return prevNode
    }
    toString() {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        const array = [];
        while (current.next) {
            array.push(current.value);
            current = current.next;
        }
        array.push(current.value);
        return array.join('<->');
    }
}
// 测试案例
const linkList = new LinkList();
linkList.append("1");
linkList.append("2");
linkList.append("3");
// 预期输出 1<->2<->3
console.log(linkList.toString());
linkList.insert("2", "4");
// 预期输出 1<->2<->4<->3
console.log(linkList.toString());
linkList.remove("2");
// 预期输出 1<->2<->3
console.log(linkList.toString());

循环链表

循环链表对比之前，会把最后一个节点的netx指向第一个节点， 第一个节点的prev指向最后一个节点

class LinkNode {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
    toString() {
        return this.value;
    }
}
class LinkList {
    // 构造函数
    constructor() {
        this.head = null;
        this.length = 0;
    }
    // 追加
    append(value) {
        const node = new LinkNode(value);
        if (this.head === null) {
            this.head = node;
        } else {
            let current = this.head;
            // 将当前节点挪到最后 由于循环 这里需要多判断一个是否指向头部
            while (current.next && current.next !== this.head) {
                current = current.next;
            }
            current.next = node;
            node.prev = current;
            // 将最后一个指针指向第一个
            node.next = this.head;
            this.head.prev = node;
        }
        this.length++;
        return this;
    }
    // 在指定对象插入链表节点
    insert(existValue, insertValue) {
        const node = new LinkNode(insertValue);
        const existNode = this.find(existValue);
        if (existNode === null) {
            throw new Error("插入的节点值不存在");
        }
        const nextNode = existNode.next;
        existNode.next = node;
        node.next = nextNode;
        node.prev = existNode;
        nextNode.prev = node;
        this.length++;
        return this;
    }
    // 删除指定对象 返回删除节点
    remove(value) {
        if (this.head === null) {
            throw new Error("链表为空，无法删除");
        }
        // 第一个删除
        if (this.head.value === value) {
            const current = this.head;
            this.head = current.next;
            this.head.prev = current.prev;
            current.next = null;
            current.prev = null;
            this.length--;
            return current;
        }
        // 查找前一个
        const preNode = this.findPre(value)
        if (preNode !== null) {
            const removeNode = preNode.next;
            const nextNode = removeNode.next;
            const prevNode = removeNode.prev;
            prevNode.next = nextNode;
            nextNode.prev = preNode;
            removeNode.next = null;
            removeNode.prev = null;
            this.length--;
            return removeNode;
        }
    }
    // 查询
    find(value) {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        while (current.next != this.head && current.value !== value) {
            current = current.next
        }
        if (current.value === value) {
            return current;
        }
        return null;
    }
    // 查询值的前一个
    findPre(value) {
        let current = this.head;
        let prevNode = null;
        while (current.next != this.head && current.next.value !== value) {
            current = current.next;
        }
        if (current.next && current.next.value === value) {
            prevNode = current;
        }
        return prevNode
    }
    toString() {
        if (this.head === null) {
            return null;
        }
        let current = this.head;
        const array = [];
        while (current.next != this.head) {
            array.push(current.value);
            current = current.next;
        }
        array.push(current.value);
        return array.join('<->');
    }
}
// 测试案例
const linkList = new LinkList();
linkList.append("1");
linkList.append("2");
linkList.append("3");
// 预期输出 1<->2<->3
console.log(linkList.toString());
linkList.insert("2", "4");
// 预期输出 1<->2<->4<->3
console.log(linkList.toString());
linkList.remove("2");
// 预期输出 1<->2<->3
console.log(linkList.toString());
// 第一个的prev 指向最后 输出3
console.log(linkList.head.prev.toString());
// 最后一个 next指向第一个 输出1
console.log(linkList.head.prev.next.toString());

源码地址放在 Github上，地址是：github.com/qiubohong/f…

文章标签：
前端开发
算法
JavaScript
缓存
开发者
关键词：
链表算法
算法链表
前端算法
算法前端
链表前端
QBorfy
目录
相关文章
Cyan_RA9
|
25天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表（下）
408考研——《数据结构》算法题基础篇之链表（下）。
Cyan_RA9
83 29
陌陌谣
|
1天前
|
存储 监控 算法
公司监控上网软件架构：基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代，公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录，具备高效插入、删除操作及节省内存的优势，助力企业实时追踪员工上网行为，提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为，并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式，但实际开发还需考虑安全性、隐私保护等多方面因素。
陌陌谣
11 0
公司监控上网软件架构：基于 C++ 链表算法的数据关联机制探讨
Cyan_RA9
|
25天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表（上）
408考研——《数据结构》算法题基础篇之链表（上）。
Cyan_RA9
92 25
Codelinghu
|
4月前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
Codelinghu
100 1
Codelinghu
|
4月前
|
算法 索引
❤️算法笔记❤️-(每日一刷-141、环形链表)
❤️算法笔记❤️-(每日一刷-141、环形链表)
Codelinghu
74 0
Codelinghu
|
4月前
|
算法
【❤️算法笔记❤️】-(每日一刷-876、单链表的中点)
【❤️算法笔记❤️】-(每日一刷-876、单链表的中点)
Codelinghu
74 0
Codelinghu
|
4月前
|
算法
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
Codelinghu
53 0
Codelinghu
|
4月前
|
存储 算法
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
Codelinghu
158 0
多客潇潇
|
2月前
|
机器学习/深度学习 前端开发 算法
婚恋交友系统平台 相亲交友平台系统 婚恋交友系统APP 婚恋系统源码 婚恋交友平台开发流程 婚恋交友系统架构设计 婚恋交友系统前端/后端开发 婚恋交友系统匹配推荐算法优化
婚恋交友系统平台通过线上互动帮助单身男女找到合适伴侣，提供用户注册、个人资料填写、匹配推荐、实时聊天、社区互动等功能。开发流程包括需求分析、技术选型、系统架构设计、功能实现、测试优化和上线运维。匹配推荐算法优化是核心，通过用户行为数据分析和机器学习提高匹配准确性。
多客潇潇
201 3
肾透侧视攻城狮
|
3月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
52 2

热门文章

最新文章

  • 1
    DeepSeek加持的通义灵码2.0 AI程序员实战案例：助力嵌入式开发中的算法生成革新
  • 2
    Python 实现单向链表，和单向链表的反转
  • 3
    接入DeepSeek需要做算法备案吗？一文读懂算法备案的那些事儿
  • 4
    近端策略优化(PPO)算法的理论基础与PyTorch代码详解
  • 5
    基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
  • 6
    算法系列之分治算法
  • 7
    C 408—《数据结构》算法题基础篇—链表（上）
  • 8
    算法系列之搜索算法-深度优先搜索DFS
  • 9
    【算法合规新时代】企业如何把握“清朗·网络平台算法典型问题治理”专项行动？
  • 10
    C 408—《数据结构》算法题基础篇—链表（下）
  • 1
    前端起dev从110秒减少到7秒, 开发体验大幅提升
    17
  • 2
    无前端经验如何快速搭建游戏站：使用 windsurf 从零到上线的详细指南
    33
  • 3
    【01】鸿蒙实战应用开发-华为鸿蒙纯血操作系统Harmony OS NEXT-项目开发实战-优雅草卓伊凡拟开发一个一站式家政服务平台-前期筹备-暂定取名斑马家政软件系统-本项目前端开源-服务端采用优雅草蜻蜓Z系统-搭配ruoyi框架admin后台-全过程实战项目分享-从零开发到上线
    39
  • 4
    VSCode AI提效工具，通义灵码前端开发体验
    95
  • 5
    开箱即用的GO后台管理系统 Kratos Admin - 前端权限
    13
  • 6
    以项目登录接口为例-大前端之开发postman请求接口带token的请求测试-前端开发必学之一-如果要学会联调接口而不是纯写静态前端页面-这个是必学-本文以优雅草蜻蜓Q系统API为实践来演示我们如何带token请求接口-优雅草卓伊凡
    47
  • 7
    大前端之前端开发接口测试工具postman的使用方法-简单get接口请求测试的使用方法-简单教学一看就会-以实际例子来说明-优雅草卓伊凡
    84
  • 8
    【2025优雅草开源计划进行中01】-针对web前端开发初学者使用-优雅草科技官网-纯静态页面html+css+JavaScript可直接下载使用-开源-首页为优雅草吴银满工程师原创-优雅草卓伊凡发布
    36
  • 9
    【11】flutter进行了聊天页面的开发-增加了即时通讯聊天的整体页面和组件-切换-朋友-陌生人-vip开通详细页面-即时通讯sdk准备-直播sdk准备-即时通讯有无UI集成的区别介绍-开发完整的社交APP-前端客户端开发+数据联调|以优雅草商业项目为例做开发-flutter开发-全流程-商业应用级实战开发-优雅草Alex
    159
  • 10
    详解智能编码在前端研发的创新应用
    122

    • 相关课程

    更多
  • 移动Web前端开发
  • Ajax 前端开发入门与实战
  • 零基础学前端HTML+CSS
  • 前端开发CSS基础
  • 前端开发框架Bootstrap使用教程
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • Vue.js 在前端服务化上的探索与实践
  • 阿里文娱大前端技术实践
  • 前端代码是怎样智能生成的

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • 前端开发基础3：CSS3常见显示属性
  • 前端开发基础6：Node.js和LESS预编译工具
  • 前端开发基础2：VS Code和Edge的联动开发
  • 前端开发基础1：前端开发环境的安装和配置
  • RSA非对称加密算法
    • 下一篇
    通义万相：视觉生成大模型再进化