1.实验准备
- 熟悉JavaScript语法；
- 查看JavaScript教程：
https://www.liaoxuefeng.com/wiki/001434446689867b27157e896e74d51a89c25cc8b43bdb3000
安装和运行：http://nodejs.cn/ 下载nodejs
2.实验内容
- 生成1000个1-10000的数字，插入到链表中。 利用filter函数过滤掉那些少于2000的数字。
- 制作一个链表list，实现链表的加入，删除，查询等操作。同时把该数据保存为json格式的文件；并能从文件读取到内存中；
3.实验环境
- 所有的代码存放在js文件中，并通过node.js来运行。
- 安装和运行：http://nodejs.cn/ 下载node.js。
4.实验步骤
1、链表的基本概念
首先，要实现链表，我们先搞懂一些链表的基本东西，因为这很重要！
链表定义
在链表中有一个头指针变量，图中head表示的就是头指针，这个指针变量保存一个地址。从图中的箭头可以看到该地址为一个变量的地址，也就是说头指针指向一个变量。这个变量称为元素，在链表中每一个元素包括两个部分：数据部分和指针部分。数据部分用来存放元素所包含的数据，而指针部分用来指向下一个元素。最后一个元素指针指向NULL，表示指向的地址为空。从图1可以看到，head头结点指向第一个元素，第一个元素中的指针又指向第二个元素，第二个元素的指针又指向第三个元素的地址，第三个元素的指针就指向为空。
插入结点
向链表中插入一个节点的效率很高，需要修改它前面的节点(前驱)，使其指向新加入的节点，而将新节点指向原来前驱节点指向的节点即可。下面我将用图片演示如何在 data2 节点 后面插入 data4 节点。
删除结点
同样，从链表中删除一个节点，也很简单。只需将待删节点的前驱节点指向待删节点的，同时将待删节点指向null，那么节点就删除成功了。下面我们用图片演示如何从链表中删除 data4 节点。
2、JavaScript实现链表
1、Node类
Node类包含两个属性： element 用来保存节点上的数据，next 用来保存指向下一个节点的链接。
function Node(element) {
this.element = element; //element用来保存结点上的数据
this.next = null; //指向下一个节点的链接
}
2、LinkedList类
LinkedList类提供了对链表进行操作的方法，包括插入删除节点，查找给定的值等。
function LinkedList() {
this.head = new Node('head');//头节点
this.find = find; //在列表中查找给定的值
this.findout = findout; //查找给定值
this.insert = insert; //插入节点
this.show = show;//显示链表
this.remove = remove; // 删除节点
this.findPrevious = findPrevious;//找到前一节点
}
3、find：查找给定节点
find 方法同时展示了如何在链表上移动。首先，创建一个新节点，将链表的头节点赋给这个新创建的节点，然后在链表上循环，如果当前节点的 element 属性和我们要找的信息不符，就将当前节点移动到下一个节点，如果查找成功，该方法返回包含该数据的节点；否则，就会返回null。
function find(item) {
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;//从当前节点移动到下一个节点
}
return currNode;
}
4、insert：插入新节点
一旦找到了节点，我们就可以将新的节点插入到链表中了，将新节点的 next 属性设置为后面节点的 next 属性对应的值，然后设置后面节点的 next 属性指向新的节点，
function insert(newElement, item) {
var newNode = new Node(newElement); //创建结点
var currentNode = this.find(item); //找到目标结点
newNode.next = currentNode.next; //修改目标结点的next指向链接
currentNode.next = newNode; //将目标结点的next值赋给要插入的结点的next
}
5、findout：查找给定值
从头节点出发，依次查找，和find类似，只不过有输出位置。
function findout(item) { //查找给定的值的位置
var i = 0;
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;
i++;
}
console.log(currNode.element, "位于第", i, "个");
return currNode;
}
6、findPrevious：找到待删除节点的前驱
为了删除想要的那个节点，我们定义一个 findPrevious 方法遍历链表，检查每一个节点的下一个节点是否存储待删除的数据。如果找到，返回该节点，这样就可以修改它的 next 属性了
function findPrevious(item) {//找到要删除的结点的前一个结点
var currentNode = this.head;
while (!(currentNode.next == null) &&
(currentNode.next.element != item)) {
currNode = currentNode.next;
}
return currNode;
}
7、remove:删除节点
从链表中删除节点时，我们先要找个待删除节点的前一个节点，找到后，我们修改它的 next 属性，使其不在指向待删除的节点，而是待删除节点的下一个节点。
function remove(item) {
var prevNode = this.findPrevious(item);
//找到要删除结点的前一个结点
if (!(prevNode.next == null)) {//若不为空
prevNode.next = prevNode.next.next;//删去
}
}
8、show:打印显示列表
将头节点赋给一个新的变量，然后循环链表，直到当前节点的 next 属性为 null 时停止循环，我们循环过程中将每个节点的数据打印出来就好了。
function show() {
var currentNode = this.head; //从头结点开始
while (!(currentNode.next == null)) { //若结点不为空
console.log(currentNode.next.element); //则输出
currentNode = currentNode.next;
}
}
3、主程序中生成1000个随机数并过滤
首先我们定义一个链表numes一个生成1-10000之间的随机数数组a，因为是生成[1,10000]的随机数，所以我们用Math.floor(Math.random()*max)+1来进行计算。
var numes = new LinkedList();
var a = new Array();
for (var i = 0; i < 1000; i++) {
a[i] = Math.floor(Math.random() * (10000)) + 1;
}
接着我们用filter函数来过滤掉小于2000的那些数字，并用a_f数组来存储过滤完成新生成的数组
var a_f = a.filter(function (x)
{ return x >= 2000 })
最后用我们将a_f数组总的元素插入到定义的列表numes里，并显示出来：
numes.insert(a_f[0], 'head');
for (var i = 1; i < a_f.length; i++)
numes.insert(a_f[i], a_f[i - 1]);
numes.show();
运行结果：
4、js与json的转换
1、json了解
JSON是JavaScript Object Notation的缩写，它是一种数据交换格式。
在JavaScript中，我们可以直接使用JSON，因为JavaScript内置了JSON的解析。把任何JavaScript对象变成JSON，就是把这个对象序列化成一个JSON格式的字符串，这样才能够通过网络传递给其他计算机。
如果我们收到一个JSON格式的字符串，只需要把它反序列化成一个JavaScript对象，就可以在JavaScript中直接使用这个对象了。
2、把数据保存为.json格式的文件
var fs=require('fs');//创建文件
var path=require('path');//系统路径模块
//把data对象转换为json格式字符串
var content=JSON.stringify(names);
//指定创建目录及文件名称，__dirname为执行当前js文件的目录
var file=path.join(__dirname,'list.json');
console.log("写入文件：");
fs.writeFile(file,content,
function(err)
{
if(err)
{
return console.log(err);
}
console.log('文件创建成功，地址：'+file);
}
);
运行结果：
同时在和list.js文件同一目录下会自动生成list.json文件：
3、读取文件
fs.readFile(path.join(__dirname,'list.json'),{encoding:'utf-8'},function (err,bytesRead) {
console.log("读取文件：");
if(err) throw err;
console.log("读取文件_js对象：");
console.log(JSON.parse(bytesRead));
console.log("读取文件_json格式：");
console.log(JSON.stringify(JSON.parse(bytesRead)));
console.log("ReadFile Success");
}
运行结果：
5.实验心得
本次实验在JavaScript的基础上实现了链表的基本操作，JavaScript实际上并不是很难，基本逻辑语句都比较好掌握，只要对链表的基本操作没有问题，这一部分的实现就比较容易；而js和json之间的转换在参考官网上的教程后同样也能够基本实现。
