JavaScript数据结构链表知识详解

最近在看《javascript数据结构和算法》这本书,补一下数据结构和算法部分的知识,觉得自己这块是短板。

链表:存储有序的元素集合,但不同于数组,链表中的元素在内存中不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。

好处:可以添加或移除任意项,它会按需扩容,且不需要移动其他元素。

与数组的区别:

数组:可以直接访问任何位置的任何元素;

链表:想要访问链表中的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。

做点小笔记。

function LinkedList(){
var Node = function(element){
this.element = element
this.next = null
}
var length = 0
var head = null
this.append = function(element){
var node = new Node(element)
var current
if(head == null){ //链表为空
head = node
}else{ //链表不为空
current = head
//循环链表,直到最后一项
while(current.next){
current = current.next
}
current.next = node
}
length ++ //更新链表长度
}
this.insert = function(position,element){
var node = new Node(element)
var current = head
var previous
var index = 0
if(position>=1 && position<=length){ //判断是否越界
if(position === 0){ //插入首部
node.next = current
head = node
}else{
while(index++ < position){
previous = current
current = current.next
}
node.next = current
previous.next = node
}
length ++ //更新链表长度
return true
}else{
return false
}
}
this.indexOf = function(element){
var current = head
var index = -1
while(current){
if (element === current.element) {
return index
}
index++
current = current.next
}
return -1
}
this.removeAt = function(position){
if(position>-1 && position<length){ //判断是否越界
var current = head
var previous
var index = 0
if(position === 0){ //移除第一个元素
head = current.next
}else{
while(index++ < position){
previous = current
current = current.next
}
previous.next = current.next //移除元素
}
length -- //更新长度
return current.element
}else{
return null
}
}
this.remove = function(element){
var index = this.indexOf(element)
return this.removeAt(index)
}
this.isEmpty = function(){
return length == 0
}
this.size = function(){
return length
}
this.toString = function(){
var current = head
var string = ""
while(current){
string = "," + current.element
current = current.next
}
return string.slice(1)
}
this.getHead = function(){
return head
}
}

以上所述是小编给大家介绍的JavaScript数据结构链表知识详解,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!

(0)

