8

所以我在 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 方法的实现？

4

2 回答 2

6

有关 LinkedList 和 ArrayList 数据结构的复杂性，请参阅http://en.wikipedia.org/wiki/Dynamic_array#Performance。对于有趣的人，还可以查看何时使用 LinkedList 而不是 ArrayList？

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

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

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

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

于 2013-08-26T10:51:25.413 回答
6

实际上插入到链表中间是 O(n) 时间复杂度，这意味着平均或在最坏的情况下它所花费的时间与链表中已有元素的数量（即 n）成正比。“O(index)”甚至不是实时复杂度。

插入数组中间的时间复杂度也是 O(n)。“O(length - index)”也不是实时复杂度。在平均或最坏的情况下，移动列表中的元素所涉及的操作数将与列表中的项目数（即 n）成正比。

链表相对于数组的优势在于，将元素添加到列表的前/后是 O(1) 时间复杂度，但对于数组来说是 O(n)。

数组相对于链表的优势在于，通过索引从数组中检索元素是 O(1)，但对于链表来说是 O(n)。

在链表和数组之间做出决定的最简单方法是确定您是否需要快速附加/前置或基于快速索引的数据检索。如果您两者都需要，那么这些数据结构有一些变体，可以在这两个领域提供良好的性能/折衷。

于 2014-01-04T08:29:19.787 回答