javascript实现链表结构

链表结构的原理图：

链表是由一组节点组成的集合，每个节点都是使用一个对象的引用指向他的后继节点；最后一个节点指向空对象null；为了更好的标示链表的起点，在第一个节点之前添加了一个头节点；

插入节点的原理图

链表中插入一个节点的效率很高，向链表中插入一个节点，需要修改它前面那个节点（前驱节点），让它指向新加入的节点，然后让新加入的节点指向前驱节点以前指向的节点；

删除节点的原理图

和插入节点一样也是改变指向：

js面向对象方式实现链表结构

一、构建Node类：

node类包含两个属性：

element用来保存节点上的数据next用来保存指向下一个节点的链接，使用构造函数构建Node类，以便于用new操作符创建一个新的节点实例： //构建Node类 function Node(element){ this.element = element; this.next = null; }

二、构建LinkedList类

使用构造函数和原型混合模式，定义header属性，是头节点的引用； 利用原型模式，为所有实例定义insert，findNode等方法；

function LinkedList(){ this.header = new Node("header"); }

三、findNode方法

每个链表LinkedList实例都拥有这个方法，这个方法的目的找出某个链表LinkedList实例中包含内容element的节点，接受的参数为element,返回节点；

findNode: function(ele){ var curNode = this.header; while (curNode){ if (curNode.element == ele){ // console.log(curNode); return curNode; break; } else { curNode = curNode.next; } } }

四、插入节点insert(preEle, ele)方法；

这个方法接收两个参数节点内容preEle和节点内容ele，表示将节点内容ele插入到链表中内容为preEle的节点；

insert: function(preEle, ele){ var newNode = new Node(ele); var preNode = this.findNode(preEle); var nextNode = preNode.next; preNode.next = newNode; newNode.next = nextNode; }

五、显示所有节点内容

showAllEle: function(){ var elements = []; var curNode = this.header; while(curNode){ if (curNode.element){ elements.push(curNode.element); } curNode = curNode.next; } return elements; }

六、移除某个节点remove（ele）；

将内容为ele的节点移除

remove: function(ele){ var toRemoveNode = this.findNode(ele); var curNode = this.header; while(curNode){ if (curNode.next == toRemoveNode){ var preNode = curNode; break; } else { curNode = curNode.next; } } //将前驱节点next指向，要删除的toRemoveNode节点next指向的节点； preNode.next = toRemoveNode.next; toRemoveNode = null; }

七、清空链表empty（）

empty: function(){ this.header.next = null; }

八、实例演示所构造的链表 首先new一个新的链表，插入几个值：

var list = new LinkedList(); list.insert("header", "a"); list.insert("a", "b"); list.insert("b", "c"); list.insert("c", "d"); list.insert("d", "e");

打印list：console.log(list),在浏览器调试工具的结果如下图，这张图很直观的展示了链表结构特点，环环相扣； 在b的后面插入一个值：list.insert("b", "插入的值"); 打印list：console.log(list),在浏览器调试工具的结果如下图 移除c再打印

list.remove('c'); console.log(list);

最后清空链表list.empty();

双向链表的实现

在单向链表中，移除节点的时候，需要寻找移除节点的前驱节点，这个寻找过程又进行了一次遍历，遍历的过程是十分浪费资源的， 如果移除节点有个provious属性来指向前驱节点，这样的话，省略了遍历查找过程，听起来是不是很有趣啊？ 接下来思考如果把单向链表改成双向链表呢？

一、更改构造函数Node，添加previous属性

function Node(element){ this.element = element； this.next = null; this.previous = null; }

二、更改insert方法

insert: function(preEle, ele){ var newNode = new Node(ele); var preNode = this.findNode(preEle); var nextNode = preNode.next; preNode.next = newNode; newNode.next = nextNode; newNode.previous = preNode; nextNode.previous = newNode; }

三、更改remove方法：

remove: function(ele){ var toRemoveNode = this.findNode(ele); var previousNode = toRemoveNode.previous; var nextNode = toRemoveNode.next; //将前驱节点next指向，要删除的toRemoveNode节点next指向的节点； nextNode.previous = previousNode; preNode.next = toRemoveNode.next; toRemoveNode = null; }