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