链接列表与Javascript中的数组

Question

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

Answer 1

实际上插入到链表的中间是O(n)时间复杂度,意味着它将花费平均时间或者在最坏情况下与已经在列表中的元素数量(即n)成比例."O(索引)"甚至不是实时复杂性.

插入数组中间的时间复杂度也是O(n)."O(长度 - 索引)"也不是实时复杂性.在平均或最差情况下移动列表中的元素所涉及的操作的数量将与列表中的项目数量(即n)成比例.

对阵列上的链表的优点是在列表的前/后添加/附加元素是O(1)时间复杂度,但是对于数组是O(n).

数组在链表上的优点是通过索引从数组中检索元素是O(1),但是对于链表来说是O(n).

决定链接列表和数组之间的最简单方法是确定是否需要快速追加/前置或基于快速索引的数据检索.如果您需要两者,那么这些数据结构会有一些变化,可以在这两个方面提供良好的性能/妥协.

Answer 2

有关LinkedList和ArrayList数据结构的复杂性,请参见http://en.wikipedia.org/wiki/Dynamic_array#Performance.对于funzies,还要检查何时使用LinkedList over ArrayList？

在单链表中的节点之后插入是恒定时间操作.如果在双向链表中有节点,则在它之前插入也是一个恒定时间操作.

但是,你的addOnPosition函数会在链表"索引"时间内运行; 也就是说,你多次从一个节点跳到下一个节点.因此,您的算法的复杂性基本上是O(索引) - 我们将其写为O(n).

解释一下我的观点:如果你想在第0个元素插入一个节点,你的操作基本上是在恒定的时间运行; 你得到了this._front节点,你就完成了.要插入到线性单链表的末尾,必须迭代到列表的末尾,从一个节点到下一个节点执行更多"跳转".您可以使用循环链接列表来优化此案例.

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