Javascript 中的链表与数组

所以我在 JS 中玩弄链表并提出以下问题：

假设我们有一个数组和一个链表，都有 5000 个元素。我们想在索引 10 处插入新元素。数组方式非常简单。我们在给定索引处插入新元素，并将其余元素向前移动一个索引。所以我尝试用链表来做到这一点，并以以下结果结束：

获取链表的实现尼古拉斯·扎卡斯 https://github.com/nzakas/computer-science-in-javascript/blob/master/data-structures/linked-list/linked-list.js并添加附加方法 addOnPosition(data,index)。最后是代码：

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

最后，我的问题是：这种方法是否比使用数组执行所有这些操作更快？如果是，两者的复杂性是多少？ 也许更重要的是，我是否错过了 adOnPosition 方法实现的某些内容？

See http://en.wikipedia.org/wiki/Dynamic_array#性能 http://en.wikipedia.org/wiki/Dynamic_array#PerformanceLinkedList 和 ArrayList 数据结构的复杂性。对于有趣的人，还可以查看何时使用 LinkedList 而不是 ArrayList？ https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist

在单链表中的节点后面插入是一个常数时间操作。如果双向链表中有一个节点，在它之前插入也是一个常数时间操作。

但是，您的 addOnPosition 函数会沿着链表“index”运行；也就是说，您从一个节点跳转到下一个节点很多次。因此，你的算法的复杂度基本上是 O(index) - 我们将其写为 O(n)。

解释一下我的观点：如果你想在第 0 个元素处插入一个节点，你的操作基本上会以恒定的时间运行；你得到this._front节点，你就完成了。要插入到线性单链表的末尾，您必须向下迭代到列表的末尾，执行从一个节点到下一个节点的更多“跳转”。您可以使用循环链表 http://en.wikipedia.org/wiki/Linked_list#Circular_list来优化这个案例。

至于使用数组列表执行类似的插入，插入复杂度基本上是 O(长度 - 索引)，因为长度索引元素必须在数组中向下移动，我们将其写为 O(n)。