Complexité du temps de liste liée
Liste liée individuellement
Le diagramme suivant montre une liste liée individuellement de trois éléments:
Chaque élément a deux parties. La première partie a les données. La deuxième partie a un pointeur qui pointe vers l'élément suivant. Les deuxième et troisième éléments sont similaires au premier. Le dernier élément a un pointeur nul. Avec la liste liée individuellement, la traversée ne peut aller dans une seule direction: la direction avant.
Les éléments d'une liste liée ne sont pas abordés par les références (indices en carré de crochets), tout étant égal. Ils sont accessibles par les itérateurs (pointeurs). Dans le cas d'une liste liée individuellement, l'itérateur doit commencer depuis le début et passer de l'élément par élément, afin d'atteindre l'élément prévu.
Liste doublement liée
Le diagramme suivant montre une liste doublement liée de trois éléments:
Ici, chaque élément a trois parties. La première partie a un pointeur qui pointe vers l'élément précédent. La deuxième partie a les données. La troisième partie a un pointeur qui pointe vers l'élément suivant. La première partie du premier élément a un pointeur qui pointe vers Null. La troisième partie du dernier élément a un pointeur qui pointe vers Null. Avec la liste doublement liée, la traversée peut aller dans les deux sens: la direction avant ou la direction inverse.
Les éléments d'une liste liée ne sont pas abordés par les références (indices en carrés). Ils sont accessibles par les itérateurs (pointeurs). Dans le cas d'une liste doublement liée, l'itérateur peut se déplacer dans les deux sens mais doit commencer à chaque extrémité. Le mouvement ne peut pas démarrer officiellement à partir de la liste.
Le but de cet article est de déterminer ce que l'on appelle la complexité temporelle de la liste liée.
Complexité du temps en général
La complexité du temps est l'exécution relative d'un code. La complexité du temps peut également être considérée comme le nombre d'opérations principales du code.
Temps constant
Une opération principale telle que l'insert ou la suppression aurait une complexité temporelle de temps constant car l'action peut être considérée comme se produisant une fois. Il est écrit comme:
O (1)
où 1 signifie un temps ou une action constant. Cela utilise la notation Big-O qui commence par O en majuscules suivie de parenthèses. À l'intérieur des parenthèses se trouve le nombre d'opérations principales pour la tâche.
Temps linéaire
La lecture d'un tableau à partir du début - un élément après l'autre à la recherche d'un élément particulier - est appelé une recherche linéaire.
L'élément recherché peut être trouvé quelque part au milieu et la recherche s'arrêterait. Ceci est toujours une recherche linéaire. La complexité temporelle de la recherche linéaire est écrite comme:
Sur)
où n est le nombre maximal possible d'opérations.
Liste liée Opérations principales
Recherche
Pour la liste liée individuellement, afin de passer d'un élément à l'autre, le code doit utiliser le pointeur de l'élément actuel, qui pointe vers l'élément suivant. Ce n'est pas le cas avec les tableaux. Pour une liste doublement liée, afin de passer d'un élément à l'autre, le code doit utiliser le pointeur de l'élément actuel qui pointe vers l'élément suivant. Ce n'est pas le cas avec les tableaux. Pour une liste doublement liée, afin de passer d'un élément à l'élément précédent, le code doit utiliser le pointeur de l'élément actuel qui pointe vers l'élément précédent. Ce n'est pas le cas avec les tableaux.
Effacement
Lorsqu'un élément actuel est supprimé, le pointeur de l'élément précédent qui le pointait vers le point, doit être fait pour pointer vers l'élément suivant. Ensuite, le pointeur de l'élément suivant le pointant devait être fait pour pointer vers l'élément précédent.
Insertion
Lorsque l'élément actuel est inséré, le pointeur de l'élément précédent qui pointait vers l'élément suivant doit être fait pour pointer vers l'élément actuel. Le pointeur de l'élément suivant qui pointait vers l'élément précédent doit être fait pour pointer vers l'élément actuel.
Le pointeur avant de l'élément actuel doit être fait pour pointer vers le nouvel élément suivant. Le pointeur arrière de l'élément actuel doit être fait pour pointer vers le nouvel élément précédent.
Complexité du temps pour la liste liée
Lorsque vous parlez de complexité temporelle pour une liste liée, c'est la complexité du temps pour la recherche, l'insertion et la suppression dont on parle de. Ce n'est pas le moment de la complexité de la construction de la liste liée dont on parle. La complexité du temps pour créer une liste liée est un problème différent.
Recherche
Pour qu'une liste liée individuellement soit rechercher un élément particulier (données), le code de recherche doit scanner l'élément de liste par élément depuis le début. Pour qu'une liste doublement liée soit à la recherche d'un élément particulier, le code de recherche doit scanner l'élément de liste par élément - depuis le début. Ou numériser la liste, élément par élément, à partir de la fin. La complexité du temps de recherche pour une liste liée (individuellement ou doublement) est:
Sur)
où n est le nombre d'éléments dans la liste. Peu importe si l'élément était trouvé, quelque part dans la liste.
Insertion
L'insertion est considérée comme une opération principale. Afin d'insérer un élément dans une liste liée, la recherche doit avoir lieu, pour arriver au poste, pour l'insertion. La complexité temporelle de la recherche est O (n). La complexité du temps pour l'action de l'insertion est O (1). Ainsi, la complexité temporelle de l'insertion dans une liste liée est O (n + 1). Pour plus de simplicité, la complexité temporelle de l'insertion d'un élément, dans une liste liée, est écrite comme:
Sur)
Effacement
La suppression est considérée comme une opération principale. Afin de supprimer un élément dans une liste liée, la recherche doit avoir lieu, pour arriver au poste de suppression. La complexité temporelle de la recherche est O (n). La complexité du temps pour l'action de la suppression est O (1). Ainsi, la complexité temporelle de la suppression dans une liste liée est O (n + 1). Pour plus de simplicité, la complexité temporelle de la suppression d'un élément, sur une liste liée, est écrite comme:
Sur)
Construire une liste liée en C
Pour construire une liste doublement liée en C, utilisez l'objet struct. Le premier membre de données doit avoir un pointeur qui pointe vers la structure précédente. Le troisième membre de données doit avoir un pointeur qui pointe vers la structure suivante. Le membre des données moyens devrait avoir les données. Le premier membre de données de la première structure devrait pointer vers null. Le troisième membre de données de la dernière structure devrait également indiquer Null.
Dans le cas d'une liste liée individuellement, omettez le premier membre de données.
Conclusion
La complexité du temps pour rechercher une liste liée est:
Sur)
Pour plus de simplicité, la complexité du temps pour insérer un élément dans une liste liée est:
Sur)
et pas o (1).
Pour plus de simplicité, la complexité du temps pour la suppression d'un élément, sur une liste liée, est:
Sur)
et pas o (1).