3 minutes
Listes Chaînées et Leurs Utilisations
Dernière mise à jour: 6 octobre, 2022Les listes chaînées sont des structures de données simples composées de deux parties principales. Une partie qui contient les données réelles et une autre pour les informations sur l'élément de liste suivant. Il existe 3 principaux types de listes liées ; listes liées simples, listes doublement liées et listes liées circulaires qui. Habituellement, les listes liées ont une partie qui agit comme tête, vous pouvez choisir de "terminer" vos listes liées par une queue ou vous pouvez également l'utiliser vide. Une représentation visuelle simple pour une liste à liens simples ressemblerait à ceci :
Il existe différentes méthodes pour créer des listes chaînées dans différentes langues. Je vais créer des listes liées en python car python est vraiment facile à apprendre et à comprendre.
§Commençons
Tout d'abord, comment créer réellement une liste chaînée ? Chaque élément de la liste chaînée est appelé node. Chaque nœud (node) sera composé de deux des deux parties comme nous l'avons dit ci-dessus. Une partie pour les données et une autre pour l'adresse du nœud suivant. Voici comment j'ai créé le nœud :
class Node:
def __init__(self, data):
self.data = data
self.next = None
Pour la liste chaînée réelle, nous allons créer une autre classe python. J'ai codé le mien afin que nous devions informer nous-mêmes notre liste liée de la tête. Vous pouvez le coder de manière à ce qu'il obtienne automatiquement la tête (et peut-être aussi le nœud de queue) des nœuds donnés.
§Insertion
Comme dans toute structure qui ressemble à une chaîne, vous pouvez rompre le lien de n'importe quelle partie pour insérer un nœud en temps constant. La création de ce comportement dans un tableau/une liste prendrait potentiellement du temps O(N). Disons que vous avez ce tableau :
arr = [4, 5, 1, 6, 2]
Ok maintenant, nous voulons insérer 3 en deuxième position python arr[1] = 3. À la fin de l'insertion, notre tableau/liste ressemblera à ceci :
arr = [4, 3, 5, 1, 6, 2]
Pour ce faire, nous avons poussé chaque élément d'un index vers la droite et ouvert un espace pour la valeur 3. C'est la cause de la complexité en temps O(N).
Dans une liste chaînée, il serait plus facile d'obtenir la même chose car il suffit de rompre le lien entre deux nœuds et d'ajouter un nœud entre eux avec de nouveaux liens. La complexité temporelle de cette opération est constante (O(N)). Un visuel nous aiderait probablement à mieux comprendre cela :
La suppression serait aussi simple que de supprimer les liens. Nous sélectionnons le nœud précédent du nœud que nous voulons supprimer et faisons pointer ce nœud vers le nœud après le nœud que nous voulons supprimer. De cette façon, nous le sautons simplement dans la chaîne. Une représentation visuelle peut être trouvée ci-dessous:
§Deletion
La suppression dans une liste chaînée prend un temps constant (O(1)) alors que dans une liste/un tableau cela prendrait un temps linéaire (O(N)). Dans une liste, nous supprimerions l'élément / la valeur de la liste et déplacerions chaque élément de la liste d'un index à gauche.
§Le Code Pour La Liste Liée
Le code complet de la structure de données de la liste chaînée ressemblera à ceci. J'ai écrit ce code pour pratiquer des actions sur des listes chaînées. Vous pouvez voir qu'il couvre la plupart des actions que vous voudriez faire dans une liste chaînée :
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = Node
def is_empty(self):
size = 0
temp = self.head
while temp:
size += 1
temp = temp.next
print("is it empty: ", bool(size == 0))
def front(self):
return self.head.data
def back(self):
temp = self.head
while temp.next is not None:
temp = temp.next
return temp.data
def get_size(self):
size = 0
temp = self.head
while temp:
size += 1
temp = temp.next
print("size is: ", size)
return size
# aller une par une imprimer les valeurs
def print_list(self):
temp = self.head
while temp:
print(temp.data)
temp = temp.next
def value_at(self, index):
temp = self.head
nth = 0
while temp:
if index != nth:
nth += 1
temp = temp.next
else:
print(index, "la nième valeur de l'élément est :", temp.data)
return
def push_front(self, value):
to_add = Node(value)
temp = self.head
self.head = to_add
to_add.next = temp
def pop_front(self):
self.head = self.head.next
def push_back(self, value):
to_add = Node(value)
temp = self.head
while temp.next:
temp = temp.next
temp.next = to_add
def pop_back(self):
temp = self.head
while temp.next.next is not None:
temp = temp.next
print("removed: ", temp.next.data)
temp.next = None
def insert(self, index, value):
to_insert = Node(value)
temp = self.head
nth = 0
while temp:
if nth == index:
old_temp_next = temp.next
to_insert.next = old_temp_next
temp.next = to_insert
temp = temp.next
nth += 1
def erase(self, index):
if index < 0:
print('l\'index ne peut pas être négatif')
if index == 0:
self.pop_front()
nth = 1
prev = self.head
current = self.head.next
while current:
if index == nth:
prev.next = current.next
current.next = None
return
nth += 1
prev = current
current = current.next
print("out of bounds")
# value_n_from_end(n) - renvoie la valeur du nœud à la nième position à partir de la fin de la liste
# J'ai décidé de commencer l'indexation à partir de 0, donc le zéro est le dernier
def value_n_from_end(self, index):
nth = 1
size = self.get_size()
wanted = size - index
current = self.head
if wanted == 0:
print("les données recherchées sont: ", current.data)
return current.data
while current:
if nth == wanted:
print("retour: ", current.data)
return current.data
current = current.next
nth += 1
# Aller avec la manière itérative de le faire parce que la complexité de l'espace est O (1)
# def reverse(self): # Temps itératif O(n), espace O(1)
# prev = None
# current = self.head
# while(current):
# next = current.next
# current.next = prev
# prev = current
# current = next
# # print("current", current.data)
# self.head = prev
def reverse(self, node): # recursive time O(n), space O(n)
if node is None:
print("node is:", node.data)
return node
if node.next is None:
print("node is, no next:", node.data)
self.head = node
return node
node1 = self.reverse(node.next) # appeler récursivement jusqu'à ce que nous atteignions la base
node.next.next = node # pointe vers lui-même
node.next = None
return node1
# remove_value(value) - supprime le premier élément de la liste avec cette valeur
def remove_value(self, value):
current = self.head
prev = None
if self.head.data == value:
self.head = self.head.next
while current:
if current.data == value:
prev = current
current = current.next
prev.next = current
prev = current
current = current.next
if __name__ == '__main__':
# initialiser avec une liste vide
s_l_list = LinkedList()
# le premier nœud, je dois définir la tête
s_l_list.head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
fifth = Node(3)
# chain' em up
s_l_list.head.next = second
second.next = third
third.next = fourth
fourth.next = fifth
# s_l_list.print_list()
# s_l_list.get_size()
# s_l_list.is_empty()
# s_l_list.value_at(0)
# s_l_list.value_at(2)
# s_l_list.push_back(5)
# s_l_list.print_list()
# s_l_list.push_back(6)
# s_l_list.print_list()
# s_l_list.pop_back()
# s_l_list.print_list()
# s_l_list.push_front(0)
# s_l_list.print_list()
# s_l_list.pop_front()
# s_l_list.print_list()
# print(s_l_list.front())
# print(s_l_list.back())
# s_l_list.print_list()
# s_l_list.insert(1, 77)
# s_l_list.print_list()
# s_l_list.erase(2)
# s_l_list.print_list()
# s_l_list.value_n_from_end(0)
# s_l_list.reverse()
# s_l_list.print_list()
# s_l_list.reverse(s_l_list.head) # appeler la méthode avec la tête actuelle
# s_l_list.print_list()
s_l_list.remove_value(1)
s_l_list.print_list()
Vous pouvez décommenter les lignes commentées afin de tester différentes parties et les actions que vous pouvez effectuer sur la liste liée. Allez tester !
§Conclusion et Utilisations des Listes Liées
Vous pouvez envisager d'utiliser des listes liées lorsque :
- Vous avez besoin d'un temps constant dans les opérations d'insertion et de suppression sur de très gros ensembles de données.
- Vous ne savez pas vraiment combien d'éléments votre tableau/liste va contenir. A chaque insertion/suppression dans un tableau, votre tableau est recréé dans la mémoire. Cela peut ne pas sembler être un problème lorsque vous travaillez avec des langages tels que JavaScript et Python, car nous n'avons pas besoin de définir une taille lorsque nous créons notre tableau/liste.
- Vous devez créer une file d'attente comme des structures de données dans lesquelles l'ordre compte.
Il existe bien sûr de nombreux autres avantages et si vous souhaitez approfondir, je vous suggère de lire [cet article] (https://www.javatpoint.com/application-of-linked-list). C'est un peu difficile à lire, mais je pense qu'après avoir lu mon article ici, vous devriez pouvoir comprendre facilement celui-là aussi.
Continuez d'apprendre!
Ilker AkbiyikTable Des Matières
Articles Similaires
