Circular, doubly linked list, how to manage the node to object relationship?

Question

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)

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).

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

Answer 1

Here's my implementation:

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