JavaScript实现单向链表数据结构
学习过数据结构的人都应该清楚，链表是一种动态的数据结构，这意味着我们可以从中任意添加或移除项，它会按需进行扩容。链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。下图展示了一个链表的结构：
相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。
在我们现实生活中类似于链表这种数据结构的有很多，比如手表的表链，坦克的履带，火车等。想在其中插入一节需要先断开两节之间的联系，插入之后，将新插入的和之前的两个节点分别在联系起来。
创建一个链表
在原生的js中没有链表这么一个存储结构，需要我们来进行手动创建，下面我们来创建一下链表的基本骨架：
function LinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0;
var head = null;
}在骨架中，我们需要一个Node类来作为基础节点，每一个节点都是通过new Node来实现的，length用来存储整个链表的长度，head指向链表的头。
然后我们需要实现以下链表的基本功能：
- append(element)：向列表尾部添加一个新的项
- insert(position, element)：向列表的特定位置插入一个新的项，返回最终插入的位置
- remove(element)：从列表中移除一项,移除成功返回true，如果链表中没有该元素则返回false
- indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1
- removeAt(position)：从列表的特定位置移除一项
- isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false
- size()：返回链表包含的元素个数。与数组的length属性类似
- toString()：由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值
append方法
append方法实现的是向链表的末尾添加一个元素，如果链表长度为0，则直接首元素就是该添加的元素，具体实现方式如下：
this.append = function(element){
var node = new Node(element);
var current = null;
if(head==null){
//此时链接长度为空，直接插入为首元素
head = node;
}else{
current = head;
while(current.next!=null){
//遍历查找链表，直到找到最后一个元素
current = current.next;
}
current.next = node;
}
//更新链表长度
length++;
}添加时首先要判断的是链表长度是否为空，也就是head首元素是否为null，也可以判断length是否为0。我们创建的Node类中next始终null，代表的是新创建的元素为末尾元素，其next为null，如果next不为空，则说明该值不是末尾元素，这为添加末尾元素时提供了判断依据。
insert方法
向列表的特定位置插入一个新的项，返回最终插入的位置，我们来看一下实现代码：
this.insert = function(position,element){
try{
position = parseInt(position);
if(isNaN(position)||position>length){
//position为非数字或者长度大于链表长度，则position位置为末尾插入
position = length;
}else if(position<0){
//如果小于0，则默认插入链表顶部
position = 0;
}
var node = new Node(element);
var current = head,index = 0,previous = null;
if(position==0){
node.next = current;
head = node;
}else{
while(index++<position){
previous = current;
current = previous.next;
}
node.next = current;
previous.next = node;
}
length++;
return position;
}catch(e){
console.log(e)
}
}插入方法需要检测判断一下这个position是否合法，如果是非数字或者数值大于链表长度，则默认添加到链表的尾部，如果数值小于0，则默认添加到链表的头部，然后则是创建一个节点，之后遍历链表，查找到其合适位置进行插入，最后更新链表长度，并将插入位置返回。
实现效果如图所示：
removeAt方法
从链表中特定位置移除元素和插入元素一样都需要判断position是否合法，但是该方法不能默认值，只要不合法就不能进行删除操作，以防误删数据，不存在的位置直接返回false，否则返回true，具体实现代码如下：
this.removeAt(position){
try{
position = parseInt(position);
if(isNaN(position)||position>length||position<0){
return false
}
var current = head,index = 0,previous = null;
if(length==0){
return false;
}else if(position==0){
head = current.next;
}else{
while(index++<position){
previous = current;
current = previous.next;
}
previous.next = current.next;
}
length--;
return true;
}catch(e){
console.log(e);
return false;
}
}indexOf方法
indexOf方法返回元素在列表中的索引，如果列表中没有该元素则返回-1。传入的参数是元素本身，我们需要对元素本身进行查找匹配，这里的元素有可能存储的是基本数据类型，也有可能是引用数据类型，这里我们需要进行区分。我们来看一下实现代码：
this.indexOf = function(element){
var current = head;
var index = -1;
while(current){
index++;
if(current.element instanceof Object&& JSON.stringify(current.element)==JSON.stringify(element)){
return index
}else if(!(current.element instanceof Object)&¤t.element==element){
return index;
}
current = current.next;
}
return index;
}remove方法
remove方法就很简单了，我们可以借助上面的indexOf和removeAt方法来进行实现，首先通过indexOf来获取元素位置，然后通过removeAt方法来进行删除操作，下面来看示例代码：
this.remove = function(element){
var index = this.indexOf(element);
if(index = -1){
return false;
}
return this.removeAt(index);
}isEmpty方法
这个方法很容易实现了，只需要判断他的length即可：
this.isEmpyt = function(){
return length==0
}size方法
这个方法和上面那个判断类似，只需要将length返回即可：
this.size = function(){
return length;
}