循环，双向链表，如何管理节点与对象的关系

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