Linked list vs Array in Javascript

Question

So I was playing around with the linked list in JS and came up with the following question:

Lets say, that we have an array and a linked list both with 5000 elements. We want to insert new element at index 10. The array way is pretty simple. We insert the new element at the given index and move the rest of the elements one index forward. So I tried doing this with linked list and end it up with the following:

Getting the implementation of linked list from Nicholas Zakas and adding additional method addOnPosition(data,index). At the end here is the code:

function LinkedList() {
this._head = null;
this._length = 0;
}

LinkedList.prototype = {

constructor: LinkedList,

add: function(data) {

    var node = {
            data: data,
            next: null
        },
        current;

    if (this._head === null) {
        this._head = node;
    }
    else {
        current = this._head;
        while (current.next) {
            current = current.next;
        }
        current.next = node;
    }
    this._length++;
},

remove: function(index) {

    if (index > -1 && index < this._length) {

        var current = this._head,
            previous,
            i = 0;


        if (index === 0) {
            this._head = current.next;
        }
        else {
            while (i++ < index) {
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }

        this._length--;
        return current.data;
    }
    else {
        return null;
    }
},

item: function(index) {

    var current = this._head,
        i = 0;

    if (index > - 1 && index < this._length) {

        while (i++ < index) {
            current = current.next;
        }
        return current.data;

    }
    else {
        return null;
    }
},

addOnPosition: function(data,index) {

    if (index > -1 && index <= this._length) {
        var node = {
                data: data,
                next: null
            },
            current = this._head,
            i = 0,
            temp,
            previous;

        if (this._head === null) {
            this._head = node;
        }
        else {
            if (index === 0) {
                this._head = node;
                node.next = current;
            }
            else {
                while (i++ < index) {
                    previous = current;
                    current = current.next;
                }
                previous.next = node;
                node.next = current;
            }
        }
        this._length++;
    }
    else {
        return null;
    }
},

toArray: function() {
    var result = [],
        current = this._head;

    while (current) {
        result.push(current.data);
        current = current.next;
    }
    return result;
},
toString: function() {
    return this.toArray().toString();
}
}

At the end, my question is: Is this method faster than doing all this with array and if it is, what is the complexity for both? And probably the more important, did I missed something with the adOnPosition method implementation?

Answer 1

See http://en.wikipedia.org/wiki/Dynamic_array#Performance for complexity of LinkedList and ArrayList data structures. For funzies, also check out When to use LinkedList over ArrayList?

---

Inserting after a node in a singly-linked list is a constant-time operation. If you have a node in a doubly-linked list, inserting before it is also a constant-time operation.

However, your addOnPosition function runs down the linked list 'index' times; that is, you jump from one node to the next that many times. As such, your algorithm's complexity is basically O(index) - we'd write that as O(n).

To explain my point: If you wish to insert a node at the 0th element, your operation basically runs at constant time; you get the this._front node and you're done. To insert to the end of your linear, singly-linked list, you must iterate down to the end of the list, performing more "jumps" from one node to the next. You can use circular linked lists to optimize this case.

As for performing a similar insertion with an arraylist, insertion complexity is basically O(length - index) as length-index elements must be shifted down the array, we write this as O(n).

Answer 2

Actually insertion into the middle of a linked list is O(n) time complexity, meaning the time it will take on average or in the worst case is proportional to the number of elements already in the list (i.e. n). "O(index)" is not even a real time complexity.

The time complexity for inserting into the middle of an array is also O(n). "O(length - index)" is also not a real time complexity. The number of operations involved in shifting elements in the list in the average or worst case is going to be proportional to the number of items in the list (i.e. n).

The advantage to a linked list over an array is that prepending/appending elements to the front/back of the list is O(1) time complexity, but O(n) for an array.

The advantage of an array over a linked list is that retrieving an element from an array by it's index is O(1), but O(n) for a linked list.

The simplest way to decide between a linked list and an array, is to determine if you need fast appending/prepending or fast index based retrieval of data. If you need both, then there are some variations on these data structures that provide good performance/compromises in both areas.