Javascript 中的链表与数组 [英] Linked list vs Array in Javascript

问题描述

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

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

假设我们有一个数组和一个链表，它们都有 5000 个元素.我们想在索引 10 处插入新元素.数组方式非常简单.我们在给定的索引处插入新元素，并将其余元素向前移动一个索引.所以我尝试用链表来做这件事，最后得到以下内容:

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:

从Nicholas Zakas 并添加额外的方法 addOnPosition(data,index).最后是代码:

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

最后，我的问题是:这种方法是否比用数组做所有这些更快，如果是，两者的复杂度是多少?或许更重要的是，我是否遗漏了 adOnPosition 方法的实现?

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?

推荐答案

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

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.

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

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).

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

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.

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

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).

这篇关于Javascript 中的链表与数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！