JavaScript实现链表

fxp 发布于2019-08-23 15:41 / 1878人阅读

摘要：什么是链表链表是一个集合，是或中的概念。向链表中插入一个值，不需要把后面的每个元素往后移动位置。因为在中不能像一样那样直接操作指针，所以现在用数组模拟一个链表。

什么是链表

链表是一个集合，是C或C++中的概念。和数组有什么区别呢？
链表每个元素有两部分组成，第一部分是存储的值，第二部分是记录了下一个元素的位置信息。在C中即使下一个元素的指针，其实就通过第二个属性能直接拿到下一个元素的值。

{
value:"",
next:1
}

一个元素通过他的next就知道下一个值是什么。就像一个链子，上一个元素连着下一个元素。
向链表中插入一个值，不需要把后面的每个元素往后移动位置。
1.只需要把修改插入位置前一个元素的next属性只想插入的值；
2.插入的值的next只插入之后的那个元素即可。
因为在JavaScript中不能像C一样那样直接操作指针，所以现在用数组模拟一个链表。

javascript版本的链表

//比如有一个集合
let left = [2, 3, 4, 5, 8, 9];
//用另一个集合对应位置的值来记录下一个元素的索引。每个值存储的是需要获取值的索引，如果没有对应的则存-1；
//这个集合的奥妙在于，它的**索引**和**值**是能串联起来的“一条绳”,索引和值前后衔接。
// [1, 2, 3, 4, 5, -1]
//  0  1  2  3  4   5
let right = [1, 2, 3, 4, 5, -1];
//一个要插入的值
let middle = 6;
let len = left.length;
left.push(middle);
let t = 0;
while (t != -1) {
  if (left[right[t]] > middle) {
    right[len] = right[t];
    right[t] = len;
    break;
  }
  t = right[t];
}

console.log("输出结果：");
console.log(left);
console.log(right);
t = 0;
while (t != -1) {
  console.log(left[t]);
  //这就体现出了索引和值前后衔接的关系了。注意right的索引用的也是t
  t = right[t];
}

结果

2 3 4 5 6 8 9

分析

原始：

[2, 3, 4, 5, 8, 9];
[1, 2, 3, 4, 5, -1]

插入后：
所谓的插入是保证输出的顺序像插入的效果。

[2, 3, 4, 5, 8, 9, 6];
[1, 2, 3, 6, 5, -1, 4]

GPU云服务器云服务器多链表c语言实现 java实现链表插入遍历c语言实现链表用链表实现队列c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/102428.html

学习JavaScript数据结构与算法（二）：链表

摘要：实现移除给定的元素要移除的元素返回值表示移除成功方法说明移除单向链表中某个位置的元素。的前端乐园原文链接寒假前端学习学习数据结构与算法二链表本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第四篇文章：学习JavaScript数据结构与...

lolomaco 2019-08-22 11:00 评论0 收藏0
用 JavaScript 实现链表操作 - 06 Insert Sort

摘要：需求实现一个函数对链表进行升序排列插入排序。关于插入排序插入排序的介绍可以看，大体逻辑为建立一个新的空链表。遍历完成，返回新链表。代码如下总结因为有上个的函数的帮助，这个插入排序实现起来非常简单。 TL;DR 2016 年末最后一篇，对链表进行插入排序。系列目录见前言和目录。需求实现一个 insertSort() 函数对链表进行升序排列（插入排序）。实现过程中可以使用上一个 ...

doodlewind 2019-08-21 11:28 评论0 收藏0
JavaScript 数据结构与算法之美 - 线性表（数组、栈、队列、链表）

摘要：每个线性表上的数据最多只有前和后两个方向。数组链表队列栈等就是线性表结构。非线性表数据之间并不是简单的前后关系。不包含任何元素的栈称为空栈。移除栈顶的元素，同时返回被移除的元素。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言基础知识就像是一座大楼的地基，它决定了我们的技术高度。我们应该多掌握一些可移值的...

kaka 2019-08-23 18:25 评论0 收藏0
用 JavaScript 实现链表操作 - 13 Shuffle Merge

摘要：需求实现函数把两个链表合并成一个。新链表的节点是交叉从两个链表中取的。通过行的调换指针，我们可以保证下一次循环就是对另一个链表进行操作了。这样一直遍历到两个链表末尾，返回结束。参考资料的代码实现的测试 TL;DR 把两个链表洗牌合并成一个，系列目录见前言和目录。需求实现函数 shuffleMerge() 把两个链表合并成一个。新链表的节点是交叉从两个链表中取的。这叫洗牌合并。举...

shiguibiao 2019-08-20 14:21 评论0 收藏0
JavaScript数据结构04 - 链表

摘要：类表示要加入链表的项。循环链表和普通链表之间唯一的区别在于，最后一个元素指向下一个元素的指针不是引用，而是指向第一个元素。这里就不进行代码实现了，大家可以结合上面的单向链表和双向链表自己实现一个循环链表。一、定义 1.1 概念前面我们学习了数组这种数据结构。数组（或者也可以称为列表）是一种非常简单的存储数据序列的数据结构。在这一节，我们要学习如何实现和使用链表这种动态的数据结构，这...

cheukyin 2019-08-23 10:39 评论0 收藏0
用 JavaScript 实现链表操作 - 11 Alternating Split

摘要：需求实现一个函数，把一个链表切分成两个。子链表的节点应该是在父链表中交替出现的。所以整个算法的解法就能很容易地用表示。唯一需要考虑的就是在每个循环体中判断节点该插入哪个链表。也有人使用持续增长的配合取余来做，比如。 TL;DR 把一个链表交替切分成两个，系列目录见前言和目录。需求实现一个 alternatingSplit() 函数，把一个链表切分成两个。子链表的节点应该是在父链...

jsyzchen 2019-08-20 14:02 评论0 收藏0