1. 实验准备
- 熟悉JavaScript语法；
- 查看JavaScript教程：
https://www.liaoxuefeng.com/wiki/001434446689867b27157e896e74d51a89c25cc8b43bdb3000
2. 实验内容
- 制作一个链表list，实现链表的加入，删除，查询等操作。同时把该数据保存为json格式的文件；并能从文件读取到内存中；
3.实验环境
- 所有的代码存放在js文件中，并通过node.js来运行。
- 安装和运行：http://nodejs.cn/ 下载node.js
4.实验解析
1、基本概念
1、链表定义
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表.png
在链表中有一个头指针变量，图中head表示的就是头指针，这个指针变量保存一个地址。从图中的箭头可以看到该地址为一个变量的地址，也就是说头指针指向一个变量。这个变量称为元素，在链表中每一个元素包括两个部分：数据部分和指针部分。数据部分用来存放元素所包含的数据，而指针部分用来指向下一个元素。最后一个元素指针指向NULL，表示指向的地址为空。从图1可以看到，head头结点指向第一个元素，第一个元素中的指针又指向第二个元素，第二个元素的指针又指向第三个元素的地址，第三个元素的指针就指向为空。
2、插入操作
链表的插入操作可以在链表的头指针位置进行（链表头插入节点过程.jpg），也可以在某个结点的位置进行，或者可以像创建结构时在链表的后面添加结点（链表尾插入节点过程.jpg）。这三种插入操作的思想都是一样的。
链表尾插入节点过程.png
链表头插入节点过程.png
3、删除操作
通过图4可以发现要删除一个结点，首先要找到这个结点的位置，例如图中的NO2结点。然后将NO1结点的指针指向NO3结点，最后将NO2结点的内存空间释放掉，这样就完成了结点的删除操作。
删除节点.png
2、Javascript代码
1、Node类用来表示节点
function Node(element) {
this.element = element;
this.next = null;//next用来保存指向下一个节点的链接
}
2、LinkedList类提供插入节点、删除节点、显示列表元素的方法
function LinkedList() {
this.head = new Node('head');
this.find = find ; //在列表中查找给定的值
this.findout = findout ; //查找给定值
this.insert = insert ; //插入节点
this.display = display;
this.remove = remove; // 删除节点
this.findPrevious = findPrevious;
}
3、遍历链表，查找给定数据
function find(item) {
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;//从当前节点移动到下一个节点
}
return currNode;
}
4、插入新节点
function insert(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
5、查找给定值
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、找到待删除节点的前驱
function findPrevious(item) {
var currNode = this.head;
while (!(currNode.next == null) && (currNode.next.element != item)) {
currNode = currNode.next;
}
return currNode;
}
7、从链表中删除节点
function remove(item) {
var prevNode = this.findPrevious(item);
if (!(prevNode.next == null)) {
prevNode.next = prevNode.next.next;
}
}
8、显示列表中的元素
function display() {
var currNode = this.head;
while (!(currNode.next == null)) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
9、主程序
var names = new LinkedList();
names.insert('Claire', 'head');
names.insert('Nancy', 'Claire');
names.insert('Joe', 'Nancy');
names.display();
console.log('--------------------------------');
console.log("在Claire后面插入Cherry后的链表：");
names.insert('Cherry' , 'Claire');
names.display();
console.log("寻找Nancy：");
names.findout('Nancy');
console.log("删除Joe之后的链表：");
names.remove('Joe');
names.display();
运行结果：
运行结果.png
3、js与json的转换
1、关于JSON
JSON是JavaScript Object Notation的缩写，它是一种数据交换格式。
- 在JSON中，一共就这么几种数据类型：
number：和JavaScript的number完全一致；
boolean：就是JavaScript的true或false；
string：就是JavaScript的string；
null：就是JavaScript的null；
array：就是JavaScript的Array表示方式——[]；
object：就是JavaScript的{ ... }表示方式。
以及上面的任意组合。
- JSON还定死了字符集必须是UTF-8，表示多语言就没有问题了。为了统一解析，JSON的字符串规定必须用双引号""，Object的键也必须用双引号""。
- 由于JSON非常简单，很快就风靡Web世界，并且成为ECMA标准。几乎所有编程语言都有解析JSON的库，而在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);
}
);
console.log("json内容：");
console.log(content);
运行结果：
写入文件.png
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");
}
运行结果：
读取文件.png
