JS实现双向链表.docx

JS部分- LinkedList.js/* * author Tony * description 该js文件定义了双向链表 */LinkedList = function()function Node(data, prev, next) this.data = data | null; this.prev = prev | null; this.next = next | null;Ntotype = getValue: function() return this.data; , setValue: function(obj) this.data = obj; , getPrev: function() return this.prev; , setPrev: function(node) this.prev = node; , getNext: function() return this.next; , setNext: function(node) this.next = node; ;Ntotype.constructor = Node;function nodeByIndex(index, list) var i = 0, node = list.head, length = list.length; / 第一个 if(index=0) return node; while(node.next) if(i=index) return node; node = node.next & node.next; i+; / 最后 一个 node = length-1 = index ? node : null; return node; function nodeByData(data, list) var node = list.head; while(node.next) if(node.data = data) return node; node = node.next; if(node.data = data) return node; / 没有找到 return null;function LinkedList() this.head = null; this.tail = null; this.length = 0;LinkedLtotype = add: function(index, obj) if(obj = undefined | obj = null | typeof index != number) throw new Error(add failed, invalid param); / 逆向取 -1，如取最后一个元素 if(index 0) index = this.length + index; / 空链表/索引越界 if(indexthis.length) throw new Error(add failed, invalid index); var newNode = new Node(obj); if(index=0) if(this.head) newNode.setNext(this.head); this.head = newNode; else this.head = this.tail = newNode; else var node = nodeByIndex(index-1, this), next = node.next; node.setNext(newNode); newNode.setPrev(node); newNode.setNext(next); this.length+; , get: function(index) if(typeof index != number) throw new Error(get failed, invalid param); / 逆向取 -1，如取最后一个元素 if(index 0) index = this.length + index; / 空链表/索引越界 if(this.isEmpty() | index=this.length) throw new Error(Index: + index + , Size: + this.length); var node = nodeByIndex(index, this); return node.data; , getFirst: function() return this.get(0); , getLast: function() return this.get(this.length-1); , set: function(index, obj) / 逆向取 -1，如取最后一个元素 if(index 0) index = this.length + index; / 空链表/索引越界 if(this.isEmpty() | index=this.length) throw new Error(Index: + index + , Size: + this.length); var node = nodeByIndex(index, this); node.data = obj; , size: function() return this.length; , clear: function() this.head.next = null; this.head = null; , remove: function(obj) var isIndex = typeof obj = number; var node = isIndex ? nodeByIndex(obj, this) : nodeByData(obj, this); if(node = null) throw new Error(remove failed, the node does not exist); var prev = node.prev; / 删除第一个元素，注意第一个元素没有前驱 if(prev = null) this.head = node.next; this.head.prev = null; node.next = null; node = null; else prev.setNext(node.next); node.next.setPrev(prev); node.prev = null; node.next = null; node = null; this.length-; , isEmpty: function() return this.head = null; , addLast: function(obj) this.add(this.length, obj); , addFirst: function(obj) this.add(0, obj); , contains: function(obj) var node = this.head; if(this.isEmpty() return false; while(node.next) if(node.data = obj) return true; node = node.next; / 第一个(length为1时)和最后一个元素 if(node.data = obj) return true; return false; , toString: function() var str = , node = this.head; if(this.isEmpty() return ; str = + node.data; while(node.next) node = node.next; str += , + node.data; str += ; return str; ;LinkedLtotype.constructor = LinkedList;return LinkedList; ();JSP页面测试部分-XXX.jspInsert title here / 双向链表测试 var list = new LinkedList(); list.add(0,one); list.add(1,two); list.addLast(three); list.addLast(four); list.add(2,five); /list.addFirst(five); /list.addLast(five); /console.log(list.size(); console.log(list.get(3);