扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 前端开发 > JavaScript >JavaScript实现单链表过程解析
  • 500

0
分享到

JavaScript实现单链表过程解析

2024-04-02 19:04:59 500人浏览 八月长安
摘要

前言： 要存储多个元素，数组是最常用的数据结构，但是数组也有很多缺点： 数组的创建通常要申请一段连续的内存空间，并且大小是固定的，所以当当前数组不能满足容量需求时，需要进行扩容，（一

前言：

要存储多个元素，数组是最常用的数据结构，但是数组也有很多缺点：

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

所以要存储多个元素，另一个选择就是链表，不同于数组的是，链表中的元素在内存中不必是连续的空间。链表的每个元素有一个存储元素本身的节点和指向下一个元素的引用。
相对于数组，链表有一些优点：

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

相对于数组，链表有一些缺点：

  • 链表访问任何一个位置的元素的时候，都需要从头开始访问，无法通过下标直接访问元素。

一、什么是单链表

那么到底什么是单链表呢？

它就类似于火车，火车头规连接一个节点，节点上有乘客，并且这个节点会连接到下一个节点，依次类推，如下所示：

我们的链表结构就是：

了解了直观上的链表，我们再来对单链表进行代码的封装。

二、单链表的封装

首先，我们封装一个nodeList类，用于表示链表结构，在这个类里面在封装一个内部类Node，用于封装每一个节点上的信息（数据和指向下一个节点的引用），然后在NodeList类中保存两个属性，一个是链表的长度，一个是链表中的头结点。

如下所示：


 function LinkedList(){
            this.length = 0;
            this.head = null;
            //内部的类
            function Node(data){
                this.data = data;
                this.next = null;
            }
        }

三、单链表的常用操作

然后在里面添加单链表常用的操作。主要有：

  • append（element) :向列表尾部添加一个项
  • insert(position,element) :向列表的特定位置插入一个项
  • get(position) :获取对应位置的元素
  • indexOf(element) :返回元素在列表中的索引，如果列表中没有该元素则返回-1
  • update(position，ele) :修改某个位置的元素
  • removeAt(position) :从列表的指定位置移除一项
  • remove(element) :从列表中移除一项
  • isEmpty() :如果链表中不包含任何元素，返回true,如果链表长度大于0返回false
  • size() :返回链表包含的元素个数，与数组的length属性相关
  • toString() :由于列表项用到了Node类，需要重写继承自javascript对象默认的toString方法，让其输出元素的值

接下来们就来一个一个实现。

1、append(element)方法-----向列表尾部添加一个项

因为向链表尾部添加数据可能有两种情况：

  • 链表本身为空，新添加的数据是唯一的节点
  • 链表不为空，需要向其他节点后面追加节点

所以我们就需要进行判断，如果链表为空，直接将头结点的指针指向新节点。
如果链表不为空，则新建立一个临时节点，让它等于头结点，并对它进行判断，如果它指向的节点的指针域为空，则为尾节点，将新加的节点添加到末尾，即让尾节点的指针指向新添加的节点。如果它指向的节点的指针域不为空，则让这个临时节点的指针域指向下一个节点，一直循环操作到这个节点的指针域为空（即为尾节点）。然后每添加一个节点，让链表的长度+1。


LinkedList.prototype.append = function(data){
                var newNode = new Node(data);
                // 判断链表是否为空
                // 1.为空
                if(this.length === 0){
                    this.head = newNode;
                }else{
                    //不为空
                    var current = this.head;
                    if(current.next){
                        current = current.next;
                    }
                    current.next = newNode;
                }
                this.length += 1;
            }

2、toString方法-----输出元素的值

这个比较简单，主要是获取每一个元素，因为获取链表的任何元素都必须从第一个节点开始，所以我们可以从头结点开始，循环遍历每一个节点，并且取出其中的element，拼接成字符串，并将字符串返回。


LinkedList.prototype.toString = function(){
                var current = this.head;
                var ListStr = '';
                while(current){
                    ListStr += current.data + ' ';
                    current = current.next;
                }
                return ListStr;
            }

验证：创建几个新的节点，并打印


 var list = new LinkedList();
        list.append('a');
        list.append('b');
        list.append('c');
        list.append('d');
        list.append('e');
        alert(list);

打印结果为：

3、insert方法-----向列表的特定位置插入一个项

实现在任意位置插入数据的方法，首先判断插入的位置是否越界，然后在不越界的情况下分两种情况，如果插入到第一个位置，则表示新添加的节点是头，则需要将原来的头结点作为新节点的next,再让head指向新节点。如果插入到其他位置，则需要通过循环先找到节点位置，并在循环的过程中保存上一个节点和下一个节点，找到正确的位置后，将新节点的Next指向下一个节点，将上一个节点的next节点指向新节点。

