当前位置：首页 > 全部内容 > 正文

JavaScript数据结构之链表各种操作详解

作者：青柠

时间：2026-10-25

浏览：123

本文详细解析JavaScript中链表数据结构的实现原理与核心操作方法。对比数组优缺点，阐述链表内存分配与动态扩容优势。通过手动封装LinkedList类，逐步演示如何构建节点结构，并实现尾部添加、指定位置插入、元素获取、索引查找、数值修改及节点删除等关键功能，提供完整的代码实现思路。

文章目录

1 数组与链表的优缺点

链表与数组均可用于存储一系列元素，但两者的实现机制截然不同。

通常情况下，存储多个元素时数组是使用频率最高的数据结构，然而利用数组存储存在若干局限性：

  • 创建数组需申请一段连续的内存空间（即一整块内存），且其容量固定；若当前容量无法满足需求，则必须执行扩容操作（通常申请更大的数组，例如原大小的2倍，并将原有元素复制至新数组）。
  • 在数组的起始位置或中间位置插入数据成本高昂，因为涉及大量元素的位移操作。

存储多个元素的另一种选择是链表，与数组不同，链表中的元素在内存中无需占据连续空间；链表的每个元素由包含实际数据的节点以及指向下一个元素的引用（即指针）构成。

相较于数组，链表具备以下优势：

  • 内存空间无需连续，能够充分利用计算机内存，实现灵活的动态内存管理；
  • 链表在创建时无需确定大小，且容量可无限扩展；
  • 链表在执行插入和删除操作时，时间复杂度可达O(1)，效率远高于数组；

链表同样存在不足之处：

  • 访问链表中的任意元素均需从头节点开始遍历，且无法跳过首个元素直接访问后续元素。
  • 链表不支持通过下标直接访问元素，必须从头开始逐个访问直至定位到目标元素。

2 什么是链表

链表的每个元素由包含实际数据的节点以及指向下一个元素的引用（指针）构成。

其结构类似于火车，车头相当于头节点，车厢间的连接类似于指针，车厢内的乘客则代表数据。

1 数组与链表的优缺点

接下来我们将依据其特性手动封装一个链表实现。

3 封装链表结构

首先，我们封装一个链表类LindedList以表示链表结构。LindedList类内部应包含两个属性：链表的头节点head以及链表的长度length。

function LinkedList() {
    this.head = null; // 初始指向null
    this.length = 0; // 初始链表长度为0
}

在LindedList类内部定义一个ListNode类用于创建节点；创建节点时需传入数据data，且该节点需包含指向下一个节点的指针。

function LinkedList() {
    this.head = null; // 初始指向null
    this.length = 0; // 初始链表长度为0
    function ListNode(data) {
        this.data = data;
        this.next = null;
    }
}

至此，链表的基础结构构建完毕，接下来我们将封装链表的相关方法。

4 向链表尾部添加一个新的项

向链表尾部添加新节点时，需区分两种情况：

  • 若链表本身为空，则头节点即为新添加的节点。
  • 若链表不为空，则需使链表最后一个节点指向新添加的节点。

基于上述思路，append方法的实现如下：

LinkedList.prototype.append = function (data) { // data是新节点的值
    let node = new ListNode(data); // 创建新的节点
    if (this.length === 0) { // 如果链表为空，则新节点就是头节点
        this.head = node;
    } else { // 如果链表不为空，新节点添加到链表尾部
        let current = this.head; // 将current指向头节点
        // 链表无法直接访问到最后的节点，只能通过一次次遍历来访问
        while (current.next) { // 当达到最后一个节点时，循环结束
            // 当下一个节点存在时，就让current指针移动到下一个节点上
            current = current.next;
        }
        // 最后一个节点指向新节点
        current.next = node;
    }
    this.length += 1; // 链表的长度+1
}

5 向链表某个位置插入一个新的项

在链表任意位置插入节点时，同样分为两种情况：

  • 若插入位置为第一个位置，则新节点成为头节点，此时新节点需指向原头节点，且属性head也应更新为新节点。
  • 若插入位置为其他位置，则首先通过循环定位到该位置，同时保存前一个节点和后一个节点，随后将前一个节点指向新节点，新节点指向后一个节点。

