数据结构与算法－单向链表(js实现)

　　链表有单向链表、双向链表和循环链表，此篇文章只讲解单向链表，另外两种会在下一篇文章中补充，要真正理解和使用链表的话，建议三种链表结构都了解一下。

　　平时我们使用最多的数据结构应该是数组，很多东西都可以用数组来轻松实现，但在某些编程语言中，数组的长度是预先设定好的，想要额外添加元素或者删除元素是一件比较困难的事。那么使用链表的话恰恰就解决了这些问题，对于链表来说删除或添加一个元素是非常方便的，除了数据的随机访问(可以实现但是比较麻烦，比如可以通过添加和操作索引值来实现)，它几乎可以用在任何可以使用一维数组的情况中。

链表的定义

　　链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一

个节点的引用叫做链。

　　一般的链表都会额外添加一个头节点(作为辅助)和尾节点，例如下面这种样子

　　数组元素靠它们的位置进行引用,链表元素则是靠相互之间的关系进行引用。在上图中,我们说 bread 跟在 milk 后面,而不说 bread 是链表中的第二个元素。遍历链表,就是跟着链接,从链表的首元素一直走到尾元(但这不包含链表的头节点,头节点常常用来作为链表的接入点)。上图中另外一个值得注意的地方是,链表的尾元素指向一个 null 节点。

　　插入新元素：

　　向单向链表中插入一个节点,只需要修改它前面的节点(前驱),使其指向新加入的节点,而新加入的节点则指向原来前驱指向的节点。上图演示了如何在 eggs 后加入 cookies。

　　删除链表中已有元素：

　　从链表中删除一个元素也很简单。只需要将待删除元素的前驱节点指向待删除元素的后继节点。上图展示了从单向链表中删除Bacon。

　　除了插入和删除，链表还有其他一些操作，后面将给出讲解。

设计一个基于对象的链表

　　我们需要设计两个类，Node 类用来表示节点, LinkedList 类提供插入节点、删除节点、显示列表元素的方法,以及其他一些辅助方法。

　　Node类：　　

function Node(element) {
　　this.element = element;//当前节点的数据
　　this.next = null;//下一个节点数据
}

 　　LinkedList 类：

function LList() {  
   this.head = new Node("head");//头节点
}  
LList.prototype={  
 //查找某一节点
 find:function (item) {  
   var currNode = this.head;  
   while (currNode.element != item) {  
      currNode = currNode.next;  
   }  
   return currNode;  
 },  
 //向某一元素后面插入新节点
 insert:function(newElement,item){  
   var newNode = new Node(newElement);  
   var current = this.find(item);  
   newNode.next = current.next;  
   current.next = newNode;  
 },  
 //查找某一节点的前一个节点(前驱)
 findPrevious:function(item){  
   var currNode = this.head;  
   while (!(currNode.next == null) &&(currNode.next.element != item)) {  
      currNode = currNode.next;  
   }  
   return currNode;  
 },  
 //删除某一个节点
 remove:function(item){  
   var prevNode = this.findPrevious(item);  
   if (!(prevNode.next == null)) {  
      prevNode.next = prevNode.next.next;  
   }  
 },
 //修改某一节点的数据
 edit:function(item,newItem){
     var element=this.find(item);
     element.element=newItem;
 },  
 //在控制台打印出所有节点(为了方便预览)
 display:function(){  
   var currNode = this.head;  
   while (!(currNode.next == null)) {  
      console.log(currNode.next.element);  
      currNode = currNode.next;  
   }  
 }  
}

 　测试：

var names = new LList();
names.insert("likek", "head");//往头节点后插入节点likek
names.insert("zhangsan", "likek");//往likek后插入节点zhangsan
names.insert("lisi", "zhangsan");//往zhangsan后插入节点lisi
names.insert("wangwu", "lisi");//往lisi后插入节点wangwu
names.display();
/*likek
 zhangsan
 lisi
 wangwu*/
names.remove("zhangsan");//删除zhangsan节点
names.display();
/*likek
 lisi
 wangwu*/
names.edit("lisi","wangnima");//将lisi节点改为wangnima
names.display();
/*likek
 wangnima
 wangwu*/