代码如下：


 LinkedList.prototype.insert = function(position,data){
                if(position<0 || position >this.length){
                   return false;
               }
                var newNode = new Node(data);
                var index = 0;
              if(position == 0){
                newNode.next = this.head;
                this.head = newNode;

              }else{
                    while(index++ < position){
                        var current = this.head;
                        var previous = null;
                        previous = current;
                        current = current.next;
                    }
                    newNode.next = current;
                    previous.next = newNode;
                }
                this.length += 1;
                return true;
                }

验证：在第1个位置插入xl,在第2个位置插入wh


list.insert(1,'xl')
       list.insert(2,'wh')
        alert(list)

4、get方法-----获取对应位置的元素

这个方法相对简单，先对positon做越界判断，然后通过临时节点遍历链表直到目标位置，获取该位置的元素。


LinkedList.prototype.get = function(position,data){

                var current = this.head;
                var index = 0;
                if(position < 0 || position >= this.length){
                    return null;
                }else{
                    while(index<position){
                        current = current.next;
                        index++;
                    }
                    return current.data;
                }
            }

验证：获取第三个位置的元素：


alert( list.get(3));

5、indexOf()方法-----返回元素在列表中的索引

首先判断查找的元素的位置是否存在，如果不存在，返回-1。如果存在的话分两种情况，如果返回的元素在第一个位置，则直接返回第一个位置的索引。如果返回元素在其他位置，则需要通过循环先找到节点位置，这个过程中，索引需要跟着遍历的次数自加，找到正确元素的位置后，打印索引即为目标位置。


LinkedList.prototype.indexOf = function(data){
                var index = 0;
                var current = this.head;
                while(current){
                    if(current.data == data){
                        return index;
                    }
                    else{
                        current = current.next;
                    index++;
                    }
                }
                return -1;
            }
        }

验证：获取c的索引：


alert(list.indexOf('c'));

6、update方法-----修改某个位置的元素

这个方法和get方法很像，向后遍历，当index的值等于position时，表示找到目标位置，将date改为目标值：


LinkedList.prototype.update = function(position,ele){
                if(position<0 || position>=this.length){
                    return false;
                }else{
                    var index = 0;
                    var current = this.head;
                    while(index++ <position){
                        current = current.next;
                    }
                    current.data = ele;
                    return true;
                }
            }

验证：修该第0个位置的元素为：bear


 list.update(0,'bear')
      alert(list)

7、removeAt方法-----从列表的指定位置移除一项

首先判断删除项的位置是否越界，然后在不越界的情况下，给定两个临时节点previous和current，previous用来保存前一个current的值，从头节点开始遍历，直到索引位置等于目标位置，让临时节点current遍历到目标位置，让临时节点的前一个next指向下一个next。


LinkedList.prototype.removeAt = function(position,data){
                var current = this.head;
                var previous = null;
                var index = 0;
                if(position<0 || position>=this.length){
                    return false;
                }else{
                    while(index++ <position){
                        previous = currrent;
                        current = current.next;
                    }
                    previous.next = current.next;
                    this.length -= 1;
                    return true;
                }
            }
        }

验证：移除第三个位置的元素：


list.removeAt(3)
      alert(list)

8、remove方法-----从列表中移除一项

先判断所要删除的元素是否在链表中，如果不在，返回false，否则，构建一个临时节点，用于遍历链表，如果临时节点的data值和要删除的元素相等，则停止遍历，让临时节点的前一个next指向下一个next。这里可以在构建一个临时节点用于存储前一个current的值。


LinkedList.prototype.remove = function(ele){
                var current = this.head;
                var previous = null;
                var index = 0;
                while(current.data !== ele){
                    previous = current;
                    current = current.next;
                    index++;
                }
                previous.next = current.next;
            }

验证：删除值为xl的元素：


 list.remove('xl')
      alert(list)

9、isEmpty方法-----判断链表是否为空

根据length判断，如果链表中不包含任何元素，返回true,如果链表长度大于0返回false


LinkedList.prototype.isEmpty = function(){
                    return this.length == 0;
                }

验证：


 alert(list.isEmpty())

9、size方法-----返回链表包含的元素个数

直接返回元素的length就是其个数。


LinkedList.prototype.size = function(){
                    return this.length;
                }

验证：


   alert(list.size())

到此这篇关于JavaScript实现单链表过程解析的文章就介绍到这了,更多相关JavaScript实现单链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

--结束END--

本文标题: JavaScript实现单链表过程解析

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

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

