JavaScript数据结构之链表的实现(2)

function findLast() {//查找链表的最后一个节点 var currentNode = this.head; while (currentNode.next != null) { currentNode = currentNode.next; } return currentNode; }

实现反序输出：

function showReverse() { var currentNode = this.head, result = ""; currentNode = this.findLast(); while(currentNode.front!=null){ result += currentNode.element + " "; currentNode = currentNode.front; } return result; }

测试程序：

var list = new LinkedList(); list.insert("a","head"); list.insert("b","a"); list.insert("c","b"); console.log(list); list.remove("b"); console.log(list.show()); console.log(list.showReverse());

输出：

循环链表

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即：

head.next = head

这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。楼主用下图来表示循环链表：

修改构造方法：

function LinkedList(){ this.head = new Node('head');//初始化 this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表 this.find = find; this.frontNode = frontNode; this.insert = insert; this.remove = remove; this.show = show; }

这时需要注意链表的输出方法show()与find()方法，原来的方式在循环链表里会陷入死循环，while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){ var currentNode = this.head;//从头结点开始 while(currentNode.element!=item&&currentNode.next.element!='head'){ currentNode = currentNode.next; } return currentNode;//找到返回结点数据，没找到返回null } function show(){ var currentNode = this.head,result = ""; while (currentNode.next != null && currentNode.next.element != "head") { result += currentNode.next.element + " "; currentNode = currentNode.next; } return result; }

测试程序：

var list = new LinkedList(); list.insert("a","head"); list.insert("b","a"); list.insert("c","b"); console.log(list.show()); list.remove("b"); console.log(list.show());

测试结果：