相关推荐

  • javascript写的一个链表实现代码

    本来要用Array来保存数据的,没试过用JS来数据结构,就用JS来试试吧. JS效率真的很低一个链表装1000个对象浏览器就提示运行缓慢了. 之前觉得AJAX3D挺用前景的,现在看来还没有流行就要夭折了.用delphi开发的游戏人们都觉得太慢了,何况用JS. 下面是我实现的一个链表: 复制代码 代码如下: /*@author eric *@mail shmilyhe@163.com *blog.csdn.net/shmilyhe */ <script> function Student(no,

  • js单向链表的具体实现实例

    复制代码 代码如下: function linkNode(_key, _value){    /// <summary>    /// 链表类的节点类    /// </summary>    this.Key = _key;    this.Value = _value;    this.next = null;}function Link(){    /// <summary>    /// 创建一个链表类    /// </summary>    th

  • JavaScript实现的链表数据结构实例

    此例是javascript来建立链表.. 并对此进行了排序.. 还可以在GenericList一般链表上进行扩展. 实现各种排序及增,删,改结点.. 复制代码 代码如下: function Node(){   this.data=null;   this.next=null; } function GenericList(){   this.head=null;   this.current=null;   //打出所有的链表结点   this.print= function(){   this

  • js链表操作(实例讲解)

    如下所示: <!doctype html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</title> <script> function Node(v){ this.value=v; this.next=null; } function ArrayList(){ this.head=new Node(

  • 深入理解链表的各类操作详解

    链表概述链表是一种常见的重要的数据结构.它是动态地进行存储分配的一种结构.它可以根据需要开辟内存单元.链表有一个"头指针"变量,以head表示,它存放一个地址.该地址指向一个元素.链表中每一个元素称为"结点",每个结点都应包括两个部分:一为用户需要用的实际数据,二为下一个结点的地址.因此,head指向第一个元素:第一个元素又指向第二个元素:--,直到最后一个元素,该元素不再指向其它元素,它称为"表尾",它的地址部分放一个"NULL&qu

  • JavaScript数据结构链表知识详解

    最近在看<javascript数据结构和算法>这本书,补一下数据结构和算法部分的知识,觉得自己这块是短板. 链表:存储有序的元素集合,但不同于数组,链表中的元素在内存中不是连续放置的.每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成. 好处:可以添加或移除任意项,它会按需扩容,且不需要移动其他元素. 与数组的区别: 数组:可以直接访问任何位置的任何元素: 链表:想要访问链表中的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素. 做点小笔记. funct

  • JavaScript数据类型相关知识详解

    一.字面量 用于表达一个固定值的表示法,又叫做常量. 1.1 数字字面量 <script> // 整数字面量 // 十进制 console.log(12); // 八进制 console.log(010); // 十六进制 console.log(0x100); </script 效果展示 1.2 浮点数字面量 浮点数不区分进制,所有的浮点数都是十进制下的(注意:浮点数若是0~1之间的,前面的0可以省略不写,例如0.6可以写成.6)浮点数的精度远远不如小数. // 浮点数字面量 cons

  • JavaScript中最容易混淆的作用域、提升、闭包知识详解(推荐)

    一.函数作用域 1.函数作用域 就是作用域在一个"Function"里,属于这个函数的全部变量都可以在整个函数的范围内使用及复用. function foo(a) { var b = 2; function bar() { // ... } var c = 3; } bar(); // 失败 console.log( a, b, c ); // 三个全都失败 上面的"foo"函数内的几个标识符,放到函数外面访问就都会报错. 2.立即执行函数表达式 在任意代码片段外部

  • C语言数据结构之单链表存储详解

    目录 1.定义一个链表结点 2.初始化单链表 3.输出链表数据 4.完整代码 如果说,顺序表的所占用的内存空间是连续的,那么链表则是随机分配的不连续的,那么为了使随机分散的内存空间串联在一起形成一种前后相连的关系,指针则起到了关键性作用. 单链表的基本结构: 头指针:永远指向链表第一个节点的位置. 头结点:不存任何数据的空节点,通常作为链表的第一个节点.对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题. 首元结点:首个带有元素的结点. 其他结点:链表中其他的节点. 1.定义一

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

    目录 1.插入操作 2.删除操作 3.查找操作 4.修改操作 5.完整代码 1.插入操作 (1)创建一个新的要插入的结点 (2)将新结点的 next 指针指向插入位置后的结点 (3)将插入位置前的节点指针 next 指向新的结点 注意:步骤(2)(3)的顺序不能颠倒,否则会导致插入位置后的部分链表丢失. 插入位置一共分三种,分别是头部插入.中间插入和尾部插入. 如图: 代码: link* insertElem(link* p,int elem,int pos){ link* temp = p;/

  • JavaScript字典与集合详解

    目录 字典 什么是字典 JavaScript中的字典 字典的应用 集合 什么是集合 JS中的集合 集合中的操作 交集.并集.差集的封装 字典 什么是字典 说到字典,第一时间想到的应该就是新华字典,实际上,这跟编程中的字典类似,两者都有一个特点,就是一一对应(yi yi dui ying),或者说是映射. 字典通常以**[键,值]** 对的形成存储,因为是以键值对的形式存储,更方便通过key来获取value 比如存储用户信息: { 'username': '一碗周', 'age': 18 } Ja

  • 基于JavaScript表单脚本(详解)

    什么是表单? 一个表单有三个基本组成部分: 表单标签:这里面包含了处理表单数据所用CGI程序的URL以及数据提交到服务器的方法. 表单域:包含了文本框.密码框.隐藏域.多行文本框.复选框.单选框.下拉选择框和文件上传框等. 表单按钮:包括提交按钮.复位按钮和一般按钮:用于将数据传送到服务器上的CGI脚本或者取消输入,还可以用表单按钮来控制其他定义了处理脚本的处理工作. JavaScript与表单间的关系:JS最初的应用就是用于分担服务器处理表单的责任,打破依赖服务器的局面,尽管目前web和jav

  • Java语言实现数据结构栈代码详解

    近来复习数据结构,自己动手实现了栈.栈是一种限制插入和删除只能在一个位置上的表.最基本的操作是进栈和出栈,因此,又被叫作"先进后出"表. 首先了解下栈的概念: 栈是限定仅在表头进行插入和删除操作的线性表.有时又叫LIFO(后进先出表).要搞清楚这个概念,首先要明白"栈"原来的意思,如此才能把握本质. "栈"者,存储货物或供旅客住宿的地方,可引申为仓库.中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈.出栈的说法. 实现方式是

  • redis中的数据结构和编码详解

    redis中的数据结构和编码:     背景: 1>redis在内部使用redisObject结构体来定义存储的值对象. 2>每种类型都有至少两种内部编码,Redis会根据当前值的类型和长度来决定使用哪种编码实现. 3>编码类型转换在Redis写入数据时自动完成,这个转换过程是不可逆的,转换规则只能从小内存编码向大内存编码转换.     源码: 值对象redisObject: typedef struct redisObject {                 unsigned ty

  • Redis数组和链表深入详解

    1.数组和链表基础知识 数组: 数组会在内存中开辟一块连续的空间存储数据,这种存储方式有利也有弊端.当获取数据的时候,直接通过下标值就可以获取到对应的元素,时间复杂度为O(1).但是如果新增或者删除数据会移动大量的数据,时间复杂度为O(n).数组的扩容机制是:如果数组空间不足,会先开辟一块新的空间地址,将原来的数组复制到新的数组中. 链表: 链表不需要开辟连续的内存空间,其通过指针将所有的数据连接起来.新增或者删除的时候只需要将指针指向的地址修改就行了,时间复杂度为O(1).但是查询的时间复杂度

随机推荐

其他