插入insert方法的代码实现如下：

// position为节点要插入的位置，data为节点的值
LinkedList.prototype.insert = function (position, data) {
    // 对position进行越界判断，当该值小于0或者大于链表长度时，不能进行插入操作
    if (position <= 0 || position > this.length) return false;
    let node = new ListNode(data); // 创建新节点
    if (position === 0) { // 如果节点要插入第一个位置
        node.next = this.head; // 新节点指向原来的头节点
        this.head = node; // 头节点修改为新节点
    } else {
        let previous = null; // 指向前一个位置
        let current = this.head; // 指向下一个位置
        let index = 1; // 记录循环的位置
        // 循环结束，previous和current之间就是插入的节点
        while (index < position) {
            previous = current;
            current = current.next;
            index++;
        }
        previous.next = node; // 在正确的位置插入元素
        node.next = current;
    }
    this.length += 1; // 长度加1
}

6 获取对应位置的元素

获取指定位置的元素需通过循环遍历链表以定位当前元素，get方法的实现如下：

LinkedList.prototype.get = function (position) {
    // 越界判断，如果位置小于0或者大于链表长度，不能获取到元素
    if (position <= 0 || position > this.length) return null;
    let index = 1; // 记录当前位置
    let current = this.head; // current指向头节点
    // 循环结束，current指向该位置上的节点
    while (index < position) {
        current = current.next;
        index++;
    }
    return current.data;
}

7 获取元素在链表中的索引

获取索引时需循环遍历链表，将每个节点的值与给定值进行比较；若相等则返回当前节点的位置索引，若未找到则返回-1。indexOf方法的实现如下：

// 获取某个元素的位置
LinkedList.prototype.indexOf = function (data) {
    let current = this.head;
    let index = 1; // 记录元素的位置
    while (current) { // 循环遍历链表
        if (current.data === data) { // 如果当前节点的值等于元素的值
            return index; // 返回位置
        } else { // 如果不等于，继续循环
            current = current.next;
            index++;
        }
    }
    return -1; // 循环结束了，说明没找到
}

8 修改某个位置的元素

修改指定位置的元素时，需循环遍历链表以定位给定位置，并修改该位置元素的值。update方法的实现如下：

// 修改某个位置的元素
LinkedList.prototype.update = function (position, data) {
    // 越界判断
    if (position <= 0 || position > this.length) return false;
    let current = this.head;
    let index = 1;
    while (index < position) {
        current = current.next;
        index++;
    }
    current.data = data; // 修改数据
    return true;
}

9 从链表中删除某位置节点

删除指定位置的节点分为两种情况：

  • 若删除第一个位置的节点，需将该位置节点指向null，并使第二个位置的节点成为新的头节点。
  • 若删除其他位置的节点，需循环定位到该位置，同时记录前一个节点，并将前一个节点指向该位置的下一个节点。

删除某位置节点removeAt方法的实现如下：

LinkedList.prototype.removeAt = function (position) {
    if (position <= 0 || position > this.length) return false; // 越界判断
    let current = this.head;
    if (position === 1) { // 如果删除第一个位置上的节点（头节点）
        this.head = this.head.next;
    } else { // 删除其他位置的节点
        let index = 1; // 记录当前位置
        let previous = null;
        while (index < position) {
            previous = current;
            current = current.next;
            index++;
        }
        // 上一个节点指向当前元素的下一个节点
        previous.next = current.next;
    }
    this.length--;
    return current; // 返回被删除的节点
}

10 全部代码

