首页 > 资讯 > 前端开发 > JavaScript >JavaScript数据结构之链表各种操作详解

219

分享到

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

JavaScript链表 JavaScript数据结构 JS链表 2022-11-13 18:11:21 219人浏览薄情痞子

摘要

目录1 数组与链表的优缺点2 什么是链表3 封装链表结构4 向链表尾部添加一个新的项5 向链表某个位置插入一个新的项6 获取对应位置的元素7 获取元素在链表中的索引8 修改某个位置的

1 数组与链表的优缺点

链表和数组一样，都可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。

一般情况下，要存储多个元素，数组可能是最常用的数据结构。但是使用数组存储有一些缺点：

数组的创建需要申请一段连续的内存空间（一整块的内存），并且大小是固定的，所以当当前数组不能满足容量需求时，就需要扩容（一般情况下会申请一个更大的数组，比如2倍，然后将原数组中的元素复制过去）。
在数组的开头或中间位置插入数据的成本很高，需要进行大量元素的位移。

存储多个元素的另一个选择就是链表，但是不同于数组，链表中的元素在内存中不必是连续的空间，链表的每个元素由一个存储元素本身的节点和指向下一个元素的引用（指针）组成。

那么和数组相比，链表有一些优势：

内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的内存动态管理；
链表不必在创建时就确定大小，并且大小可以无限延伸下去；
链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多；

链表也有一些缺点：

链表访问任何一个元素的位置时，都需要从头开始访问，并且无法跳过第一个元素访问任何一个元素
链表无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素

2 什么是链表

链表的每个元素由一个存储元素本身的节点和指向下一个元素的引用（指针）组成。

它类似于火车，火车头就是头节点，火车车厢之间的连接类似于指针，火车上的乘客类似于数据。

接下来我们根据它的特性来手动封装一个链表。

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链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: JavaScript数据结构之链表各种操作详解

本文链接: https://www.lsjlt.com/news/169713.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

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

目录1 数组与链表的优缺点2 什么是链表3 封装链表结构4 向链表尾部添加一个新的项5 向链表某个位置插入一个新的项6 获取对应位置的元素7 获取元素在链表中的索引8 修改某个位置的...

99+

2022-11-13

JavaScript链表 JavaScript数据结构 JS链表
关于数据结构单向链表的各种操作

目录关于节点数据添加：尾添加头添加一次性添加n个x数据节点：关于查找：根据指定数据：根据下标查找：删除头节点：删除尾节点：删除中间节点：删除全部节点：关于节点数据添加：尾添加最核...

99+

2023-05-15

数据结构数据结构单向链表
C语言数据结构之单链表操作详解

目录1、插入操作2、删除操作3、查找操作4、修改操作5、完整代码1、插入操作（1）创建一个新的要插入的结点（2）将新结点的 next 指针指向插入位置后的结点（3）将插入位置前...

99+

2024-04-02
Python数据结构之链表详解

目录0.学习目标1.线性表的链式存储结构1.1指针相关概念1.2指针结构1.3结点1.4结点类2.单链表的实现2.1单链表的初始化2.2获取单链表长度2.3读取指定位置元素2.4查找...

99+

2024-04-02
Redis数据结构之链表详解

目录1 链表和链表节点的结构2 链表相关的API1 链表和链表节点的结构 1.1 节点结构节点的结构大概长下边这个样子：那么，把这些节点就连起来就成了这个样子： 1.2 链表...

99+

2024-04-02
Java数据结构之链表详解

目录一、链表的介绍二、单链表的实现三、双向链表的实现四、循环链表的实现五，链表相关的面试题一、链表的介绍什么是链表链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑...

99+

2024-04-02
C++数据结构之链表详解

目录前言一、删除链表中给定值为key的节点二、反转链表三、返回链表的中间节点四、删除链表的倒数第K个节点五、分割链表六、合并两个有序链表七、删除有序链表中重复节点八、环形链表九、相交...

99+

2024-04-02
Java数据结构之单链表详解

目录一、图示二、链表的概念及结构三、单链表的实现四、完整代码的展示一、图示二、链表的概念及结构链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的...

99+

2024-04-02
Python数据结构之双向链表详解

目录0. 学习目标1. 双向链表简介1.1 双向链表介绍1.2 双向链表结点类1.3 双向链表优缺点2. 双向链表实现2.1 双向链表的初始化2.2 获取双向链表长度2.3 读取指定...

99+

2024-04-02
数据结构TypeScript之链表实现详解

目录链表结构特点面向对象方法封装链表构造函数基本单元：链表节点主体：链表查找节点增加节点删除节点链表结构特点链表是线性表的其中一种，用于存储有固定顺序的元素。而元素之间会通过&r...

99+

2023-01-30

TypeScript数据结构链表 TypeScript数据结构
Python数据结构之循环链表详解

目录0. 学习目标1. 循环链表简介2. 循环单链表实现2.1 循环单链表的基本操作2.2 简单的实现方法2.3 循环单链表应用示例2.4 利用循环单链表基本操作实现复杂操作3. 循...

99+

2024-04-02
Python数据结构与算法之链表,无序链表详解

目录我们首先来构造节点。节点（Node）的类构建完毕后，接下来我们开始构建整个链表（LinkList）的类。那么我们还需要一个方法来判断链表头的指向。接下来我们构建链表节点的添加方法...

99+

2024-04-02
python数据结构之链表

'''' 链表的实现，单向链表 ''' '''建立节点''' class jd: def __init__(self,data): self.data = data self.next = None...

99+

2023-01-31

数据结构链表 python
详谈mysql各种常用操作数据表结构的用法【建议收藏】

文章目录一.修改系列1.修改表名：2.修改表的注释：3.修改表字段名：4.修改表字段的数据类型：5.修改表字段的数据类型长度：6.修改表字段的默认值：7.修改表字段的注释：二.创建系列...

99+

2023-10-08

mysql
C语言数据结构之双链表&循环链表&静态链表详解

目录单链表 VS 双链表双链表双链表的初始化（带头结点）双链表的插入双链表的删除双链表的遍历循环单链表循环双链表循环双链表的初始化循环双链表的插入循环双链表的删除静态链表什么是静态链...

99+

2024-04-02
JavaScript数据结构之链表的示例分析

这篇文章主要为大家展示了“JavaScript数据结构之链表的示例分析”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“JavaScript数据结构之链表的示例分析...

99+

2024-04-02
python数据结构之链表（linked

目录基础知识 1.1 链表的基本结构 1.2 节点类和链表节点的定义 1.3 顺序打印和逆序打印链表的基本操作 2.1 计算链表长度 2.2 从前，后插入数据 2.3 查找与删除参考 1.基础知识 1....

99+

2023-01-31

数据结构链表 python
C++数据结构之单链表

目录单链表结构的定义单链表打印动态申请一个结点单链表尾插单链表尾删单链表头插单链表头删求单链表长度单链表查找单链表在pos位置插入单链表在pos后面位置插入单链表删除pos位置单链表...

99+

2024-04-02
C++数据结构中链表有哪些操作

这篇文章主要为大家展示了“C++数据结构中链表有哪些操作”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“C++数据结构中链表有哪些操作”这篇文章吧。首先创建好一个节点typedef st...

99+

2023-06-25
Java数据结构之链表的增删查改详解

目录一、链表的概念和结构1.1 链表的概念1.2 链表的分类二、单向不带头非循环链表2.1 创建节点类型2.2 头插法2.3 尾插法2.4 获取链表长度2.5 任意位置插入2.6 查...

99+

2024-04-02