Liste liée: Cette solution est-elle bonne?

Question

Je cherchais un moyen d'éviter de partir de la tête de la liste chaque fois que je veux trouver un nœud, donc j'ai pensé assigner des index aux nœuds, en gardant un pointeur vers un nœud aléatoire (pas exactement aléatoire, voir plus bas) puis trouver le pointeur le plus proche de l'index que je veux trouver. Permettez-moi d'expliquer avec le code:

// head and last are pointers to the first and last items of a doubly-linked list 
// current is a pointer that will change over time. It's used as a temporary pointer 
template <class T>a 
Node<T>* List<T>::get_closest(Node<T> node, int& difference) { 
    int curr_to_i = current->index - node->index; 
    int last_to_i = last->index - node->index; 
    Node* closest = node->index < abs(curr_to_i) ? head : current; 
    closest = closest->index < abs(last_to_i) ? closest : last; 
    difference = closest->index - node->index; 
    return closest; 
} 

/* 
* This functions adds a node with the given value to the given index. The node at that 
* index and all the following are moved, and the new node is inserted before them. 
*/ 
template <class T> 
bool List<T>::add(T value, int index) { 
    if (index < 0) { //Invalid index 
     return false; 
    } else if (index == last->index +1) { 
     push(value); 
     return true; 
    } else if (index > 0) { 
     Node* new_n = new Node; 
     new_n->value = value; 
     new_n->index = index; 
     int difference; 
     Node* closest = get_closest(new_n, difference); 
     if (difference < 0) { 
      for (int i = 0; i < abs(difference); i++) { 
       current = current->previous; 
      } 
     } else if (difference > 0) { 
       for (int i = 0; i < abs(difference); i++) { 
       current = current->next; 
      } 
     } /* current now points to the node we want to move */ 
     new_n->previous = current->previous; 
     new_n->next = current; 
     current->previous->next = new_n; 
     current->previous = new_n; 
     if (index == 0) { 
      root = new_n; 
     } 
     new_n = new_n->next; 
     while (new_n != null) { 
      new_n->index++; 
      new_n = new_n->next; 
     } 
     return true;   
    } 
} 

Est-ce plus efficace que à partir de la tête et de faire progresser en avant un certain nombre de fois?

Answer 1

Si vous avez besoin d'accéder à des éléments au milieu de la liste, il vaut mieux utiliser un tableau. Une liste est une structure de données abstraite (ADT) qui peut être implémentée de diverses manières. Ce que vous avez essentiellement fait est de créer une représentation redondante qui a l'overhead des deux méthodes.

L'avantage d'une liste chaînée est que les insertions peuvent être très rapides en tête de liste - O (1) vs. O (n) pour un tableau. Cependant, puisque vous devez maintenir votre index, vous avez de toute façon un overhead O (N) pour les insertions.

Si vous avez besoin d'indexation, utilisez simplement un tableau. Plus simple et plus rapide.

Answer 2

Il semblerait que l'insertion deviendrait beaucoup plus coûteuse. Pourquoi ne pas écrire un programme de test et chronométrer la différence?

Answer 3

Votre index pseudo-aléatoire peut potentiellement être proche du début de la liste (juste pour illustrer), provoquant des décalages de chaque élément dans la liste par la suite. Cela rend l'insertion dans une liste liée très coûteuse, tellement qu'il devient inutile d'avoir une liste liée, vous pouvez simplement utiliser un tableau.

Answer 4

Il me semble que vous essayez d'inventer Skip Lists, qui est une sorte d'arborescence triée et équilibrée.

Probablement ce que vous voulez vraiment est d'utiliser quelque chose comme boost :: multi_index, qui vous permettra d'utiliser une combinaison d'indices pour obtenir de bonnes performances sur une gamme d'opérations. L'un des examples a une impression très similaire à ce que vous essayez de faire. Avant de tenter d'utiliser quelque chose comme ceci, vous devez établir un profil de vos utilisations réelles pour déterminer s'il y a un réel avantage à optimiser cette partie de votre code, et si cela s'avère être un goulot d'étranglement, essayez plusieurs combinaisons différentes de des structures pour voir laquelle fonctionne réellement le mieux sur votre utilisation spécifique. À moins que votre ensemble de données soit assez grand, un std::vector sera presque toujours le plus rapide, en raison de la localité.