Liste liée vs Tableau en Javascript

J'ai donc été à jouer avec la liste liée dans JS et est venu avec la question suivante:

Permet de dire, que nous avons un tableau et une liste liée à la fois à 5000 éléments. Nous voulons insérer un nouvel élément à l'indice 10. Le tableau manière est assez simple. Nous insérer le nouvel élément à l'index donné et bouger le reste des éléments d'un index. J'ai donc essayé de faire avec cette liste, et à la fin il avec les personnes suivantes:

Obtenir la mise en œuvre de la liste liée de Nicolas Zakas et ajouter de la méthode addOnPosition(données,index). À la fin voici le 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();
}
}

À la fin, ma question est: cette méthode Est plus rapide que de faire tout cela avec le tableau et si elle l'est, qu'est-ce que la complexité pour les deux?
Et probablement le plus important, n'ai-je raté quelque chose avec le adOnPosition méthode de la mise en œuvre?

  • Pourquoi n'utilisez-vous pas la item méthode pour sélectionner l'index dans addOnPosition (on dirait que vous êtes vous répéter vous-même)? Cela pourrait être plus rapide pour les grandes listes, pourquoi ne pas vous écrire un test sur jsperf.com?
InformationsquelleAutor sla55er | 2013-08-26