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?
Vous devez vous connecter pour publier un commentaire.
Voir http://en.wikipedia.org/wiki/Dynamic_array#Performance pour la complexité de la LinkedList liste de tableaux et des structures de données. Pour funzies, découvrez également Quand utiliser LinkedList sur ArrayList?
De l'insertion, après un nœud dans une liste liée individuellement est une constante de temps de l'opération. Si vous avez un nœud dans une liste à double liaison, l'insertion de l'avant c'est aussi une constante de temps de l'opération.
Cependant, votre addOnPosition fonction s'exécute en bas de la liste, 'index' temps; qui est, vous sauter à partir d'un nœud à l'autre qu'à de nombreuses reprises. En tant que tel, un algorithme de complexité est fondamentalement O(index) - il faudrait écrire que O(n).
Expliquer mon point: Si vous souhaitez insérer un nœud à l'0e élément, votre opération de coeur s'exécute en temps constant; vous obtenez la
this._front
nœud et vous avez terminé. Pour insérer à la fin de votre linéaire, liste liée individuellement, vous devez effectuer une itération jusqu'à la fin de la liste, de l'exécution de "sauts" d'un nœud à l'autre. Vous pouvez utiliser circulaire listes liées pour optimiser ce cas.Que pour l'exécution d'une semblable d'insertion avec une liste de tableaux, insertion complexité est fondamentalement O(longueur de l'index), la longueur de l'index des éléments doit être décalé vers le bas du tableau, nous écrire ce que O(n).
En fait l'insertion dans le milieu d'une liste chaînée est O(n) le temps de la complexité, ce qui signifie le temps qu'il faudra en moyenne ou dans le pire des cas est proportionnelle au nombre d'éléments déjà dans la liste (c-n). "O(index)" n'est même pas un vrai moment de complexité.
La complexité du temps pour l'insertion dans le milieu d'un tableau est également en O(n). "O(longueur de l'index)" est pas non plus un temps réel de la complexité. Le nombre de fonctions impliquées dans le déplacement des éléments dans la liste, dans la moyenne ou au pire des cas va être proportionnelle au nombre d'éléments dans la liste (c'est à dire n).
L'avantage pour une liste, un tableau, c'est que les préfixant/ajoutez des éléments à l'avant/à l'arrière de la liste est O(1) le temps de la complexité, mais en O(n) pour un tableau.
L'avantage d'un tableau sur une liste chaînée est que de la récupération d'un élément d'un tableau, de par leur indice est O(1) O(n) pour une liste liée.
La façon la plus simple de choisir entre une liste et un tableau, est de déterminer si vous avez besoin rapide ajoutant/ajoutant ou rapide de l'indice basé sur la récupération des données. Si vous avez besoin, alors il ya quelques variations sur ces structures de données qui offrent de bonnes performances/compromis dans les deux zones.