js单向链表的具体实现实例_javascript技巧

复制代码 代码如下:function linkNode(_key, _value){ /// this.Key = _key; this.Value = _value; this.next = null;}function Link(){ /// this.root = new linkNode(null, null); //root永远是个空节点 this.end = this.root;}Link.prototype ={ count: 0, value: function (_key) { /// /// /// var i = this.root; while (Boolean(i = i.next)) { if (i.Key == _key) return i.Value; } }, add: function (_key, _value) { /// /// /// /// var i = this.root; while (Boolean(i = i.next)) { if (i.Key == _key) return i.Value = _value; } var node = new linkNode(_key, _value); if (this.count == 0) this.root.next = node; else this.end.next = node; this.end = node; this.count++; return _value; }, insert: function (_key, node) { /// /// /// var i = this.root; while (Boolean(i = i.next)) { if (i.Key == _key) { var tmp = i.next; i.next = node; node.next = tmp; break; } } }, insertBefore: function (_key, node) { /// /// /// var i = this.root; while (Boolean(i = i.next)) { if (i.next.Key == _key) { var tmp = i.next; i.next = node; node.next = tmp; break; } } }, remove: function (_key) { /// /// var i = this.root; do { if (i.next.Key == _key) { if (i.next.next == null) this.end = i; i.next = i.next.next; this.count--; return; } } while (Boolean(i = i.next)) }, exists: function (_key) { /// /// /// var i = this.root; while (Boolean(i = i.next)) if (i.Key == _key) return true; return false; }, removeAll: function () { /// this.root = new linkNode(null, null); this.end = this.root; this.count = 0; }, Obj2str: function (o) { if (o == undefined) { return ""; } var r = []; if (typeof o == "string") return "\"" + o.replace(/([\"\\])/g, "\\$1").replace(/(\n)/g, "\\n").replace(/(\r)/g, "\\r").replace(/(\t)/g, "\\t") + "\""; if (typeof o == "object") { if (!o.sort) { for (var i in o) r.push("\"" + i + "\":" + this.Obj2str(o[i])); r = "{" + r.join() + "}"; } else { for (var i = 0; i r.push(this.Obj2str(o[i])) r = "[" + r.join() + "]"; } return r; } return o.toString().replace(/\"\:/g, '":""'); }, getJSON: function () { /// /// //内部方法，用于递归 var me = this; var getChild = function (node) { var str = ""; str += "{\"Key\":\"" + node.Key + "\",\"Value\":" + me.Obj2str(node.Value); if (node.next != null) str += ",\"next\":" + getChild(node.next); else str += ",\"next\":\"null\""; str += "}"; return str; }; var link = "{\"root\":{\"Key\":\"null\",\"Value\":\"null\",\"next\":"; if (this.count == 0)//如果空表 { return "{\"root\":{\"Key\":\"null\",\"Value\":\"null\",\"next\":\"null\"},\"end\":{\"Key\":\"null\",\"Value\":\"null\",\"next\":\"null\"},\"count\":\"0\"}"; } link += getChild(this.root.next) + "}"; //加上end link += ",\"end\":{\"Key\":\"" + this.end.Key + "\",\"Value\":" + me.Obj2str(this.end.Value) + ",\"next\":\"null\""; link += "},\"count\":\"" + this.count + "\"}"; return link; }, getArrayJSON: function () { /// /// var link = "{\"link\":["; var i = this.root; while (Boolean(i = i.next)) { link += this.Obj2str(i.Value) + ","; } link = link.substr(0, link.length - 1); link += "]}"; return link; }, sort: function (fn) { /// /// if (fn != null) { var i = this.root; while (Boolean(i = i.next)) { var j = this.root; while (Boolean(j = j.next)) { if (j.next != null) { if (fn.call(this, j)) { var Key = j.Key; var Value = j.Value; j.Key = j.next.Key; j.Value = j.next.Value; j.next.Key = Key; j.next.Value = Value; } } } this.end = i; } } else { } }};