链表与Java中的数组 [英] 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:
从尼古拉斯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数据的复杂性结构。对于乐趣，还请查看何时在ArrayList上使用LinkedList？
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函数会在链表'index下运行时代；也就是说，您从一个节点跳到下一节点很多次。因此，您算法的复杂度基本上是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.
对于使用arraylist执行类似的插入操作，由于将length-index元素向下移动数组，因此插入复杂度基本上为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).
这篇关于链表与Java中的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
