循环，双向链表，如何管理节点与对象的关系？ [英] Circular, doubly linked list, how to manage the node to object relationship?
问题描述
此LinkedList函数使用一种非常狡猾的方法来避免客户端代码需要了解链接节点。每个列表创建一个唯一的字符串，该字符串用于将属性插入要添加到列表中的对象中。有谁知道更好的方法吗？我应该提到必须定期删除对象。
This LinkedList function uses a very dodgy method to avoid client code needing to know about the linking nodes. Each list creates a unique string which is used to intrusively insert properties into the objects being added to the list. Does anyone know of a better way to do this? I should mention that removing objects in constant time is a requirement.
这确实意味着客户端代码如下：
It does mean that client code looks like:
var myList = new LinkedList()
var a = new Something()
var b = new SomethingElse()
myList.addTail(a)
myList.addTail(b)
myList.remove(a)
myList.remove(b)
这很好而且可读，但是至少可以说，将属性插入对象中（可能与现有属性冲突） （尽管可以将其记录下来，并且可以将属性名称前缀传递给LinkedList构造函数。）
which is nice and readable, but the insertion of properties into the objects (which might clash with existing properties) is shaky, to say the least (although it can be documented and the property name prefix could be passed in to the LinkedList constructor).
这是LinkedList代码：
This is the LinkedList code:
var LinkedList = (function() {
var id = 0
var Node = function(obj, p, n) {
this.item = obj
this.prev = p
this.next = n
}
var list = function() {
this.length = 0
this.nodeName = '_' + id++ + 'lnn'
this.root = new Node(null)
this.root.next = this.root
this.root.prev = this.root
}
list.prototype = {
insertBefore : function(obj, item) {
var node = new Node(item, obj.prev, obj)
obj.prev.next = node
obj.prev = node
item[this.nodeName] = node
++this.length
},
insertAfter : function(obj, item) {
var node = new Node(item, obj, obj.next)
obj.next.prev = node
obj.next = node
item[this.nodeName] = node
++this.length
},
addTail : function(item) {
this.insertBefore(this.root, item)
},
addHead : function(item) {
this.insertAfter(this.root, item)
},
remove : function(item) {
var node = item[this.nodeName]
node.prev.next = node.next
node.next.prev = node.prev
delete node.item[this.nodeName]
--this.length
},
popHead : function() {
if(this.length > 0) {
var node = this.root.next
node.prev.next = node.next
node.next.prev = node.prev
delete node.item[this.nodeName]
--this.length
return node.item
}
return null
},
popTail : function() {
if(this.length > 0) {
var node = this.root.prev
node.prev.next = node.next
node.next.prev = node.prev
delete node.item[this.nodeName]
--this.length
return node.item
}
return null
},
forEach : function(callback, context) {
var node = this.root.next
var index = 0
while(node !== this.root) {
var next = node.next
if(callback.call(context, node.item, index) === false) {
return false
}
node = next
++index
}
return true
},
removeIf : function(callback, context) {
var node = this.root.next
while(node !== this.root) {
var next = node.next
if(callback.call(context, node.item) === true) {
node.prev.next = next
node.next.prev = node.prev
delete node.item[this.nodeName]
--this.length
}
node = next
}
},
toString : function() {
var s = this.length.toString()
var sep = ':<'
this.forEach(function(i, index) {
s += sep + i.toString()
sep = ','
})
return s + '>'
}
}
return list
})()
推荐答案
这是我的实现：
function LinkedList(initialValues){
var head = null,
version = 0,
list = {
push: function(){
var args = [].slice.call(arguments, 0),
pushable = null;
while(args.length && (pushable = args.shift()))
head = new Node(pushable).append(head);
version++;
return this;
},
pop: function(){
var popped = head;
head = head.next();
version++;
return popped.value();
},
peek: function(){
return head && head.value();
},
iterator: function(){
return new Iterator(head, version);
},
toString: function(){
var vals = [],
iter = new Iterator(head, version);
while(iter.node()){
vals.push(iter.node().toString());
iter.step();
}
return ["("].concat(vals).concat(")").join(" ");
},
size: function(){
var iter = new Iterator(head, version);
while(iter.node()){
iter.step();
}
return iter.index();
}
};
return list.push.apply(list, initialValues);
function Node(input){
var content = input,
next = null;
return {
next: function(){
return next;
},
value: function(){
return content;
},
append: function(node){
next = node;
return this;
},
set: function(val){
return content = val;
},
toString: function(){
return content.toString();
}
};
}
function Iterator(base, v){
var current = base, index = 0,
checkSafe = function(){
if(v === version)
return true;
else
throw "The iterator is no longer valid, list modified.";
};
return {
node: function(){
checkSafe();
return current;
},
step: function(){
checkSafe();
current = current.next();
index++;
return this;
},
index: function(){
checkSafe();
return index;
}
};
}
}
这篇关于循环，双向链表，如何管理节点与对象的关系？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
