© Profit_Image/Shutterstock.com
Vous avez peut-être compris les tableaux, mais il existe de nombreuses structures de données que vous pouvez utiliser en programmation. À certains égards, une liste chaînée est similaire à un tableau, mais il existe quelques différences essentielles. Découvrez ce qu’est une liste liée, explorez les différents types de listes liées et découvrez comment en utiliser une avec cet article.
Qu’est-ce qu’une liste liée ?
Comme un tableau, une liste linéaire est une structure de données linéaire. Mais la différence réside dans la manière dont ils stockent et accèdent aux données. Alors qu’un tableau stocke des éléments dans un bloc de mémoire contigu, une liste chaînée contient des éléments sous forme de nœuds, chaque nœud pointant vers l’élément suivant de la liste. En tant que tels, ils ne sont pas stockés de manière contiguë et les éléments ne sont pas accessibles à l’aide d’un index. Au lieu de cela, des pointeurs sont affectés à chaque nœud, qui dictent le nœud suivant dans la séquence. Comme avec un tableau dynamique, les listes liées peuvent être modifiées en ajoutant ou en supprimant des nœuds si nécessaire.
Quels sont les avantages ?
Maintenant que nous avons couvert exactement ce qu’est une liste chaînée, vous vous demandez peut-être pourquoi vous voulez en utiliser un. Voici quelques avantages :
À moins que vous n’utilisiez un tableau dynamique, la taille du tableau a tendance à être fixe, tandis que les listes chaînées peuvent être augmentées ou diminuées selon le cas. L’insertion ou la suppression d’éléments nécessite un temps constant, contrairement aux tableaux là où d’autres éléments devront être déplacés. Les listes liées ont tendance à être plus faciles sur vos contraintes de mémoire, en particulier avec de gros volumes de données. En effet, la mémoire n’est utilisée que pour les nœuds requis, mais la nature contiguë des tableaux signifie que vous pouvez prendre en charge certaines données dont vous n’avez pas besoin pour vos opérations. Il est plus facile de maintenir la persistance des données avec des listes liées, car les données peuvent être sérialisé plus facilement que dans les tableaux. Cela simplifie la transmission de données entre plusieurs programmes, ou après la fin des programmes. Lorsque vous avez des données éparses, c’est-à-dire avec des éléments vides, un tableau les stockerait toujours. Une liste liée, cependant, ne stocke que les valeurs qui ne sont pas vides.
Quels sont les différents types de listes liées ?
Il existe plusieurs types de listes liées que vous pouvez utiliser, chacune avec ses propres qualités. Nous allons donner un bref aperçu ici et comment les implémenter en Python.
Simple Linked List
Comme vous pouvez vous y attendre, il s’agit du type de liste chaînée le plus simple, où vous ne pouvez parcourir la liste que dans une seule direction. Chaque pointeur pointe vers le nœud suivant, le nœud final ne pointant vers rien, ou NULL. Ceci est également connu sous le nom de liste liée individuellement. Le code pour implémenter une simple liste chaînée en Python est le suivant :
class Node : def __init__(self, data): self.data=data self.next=None class LinkedList : def __init__(self): self. head=None def add(self, data): new_node=Node(data) if self.head est None: self.head=new_Node else: current_node=self.head while current_node.next is not None: current_node=current_node.next current_node.next=new_node def remove(self, data): if self.head est None: return if self.head.data==data: self.head=self.head.next return current_node=self.head tandis que current_node.next est not None : if current_node.next.data==data : current_node.next=current_node.next.next return def display(self): current_node=self.head while cur rent_node n’est pas None : print(current_node.data) current_node=current_node.next my_list=LinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(2) my_list.display
Explication
Ceci est un bloc de code assez étendu, mais pas trop difficile à comprendre.
Tout d’abord, nous définissons le”Node”et”LinkedList”Des classes. La classe « Node » représente un nœud dans la liste, chacun avec un pointeur (indiqué par « self.next »). La liste est représentée par”LinkedList”, et nous avons implémenté un nœud d’en-tête, qui permet une insertion ou une suppression plus facile d’éléments.
La fonction”add”indique qu’un nouveau nœud doit être ajouté à la fin de la liste. Si la liste est vide, le nœud d’en-tête est défini sur le nouveau nœud créé. Si elle n’est pas vide, la liste est parcourue jusqu’au dernier nœud et pointe vers le nouveau nœud.
La fonction”supprimer”fonctionne en supprimant le premier nœud de la liste. S’il s’agit du nœud d’en-tête, le nœud suivant devient alors le nœud d’en-tête. Si le nœud principal n’a pas les données données, alors la liste est parcourue pour les trouver. Une fois qu’il a trouvé le nœud avec les données données, son attribut « suivant » est défini sur le nœud suivant, ce qui supprime ce nœud de la liste.
« Afficher » parcourt la liste et imprime les données trouvées à chaque nœud.
Les données de la liste sont définies avec la classe”LinkedList”à la fin, avec des nœuds de valeurs de données 1, 2 et 3. Le nœud 2 a été supprimé pour montrer le processus de suppression, et les deux listes sont imprimées pour la sortie. Consultez la capture d’écran pour savoir comment cela fonctionne.
Les données de la liste sont définies avec la classe”LinkedList”à la fin, avec des nœuds de valeurs de données 1, 2 et 3.
©”TNGD”.com
Doublement Liste chaînée
Ceci est similaire à une liste simple, sauf que la traversée peut se produire dans les deux sens, vers l’avant et vers l’arrière. Pour implémenter cela, nous pouvons utiliser le code suivant :
class Node : def __init__(self, data): self.data=data self.prev=None self.next=None class DoublyLinkedList : def __init__(self): self.head=None self.tail=None def add(self,data): new_node=Node(data) if self.head est None: self.head=new_node self.tail=new_node else: new_node.prev=self.tail self.tail.next=new_node self.tail=new_node def remove(self, data): current_node=self.head while current_node is not None: if current_node.data==data: if current_node.prev is not None: current_node.prev.next=current_node.next sinon: self.head=current_node.next si current_node.next n’est pas None: current_node.next.prev=current_node.prev sinon: self.tail=current_node.prev return current_node=current_node.next def display(self): current_node=self.head tandis que current_node n’est pas None: print(current_node.data) current_node=current_node.next my_list=DoublyLinkedList() my_list. add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(3) my_list.display()
Explication
Une grande partie du code dans ce exemple est similaire, mais il y a quelques différences.
Nous définissons la classe”Node”d’une manière similaire, mais il y a des références au nœud précédent ainsi qu’au nœud suivant cette fois. De même, la classe”DoublyLinkedList”représente la liste mais a des instances fonctionnant à la fois comme tête et queue de la liste.
Comme avant, la fonction”add”ajoute un nouveau nœud à la fin de la liste. Mais si la liste est vide, alors la tête et la queue sont définies sur ce nouveau nœud. Lorsque la liste n’est pas vide, l’attribut « prev » du nouveau nœud est défini sur la queue actuelle, et l’attribut « next » de la queue actuelle sur le nouveau nœud, et la queue est remplacée par le nouveau nœud.
La fonction”supprimer”supprime le premier nœud de la liste avec les données données. Les attributs”prev”et”next”des nœuds adjacents sont mis à jour pour éviter le nœud actuel, le supprimant ainsi de la liste. Si le nœud en question est la tête ou la queue, alors cet attribut est également mis à jour pour refléter cela.
Enfin, les fonctions”display”et”my_list”sont en grande partie les mêmes, mais cette fois nous avons supprimé le nœud avec la valeur de données 3. Les captures d’écran illustrent l’exécution du code.
La fonction”add”ajoute un nouveau nœud à la fin de la liste.
©”TNGD”.com
Les fonctions”display”et”my_list”sont en grande partie les mêmes, mais cette fois nous’ai supprimé le nœud avec la valeur de données 3.
©”TNGD”.com
Listes circulaires liées
Un autre type de liste liée est une liste circulaire. Comme son nom l’indique, il s’agit d’une liste où il n’y a pas de”fin”. Le nœud de fin est reconnecté au nœud de début. Un exemple est vu avec le code suivant :
class Node : def __init__(self, data): self.data=data self.next=None class CircularLinkedList : def __init__(self): self.head=None def add (self, data): new_node=Node(data) if self.head est None: self.head=new_node new_node.next=self.head else: current_node=self.head tandis que current_node.next n’est pas self.head: current_node=current_node.next current_node.next=new_node new_node.next=self.head def remove(self,data): if self.head est None: return if self.head.data==data: current_node=self.head while current_node.next n’est pas self.head: current_node=current_node.next current_node.next=self.head.next self.head=self.head.next sinon: current_node=self.head alors que current_node.next n’est pas self.head : if current_node.next.data==data : current_node.next=current_node.next.next return current_node=current_node.next def display(self) : si self.head est Aucun : renvoie current_node=self.head tant que True : print(current_node.data) current_node=current_node.next si current_node est self.head : break my_list=CircularLinkedList() my_list.add(1) my_list.add(2) my_list.add (3) my_list.display()
Explication
Il y a quelques différences clés ici. Le”new_node.next=self.head”signifie que le nouveau nœud ajouté est le dernier nœud de la liste et pointe vers l’en-tête de la liste, qui est le premier nœud.
Le”tandis que current_node.next n’est pas self.head » est utilisée pour parcourir la liste chaînée et ajouter des éléments. Parce qu’il n’y a pas de vraie fin, comme avec la liste chaînée, nous devons vérifier si le nœud actuel est le nœud principal, plutôt que s’il est simplement non nul. Ceci afin d’éviter de changer le nœud principal.
Le code”new_node.next=self.head”garantit que le nœud ajouté à la liste est connecté au nœud principal.
Le La fonction”supprimer”fonctionne de manière similaire en ce que, si les données données sont contenues dans le premier nœud, elles sont supprimées et le nœud suivant devient le nouveau nœud principal. Si le nœud principal ne contient pas les données données, la liste est parcourue comme avant, jusqu’à ce que les données soient trouvées. L’attribut « suivant » est alors affecté au nœud après celui-ci, qui saute ce nœud. Dans l’ensemble, la fonction est la même, mais la mise en œuvre est un peu plus élaborée en raison de la nature circulaire de la liste.
La fonction”afficher”est également sensiblement la même, sauf qu’il faut vérifier que nous’commençons au nœud principal et interrompons la traversée une fois que nous atteignons à nouveau ce point.
Le code’new_node.next=self.head’garantit que le nœud ajouté à la liste est connecté au nœud principal.
©”TNGD”.com
L'”affichage”La fonction est également presque la même, mais nous devons commencer par le nœud principal et interrompre la traversée une fois que nous atteignons à nouveau ce point.
©”TNGD”.com
Listes liées circulaires doubles
Puisque nous avons examiné les listes liées simples, doubles et circulaires, cela n’a de sens e pour finir avec une double liste chaînée circulaire. Tout à fait la bouchée, mais pas tout à fait insaisissable. Comme on pouvait s’y attendre, cela fait référence à une liste chaînée circulaire que nous pouvons parcourir à la fois en avant et en arrière. L’implémentation de ce type de liste peut être illustrée comme suit :
class Node : def __init__(self, data): self.data=data self.next=None self.prev=None class DoubleCircularLinkedList : def__init__(self): self.head=None def add(self, data): new_node=Node(data) if self.head est None: new_node.next=new_node new_node.prev=new_node self.head=new_node else: last_node=self.head. prev last_node.next=new_node new_node.prev=last_node new_node.next=self.head self.head.prev=new_node def remove(self,data): si self.head est None: return current_node=self.head while current_node.data !=données : noeud_actuel=noeud_actuel.next si noeud_actuel==self.head : retour si noeud_actuel==self.head : se lf.head=current_node.next current_node.prev.next=current_node.next current_node.next.prev=current_node.prev def display(self): si self.head est None: return current_node=self.head while True: print(current_node.data) current_node=current_node.next if current_node==self.head: break my_list=DoubleCircularLinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display()
Explication
La principale différence entre une liste chaînée circulaire double et une liste chaînée circulaire standard est que, comme auparavant avec la liste chaînée non circulaire, la liste double pointe chaque nœud vers le nœud précédent ainsi que vers le nœud suivant. Ceci est réalisé en mettant à jour les attributs”prev”et”next”du dernier nœud et du nouveau nœud lors de l’ajout d’un nœud. Lors de la suppression d’un nœud, ces attributs du nœud supprimé et des nœuds adjacents doivent être mis à jour. Si vous supprimez le nœud principal, les pointeurs du dernier nœud doivent être mis à jour pour refléter cela.
La double liste pointe chaque nœud vers le nœud précédent ainsi que vers le nœud suivant.
©”TNGD”.com
Si vous supprimez le nœud principal , les pointeurs du dernier nœud doivent être mis à jour pour refléter cela.
©”TNGD”.com
Récapitulation
De nombreux types de listes liées peuvent être utilisés comme une alternative aux tableaux, par exemple lorsque vous devez insérer et supprimer des éléments régulièrement ou avez des contraintes de mémoire. Bien que les tableaux fonctionnent plus rapidement lorsqu’il s’agit de certaines opérations, les listes chaînées ne sont pas sans avantages uniques, il est donc utile de comprendre comment elles fonctionnent.
Suivant…
La liste chaînée FAQ sur la structure des données et son utilisation (Foire aux questions)
Qu’est-ce qu’une liste liée ?
Une liste liée est une structure de données dans laquelle les données est stocké dans des”nœuds”, et non de manière contiguë, comme avec un tableau. Ils peuvent être simples ou circulaires, ce dernier impliquant le dernier nœud pointant vers le nœud principal. Vous pouvez également implémenter des listes à double lien, où la traversée peut se produire en avant et en arrière dans la liste.
Quels sont les avantages et les inconvénients des listes liées ?
Les listes chaînées peuvent être meilleures que les tableaux lorsque vous devez insérer et supprimer fréquemment des données ou que vous avez des contraintes de mémoire. Cependant, un tableau peut être meilleur lorsque vous devez utiliser la recherche binaire et, comme ils sont contigus, ils sont plus compatibles avec le cache. Bien que l’insertion d’éléments soit plus rapide, l’accès à un élément particulier peut être plus lent car vous devez parcourir toute la liste.
Quels sont les différents types de listes liées ?
Les types de listes liées incluent les listes simples et doublement liées, et les listes liées circulaires et doublement circulaires.
Comment insérer ou supprimer un nœud d’une liste liée ?
Pour insérer un nœud, vous devez créer le nouveau nœud et pointer l’attribut « suivant » de ce nœud vers le nœud suivant dans la liste, ainsi que pointer l’attribut « suivant » du nœud précédent vers celui-ci nouveau nœud. Pour supprimer un nœud, vous devez parcourir la liste pour trouver les données données. Ensuite, vous devez faire pointer l’attribut”suivant”du nœud précédent vers le nœud devant le nœud que vous souhaitez supprimer, afin qu’il soit ignoré dans la liste.
Comment parcourez-vous un liste liée ?
Pour parcourir la liste, vous commencez par le nœud principal et passez à chaque nœud de la séquence jusqu’à ce que vous atteigniez le nœud final.
Quelle est la complexité temporelle des opérations de liste chaînée ?
Chaque opération a sa propre complexité temporelle. Les opérations avec une complexité temporelle de O(1) incluent l’insertion d’un élément au début et la suppression d’un élément au début. La plupart des autres opérations ont une complexité de O(n). Cela comprend l’accès à un élément, l’insertion ou la suppression d’un élément à la fin, l’insertion ou la suppression d’un élément à un index spécifique et la recherche d’un élément particulier. En effet, la liste doit être parcourue, la complexité dépend donc de la taille de la liste.
Quelles sont les alternatives aux listes liées ?
Au lieu de cela d’une liste chaînée, vous pouvez utiliser un tableau, où les données sont stockées dans un bloc contigu. Les tables de hachage sont utilisées pour mapper les clés aux indices dans un tableau, de sorte qu’elles puissent être utilisées conjointement les unes avec les autres. Ou, vous pouvez utiliser un arbre, où les nœuds sont connectés dans un format hiérarchique. Les tas sont un type d’arbre binaire et constituent une autre option. Enfin, les piles et les files d’attente peuvent être utilisées avec des tableaux ou des listes liées et, bien qu’elles ne soient pas aussi flexibles que certaines options, elles offrent une modification efficace des éléments.
Quelles sont certaines applications de listes liées ?
Les listes liées sont utiles lorsque vous ne connaissez pas la taille de la liste, souhaitez implémenter d’autres structures de données, dans le traitement d’images et de musique et pour représenter des graphiques et des arbres.