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

比方说，我们有一个数组和一个链表，它们都有 5000 个元素。我们想在索引 10 处插入新元素。数组方式非常简单。我们在给定索引处插入新元素，并将其余元素向前移动一个索引。所以我尝试用链表来做这件事，并以下面的方式结束它:

从Nicholas Zakas获取链表的实现并添加附加方法 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 方法实现的某些内容？

最佳答案

参见 http://en.wikipedia.org/wiki/Dynamic_array#Performance对于 LinkedList 和 ArrayList 数据结构的复杂性。对于 funzies，还可以查看 When to use LinkedList over ArrayList?

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

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

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

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

关于javascript - Javascript 中的链表与数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18441656/