循環雙向鏈表，如何管理節點與對象的關係？

Question

這個LinkedList函數使用非常不方便的方法來避免客戶端代碼需要知道鏈接節點。每個列表創建一個唯一的字符串，用於侵入性地將屬性插入添加到列表中的對象。有誰知道更好的方法來做到這一點？我應該提到在一段時間內移除物體是一項要求。

它的意思是客戶端的代碼如下所示：

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構造函數）。

這是LinkedList的代碼：

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 
})() 

Answer 1

這裏是我的實現：

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; 
     } 
    }; 
    } 
}