用JavaScript实现基于对象的单项链表
单向链表介绍
何为单向链表
与数组的索引: 值（可以直接在数组层面对值进行修改）不同，链表各个值的关系偏向去中心化。
见上图，每个节点可分为两部分：1. 节点的值；2. 下一个节点的指向，即下一个节点是谁。例如：上图链表中的第一个节点，它的值是milk，它的下一个节点是值为Bread的节点。
单向链表优点
当我们需要组织数据时，数组不总是最佳的数据结构（对于大多数编程语言而言），缘于它有两个显著的缺点：1. 数组的长度是固定的，当数组已被数据填满时，加入新数据会显得很麻烦；2. 当我们插入、或删除数组中的某个值时，需要把数组中的其它值向后、或向前移动，以反映数组被进行了增删操作。
所以当我们需要频繁的对数据进行增删操作时，选择数组不是那么地明智，这时我们可以使用链表来实现对数据的增删功能。链表的增删会方便很多，当增加数据时，只需要更改它的节点指向和上一级节点的节点指向；当删除数据时，只需把待删除节点的节点指向赋给上一级节点即可，此时待删除节点便在链表中消失了（因为无法通过节点与节点的关系再找到它，便可视为消失了）。
例如：如果我们在milk和bread中增加sandwich数据，只需把milk的节点指向改为sandwich，把指向bread的节点指向赋给sandwich即可；当需要删除sandwich时，只需把指向bread的节点指向赋给milk即可，此时sandwich便自动消失了。
构建链表
当我们需要组织某一类的数据时，只需先建一个相应的构造器（构造函数）即可，这个构造器应包含以下的属性和方法：头节点；增，删，查等。
节点构造器
我们可以先做头节点的构造器；
//我们可以把一个节点视为一个盒子，这个盒子被分为两部分，一部分盛放的是该节点的值，另一部分盛放的则是指向下一个节点的节点指向。function Node(element) { this.element = element; this.next = null;}链表构造器
某类数据的链表构造器
function LList() { //LList: linkedList链表 //新建值为head的节点（表头），便可一生二二生三三生万物了，下面的操作都要基于表头。 this.head = new Node("head"); //查找方法，给find一个值，便可查到相应的节点 this.find = find; //插入方法，可以实现在哪插入、插入什么数据的功能 this.insert = insert; //展示打印功能，传入想要查询的节点的元素，该节点便能被打印出来，包括的指向的下一节点 this.display = display; //如果要删除某一节点，则需要找到它的前一节点，修改它的节点指向 this.findPrevious = findPrevious; //删除方法，传入想要删除的元素，即可实现删除功能 this.remove = remove; }find()方法
find()方法展示了如何在链表上进行移动。首先，新创一个节点，并将表头赋给这个新创的节点。然后在链表上进行循环，如果如果当前节点的element属性和我们要查找的值不一样，就从当前节点移到下一节点，如果查找成功，返回包含该数据的节点，失败，返回null。
function find(item) { //将表头赋给新创的节点 var currNode = this.head; //循环，如果当前节点的值与我们想要查找的值不一样，移动到下一节点。知道找到目标或移到null while (currNode.element !== item) { currNode = currNode.next; } //返回相应节点或null return currNode;}insert()方法
insert()实现插入功能，传入新节点的值newElement和待插位置item，并修改新节点和待插位置的节点指向，完成插入。
function insert(newElement, item) { var newNode = new Node(newElement); var currNode = this.find(item); newNode.next = currNode.next; currNode.next = newNode;}display()
display()显示链表中的元素
function display() { var currNOde = this.head; while (currNode !== item) { console.log(currNode.element); currNode = currNode.next; }}findPrevious()
findPrevious()查找到待删除的前一节点
function findPrevious(item) { var currNode = this.head; while ((currNode.next !== null) && (currNode.next.element !== item)) { currNode = currNode; } return currNode;}remove()方法
function remove(item) { var preNode = this.findPrevious(item); if(preNode.next !== null) { preNode.next = preNode.next.next; }}完整代码
function Node(element) { this.element = element; this.next = null;}function LList() { this.head = new Node("head"); this.find = find; this.insert = insert; this.display = display; this.findPrevious = findPrevious; this.remove = remove;}function find(item) { var currNode = this.head; while (currNode.element !== item) { currNode = currNode.next; } return currNode;}function insert(newElement, item) { var newNode = new Node(newElement); var currNode = this.find(item); newNode.next = currNode.next; currNode.next = newNode;}function display() { var currNode = this.head; while (currNode.next !== null) { console.log(currNode.next.element); currNode = currNode.next; }}function findPrevious(item) { var currNode = this.head; while ((currNode.next.element !== item) && (currNode.next !== null)) { currNode = currNode.next; } return currNode;}function remove(item) { var preNode = this.findPrevious(item); if(preNode.next !== null) { preNode.next = preNode.next.next; }}测试
向链表中写入数据
var cities = new LList();cities.insert("beijing", "head");cities.insert("shanghai", "beijing");cities.insert("guangzhou", "shanghai");cities.insert("shenzhen", "guangzhou");展示链表
cities.display();删除"shanghai"后，再次展示
cities.remove("shanghai");cities.display();删除成功！
Reference
Michael McMillan, (2014). Data Structures & Algorithms with JavaScript. Beijing: O’Reilly Media, Inc. and Posts & Telecom Press.