function LinkedList() {
    this.head = null; // 初始指向null
    this.length = 0; // 初始链表长度为0
    function ListNode(data) { // 创建新节点类
        this.data = data;
        this.next = null;
    }
    // 添加元素
    LinkedList.prototype.append = function (data) { // data是新节点的值
        let node = new ListNode(data); // 创建新的节点
        if (this.length === 0) { // 如果链表为空，则新节点就是头节点
            this.head = node;
        } else { // 如果链表不为空，新节点添加到链表尾部
            let current = this.head; // 将current指向头节点
            // 链表无法直接访问到最后的节点，只能通过一次次遍历来访问
            while (current.next) { // 当达到最后一个节点时，循环结束
                // 当下一个节点存在时，就让current指针移动到下一个节点上
                current = current.next;
            }
            // 最后一个节点指向新节点
            current.next = node;
        }
        this.length += 1; // 链表的长度+1
    }
    // 插入元素
    // position为节点要插入的位置，data为节点的值
    LinkedList.prototype.insert = function (position, data) {
        // 对position进行越界判断，当该值小于0或者大于链表长度时，不能进行插入操作
        if (position <= 0 || position > this.length) return false;
        let node = new ListNode(data); // 创建新节点
        if (position === 0) { // 如果节点要插入第一个位置
            node.next = this.head; // 新节点指向原来的头节点
            this.head = node; // 头节点修改为新节点
        } else {
            let previous = null; // 指向前一个位置
            let current = this.head; // 指向下一个位置
            let index = 1; // 记录循环的位置
            // 循环结束，previous和current之间就是插入的节点
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            previous.next = node; // 在正确的位置插入元素
            node.next = current;
        }
        this.length += 1; // 长度加1
    }
    // 获取某个位置上的元素
    LinkedList.prototype.get = function (position) {
        // 越界判断，如果位置小于0或者大于链表长度，不能获取到元素
        if (position <= 0 || position > this.length) return null;
        let index = 1; // 记录当前位置
        let current = this.head; // current指向头节点
        // 循环结束，current指向该位置上的节点
        while (index < position) {
            current = current.next;
            index++;
        }
        return current.data;
    }
    // 获取某个元素的位置
    LinkedList.prototype.indexOf = function (data) {
        let current = this.head;
        let index = 1; // 记录元素的位置
        while (current) { // 循环遍历链表
            if (current.data === data) { // 如果当前节点的值等于元素的值
                return index; // 返回位置
            } else { // 如果不等于，继续循环
                current = current.next;
                index++;
            }
        }
        return -1; // 循环结束了，说明没找到
    }
    // 修改某个位置的元素
    LinkedList.prototype.update = function (position, data) {
        // 越界判断
        if (position <= 0 || position > this.length) return false;
        let current = this.head;
        let index = 1;
        while (index < position) {
            current = current.next;
            index++;
        }
        current.data = data; // 修改数据
        return true;
    }
    LinkedList.prototype.removeAt = function (position) {
        if (position <= 0 || position > this.length) return false; // 越界判断
        let current = this.head;
        if (position === 1) { // 如果删除第一个位置上的节点（头节点）
            this.head = this.head.next;
        } else { // 删除其他位置的节点
            let index = 1; // 记录当前位置
            let previous = null;
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            // 上一个节点指向当前元素的下一个节点
            previous.next = current.next;
        }
        this.length--;
        return current; // 返回被删除的节点
    }
}

至此，关于JavaScript数据结构之链表各种操作详解的文章介绍完毕，更多相关JS链表内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！

实用工具推荐

电子包浆

绿化、压缩、噪点和虚拟水印，自由调节做旧程度。

使用 ›
图片压缩

选择画质和输出格式，预览压缩前后的大小。

使用 ›
作者最新文章

JS读取本地文件时报错或无响应的常见原因

let、const与var的区别：JavaScript变量声明最佳实践

JS中直接定义静态二维数组的字面量写法

JS 怎么查找字符串中所有匹配项的位置

JavaScript新手常犯的编码错误与最佳实践指南

相关文章
热门文章
更多
CSS text-transform与JS修改首字母大写的适用场景区别
JS中constructor属性判断数组存在哪些风险
JS正则替换中$1捕获组引用与字符串重组技巧
全栈开发中JavaScript与Java怎么协作？前后端技术栈配合解析
Node.js后端生成高强度随机字符串的方法
怎么在本地运行JavaScript脚本：Node.js下载安装与环境配置教程
JS正则表达式基础：字面量与RegExp构造函数的区别及常用元字符
JS 解压出现乱码或报错怎么解决？
JavaScript常见SyntaxError语法错误排查与修复方法
JS动态构建复杂嵌套JSON对象的方法