Javascript 中的链表与数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18441656/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Linked list vs Array in Javascript
提问by sla55er
So I was playing around with the linked list in JS and came up with the following question:
所以我在 JS 中使用链表并提出以下问题：
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:
假设我们有一个数组和一个链表，它们都有 5000 个元素。我们想在索引 10 处插入新元素。数组方式非常简单。我们在给定的索引处插入新元素，并将其余元素向前移动一个索引。所以我尝试用链表来做这件事，最后得到以下结果：
Getting the implementation of linked list from Nicholas Zakasand adding additional method addOnPosition(data,index). At the end here is the code:
从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();
}
}
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?
最后，我的问题是：这种方法是否比用数组做所有这些更快，如果是，两者的复杂度是多少？也许更重要的是，我是否遗漏了 adOnPosition 方法的实现？
采纳答案by Warty
See http://en.wikipedia.org/wiki/Dynamic_array#Performancefor complexity of LinkedList and ArrayList data structures. For funzies, also check out When to use LinkedList over ArrayList?
有关LinkedList 和 ArrayList 数据结构的复杂性，请参阅http://en.wikipedia.org/wiki/Dynamic_array#Performance。对于朋友，还请查看何时在 ArrayList 上使用 LinkedList？
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.
在单向链表中的节点之后插入是一个常数时间操作。如果你在双向链表中有一个节点，在它之前插入也是一个常数时间的操作。
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).
但是，您的 addOnPosition 函数会运行链表“索引”次；也就是说，你从一个节点跳到下一个节点很多次。因此，您的算法的复杂度基本上是 O(index) - 我们将其写为 O(n)。
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._frontnode 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 liststo optimize this case.
解释一下我的观点：如果你想在第 0 个元素插入一个节点，你的操作基本上是在恒定时间运行的；你得到了this._front节点，你就完成了。要插入到线性单向链表的末尾，您必须向下迭代到列表的末尾，从一个节点到下一个节点执行更多的“跳转”。您可以使用循环链表来优化这种情况。
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).
至于使用数组列表执行类似的插入，插入复杂度基本上是 O(length - index) 因为长度索引元素必须在数组中向下移动，我们将其写为 O(n)。
回答by user3159785
Actually insertion into the middle of a linked list is O(n) time complexity, meaning the time it will take on average or in the worst case is proportional to the number of elements already in the list (i.e. n). "O(index)" is not even a real time complexity.
实际上插入链表中间的时间复杂度为 O(n)，这意味着它平均或在最坏情况下所花费的时间与链表中已有的元素数量（即 n）成正比。“O(index)”甚至不是实时复杂度。
The time complexity for inserting into the middle of an array is also O(n). "O(length - index)" is also not a real time complexity. The number of operations involved in shifting elements in the list in the average or worst case is going to be proportional to the number of items in the list (i.e. n).
插入数组中间的时间复杂度也是 O(n)。"O(length - index)" 也不是实时复杂度。在平均或最坏情况下，在列表中移动元素所涉及的操作数将与列表中的项目数（即 n）成正比。
The advantage to a linked list over an array is that prepending/appending elements to the front/back of the list is O(1) time complexity, but O(n) for an array.
链表相对于数组的优势在于，在列表的前/后添加/添加元素的时间复杂度为 O(1)，但对于数组而言为 O(n)。
The advantage of an array over a linked list is that retrieving an element from an array by it's index is O(1), but O(n) for a linked list.
数组相对于链表的优势在于，通过索引从数组中检索元素是 O(1)，而对于链表，则是 O(n)。
The simplest way to decide between a linked list and an array, is to determine if you need fast appending/prepending or fast index based retrieval of data. If you need both, then there are some variations on these data structures that provide good performance/compromises in both areas.
在链表和数组之间做出决定的最简单方法是确定您是否需要快速附加/前置或基于快速索引的数据检索。如果两者都需要，那么这些数据结构有一些变化，可以在这两个方面提供良好的性能/妥协。
