Forums » Code » Doubly Linked List

I needed linked lists to manage the large amount of entities in my game - I couldn't find anything on the forums here so I decided to mash-up some code I found on the internet and make it Impact friendly. I've also added some methods so that list items can be deleted by 'object' rather than just index. For example, you can now do :

myList.removeObj(this);

Anyway here's the code :

/**
 * @Author Tim Fisher - Indiepath Ltd - Modified from source provided by Nicholas C. Zakas
 * 
 */

ig.module(
	'classes.doublylinkedlist'
)

.defines(function(){

	DoublyLinkedList = ig.Class.extend({
		
		_head : null,
		_tail : null,
		_length : 0,
					
		init: function() {
				
		},
		
		add: function (data){
		    
	        //create a new item object, place data in
	        var node = { 
	                data: data, 
	                next: null,
	                prev: null
	            };
	    
	        //special case: no items in the list yet
	        if (this._length == 0) {
	            this._head = node;
	            this._tail = node;
	        } else {
	        
	            //attach to the tail node
	            this._tail.next = node;
	            node.prev = this._tail;
	            this._tail = node;
	        }        
	        
	        //don't forget to update the count
	        this._length++;
	    
	    },

	    item: function(index){
	    
	        //check for out-of-bounds values
	        if (index > -1 && index < this._length){
	            var current = this._head,
	                i = 0;
	                
	            while(i++ < index){
	                current = current.next;            
	            }
	        
	            return current.data;
	        } else {
	            return null;
	        }
	    },

	    remove: function(index){
	    
	        //check for out-of-bounds values
	        if (index > -1 && index < this._length){
	        
	            var current = this._head,
	                i = 0;
	                
	            //special case: removing first item
	            if (index === 0){
	                this._head = current.next;
	                
	                /*
	                 * If there's only one item in the list and you remove it,
	                 * then this._head will be null. In that case, you should
	                 * also set this._tail to be null to effectively destroy
	                 * the list. Otherwise, set the previous pointer on the new
	                 * this._head to be null.
	                 */
	                if (!this._head){
	                    this._tail = null;
	                } else {
	                    this._head.prev = null;
	                }
	       
	            //special case: removing last item
	            } else if (index === this._length -1){
	                current = this._tail;
	                this._tail = current.prev;
	                this._tail.next = null;
	            } else {
	        
	                //find the right location
	                while(i++ < index){
	                    current = current.next;            
	                }
	            
	                //skip over the item to remove
	                current.prev.next = current.next;
	            }
	        
	            //decrement the length
	            this._length--;
	        
	            //return the value
	            return current.data;            
	        
	        } else {
	            return null;
	        }
	    },
	    
	    removeObj : function(obj){
	    	// Locate the object in the list
	    	var current = this._head, i = 0;
	    	// Compare the objects and find the index of the match
	    	while(this.objectEquals(obj, current.data) == false){
                current = current.next;
                i++;
                if (current == null) return null;
            }
	    	// The object has been found so remove it using the index
	    	this.remove(i);
	    },
	    

	    size: function(){
	        return this._length;
	    },
	    
	    toArray: function(){
	        var result = [],
	            current = this._head;
	        
	        while(current){
	            result.push(current.data);
	            current = current.next;
	        }
	        
	        return result;
	    },

	    toString: function(){
	        return this.toArray().toString();
	    },
	    
	    /* Comparison utility methods */
	    countProps : function(obj) {
	        var count = 0;
	        for (k in obj) {
	            if (obj.hasOwnProperty(k)) {
	                count++;
	            }
	        }
	        return count;
	    },
	    
	    objectEquals : function(v1, v2) {
	    	// Compare the types
	        if (typeof(v1) !== typeof(v2)) {
	            return false;
	        }
	        // Compare the function, if it's a function
	        if (typeof(v1) === "function") {
	            return v1.toString() === v2.toString();
	        }
	        // Compare the objects - count the properties and then enumerate the keys
	        if (v1 instanceof Object && v2 instanceof Object) {
	            if (this.countProps(v1) !== this.countProps(v2)) {
	                return false;
	            }
	            var r = true;
	            for (k in v1) {
	                r = this.objectEquals(v1[k], v2[k]);
	                if (!r) {
	                    return false;
	                }
	            }
	            return true;
	        } else {
	        	// Do a standard compare
	            return v1 === v2;
	        }
	    }

	});

});

It's simple to use:

var list = new DoublyLinkedList();
		list.add(1);
		list.add(3);
		list.add({hello:'mum'});
		list.add(2);
		
		console.log(list.toArray());
		
		list.removeObj({hello:'mum'});
		
		console.log(list.toArray());