猜你喜欢
  • JavaScript实现单链表过程解析
    前言： 要存储多个元素，数组是最常用的数据结构，但是数组也有很多缺点： 数组的创建通常要申请一段连续的内存空间，并且大小是固定的，所以当当前数组不能满足容量需求时，需要进行扩容，（一...
    99+
    2024-04-02
  • JavaScript实现双向链表过程解析
    目录一、什么是双向链表二、双向链表的封装三、双向链表的常用操作1、append（element)方法-----向列表尾部添加一个项2、将链表转化为字符串形式3、insert(posi...
    99+
    2024-04-02
  • JavaScript表单验证实现过程详解
    目录一. 作用二. 需求三. 实现一. 作用 如果没有表单验证，错误的数据就会发往服务端，会造成服务端压力过大； 所以在前端对数据进行过滤，以减轻服务端压力； 二. 需求 1. 当输...
    99+
    2023-01-30
    JavaScript表单验证 JS表单验证
  • Node.js环境下JavaScript实现单链表与双链表结构
    单链表（LinkedList）的javascript实现 npmjs相关库： complex-list、smart-list、singly-linked-list 编程思路： add方法用于将元素追加...
    99+
    2022-06-04
    链表 结构 环境
  • Linux内核链表实现过程
    关于双链表实现，一般教科书上定义一个双向链表节点的方法如下： struct list_node{stuct list_node *pre;stuct list_node *next;ElemType dat...
    99+
    2022-06-04
    内核 链表 过程
  • python 实现线性链表（单链表）
    初学python，拿数据结构中的线性链表存储结构练练手，理论比较简单，直接上代码。 #!/usr/bin/python # -*- coding:utf-8 -*- # Author: Hui # Date: 2017-10-13...
    99+
    2023-01-31
    链表 线性 python
  • python实现单链表
    #encoding:utf-8 import sys class Lnode():     def __init__(self,elem,next=None):         self.elem = elem    #节点的值   ...
    99+
    2023-01-31
    链表 python
  • C++详解如何实现单链表
    目录单链表单链表的基本操作1.初始化2.取值3.查找4.插入5.删除示例代码开发环境运行结果单链表 链表内存空间不一定连续，其扩展性较好。多余的不多说了。该文主要记录单链表的实现，该...
    99+
    2024-04-02
  • C++数组模拟之单链表与双链表和栈和队列的实现过程
    目录前引一、数组模拟实现单链表1.1 数组模拟的单链表解析1.2 数组模拟实现单链表例题二、数组模拟实现双链表2.1 数组模拟实现双链表解析2.2 数组模拟实现双链表例题三、数组模拟...
    99+
    2023-02-13
    C++数组模拟单链表 C++数组模拟双链表 C++数组模拟队列
  • Python实现单向链表
    单向链表每个节点都是由两部分组成：数据字段和指针，指针指向下一个元素在内存中的位置。 单向链表的第一个节点节点是链表头指针，而最后一个节点的指针设为None，不指向任何元素。（链表头...
    99+
    2024-04-02
  • python单链表的实现
    ''' 当加入第一个node节点的时候,会有几个值,(这里的self.tail.next 其实就是node.next) head = item = tail = Node(object element1 memory) item = hea...
    99+
    2023-01-31
    链表 python
  • Go语言编程指南：单链表实现详解
    Go语言编程指南：单链表实现详解 在Go语言中，单链表是一种常见的数据结构，用于存储一系列元素并按顺序访问。本文将详细介绍单链表的实现原理，并给出具体的Go语言代码示例。 单链表的定义...
    99+
    2024-04-02
  • golang实现简单rpc调用过程解析
    目录基本概念RPC通信过程RPC 具体实现server端客户端基本概念 RPC（Remote Procedure Call）远程过程调用，简单的理解是一个节点请求另一个节点提供的服务...
    99+
    2024-04-02
  • Python单链表简单实现代码
    本文实例讲述了Python单链表简单实现代码。分享给大家供大家参考，具体如下： 用Python模拟一下单链表，比较简单，初学者可以参考参考 #coding:utf-8 class Node(object...
    99+
    2022-06-04
    链表 代码 简单
  • C++如何实现单链表
    小编给大家分享一下C++如何实现单链表，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！单链表的实现(从入门到熟练)概念和结构概念：链表是一种物理存储结构上非连续、非...
    99+
    2023-06-29
  • C++怎么实现单链表
    本文小编为大家详细介绍“C++怎么实现单链表”，内容详细，步骤清晰，细节处理妥当，希望这篇“C++怎么实现单链表”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。单链表链表内存空间不一定连续，其扩展性较好。多余的不多...
    99+
    2023-07-02
  • php如何实现单链表
    本文将为大家详细介绍“php如何实现单链表”，内容步骤清晰详细，细节处理妥当，而小编每天都会更新不同的知识点，希望这篇“php如何实现单链表”能够给你意想不到的收获，请大家跟着小编的思路慢慢深入，具体内容如下，一起去收获新知识吧。php实现...
    99+
    2023-06-06
  • Golang如何实现单链表
    今天小编给大家分享一下Golang如何实现单链表的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。1. 定义节点// ...
    99+
    2023-07-05
  • JavaScript数据结构之单链表和循环链表的示例分析
    这篇文章将为大家详细讲解有关JavaScript数据结构之单链表和循环链表的示例分析，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。链表是一种物理存储单元上非线性、非连续性...
    99+
    2024-04-02
  • python如何实现单向链表及单向链表的反转
    链表的定义 链表中的每个节点会存储相邻节点的位置信息，单链表中的每个节点只存储下一关节点的位置信息 单向链表的实现 class ListNode: def __init_...
    99+
    2024-04-02
软考高级职称资格查询
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作