Liste à chaînage unique dans les structures de données
Sarah Chen
Qu'est-ce qu'une liste à lien unique ?
La liste à liaison unique est une structure de données linéaire et unidirectionnelle, dans laquelle les données sont enregistrées sur les nœuds et chaque nœud est connecté via un lien à son nœud suivant. Chaque nœud contient un champ de données et un lien vers le nœud suivant. Les listes à chaînage unique peuvent être parcourues dans une seule direction, tandis que les listes à chaînage double peuvent être parcourues dans les deux sens.
Voici une structure de nœuds d'une liste à lien unique :
Pourquoi utiliser une liste chaînée plutôt qu'un tableau ?
Il existe plusieurs cas où il est préférable d'utiliser la liste chaînée plutôt que la tableau. Voici quelques scénarios :
- Nombre d'éléments inconnu : Lorsque vous ne savez pas combien d'éléments vous devez stocker pendant l'exécution du programme, vous pouvez utiliser la liste chaînée. La mémoire est allouée dynamiquement à mesure que vous ajoutez des éléments aux listes chaînées.
- Accès aléatoire: Dans un scénario où vous n'avez pas besoin d'utiliser l'accès aléatoire aux éléments, vous pouvez utiliser la liste chaînée.
- Insertion au milieu : L'insertion au milieu d'un tableau est une tâche complexe. Parce qu’il faut pousser les autres éléments vers la droite. Cependant, une liste chaînée vous permet d'ajouter un élément à n'importe quelle position de votre choix.
Operation de liste à chaînage unique
La liste à liaison unique est idéale pour l'allocation dynamique de mémoire. Il fournit toutes les opérations de base de la liste chaînée, c'est-à-dire l'insertion, la suppression, la recherche, la mise à jour, la fusion de deux listes chaînées, le parcours, etc.
Nous allons discuter ici du fonctionnement suivant de la liste chaînée :
- Insertion en tête
- Insertion à la queue
- Insérer après un nœud
- Insérer avant un nœud
- Supprimer le nœud principal
- Supprimer le nœud de queue
- Rechercher et supprimer un nœud
- Parcourir la liste chaînée
Voici un exemple de liste chaînée avec quatre nœuds.
Insertion en tête d'une liste à chaînage unique
Il s'agit d'une opération simple. Généralement, cela s’appelle pousser une liste à chaînage unique. Vous devez créer un nouveau nœud et le placer en tête de la liste chaînée.
Pour effectuer cette opération, nous devons respecter deux conditions importantes. Ils sont
- Si la liste est vide, alors le nœud nouvellement créé sera le nœud principal et le nœud suivant de la tête sera « NULL ».
- Si la liste n'est pas vide, le nouveau nœud sera le nœud principal et le suivant pointera vers le nœud principal précédent.
Voici le pseudo-code pour insérer un nœud en tête d'une liste chaînée :
function insertAtHead( head, value ): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
Insertion à la fin d'une liste à lien unique
L'insertion d'un nœud à la fin d'une liste chaînée présente certaines similitudes avec l'insertion dans l'en-tête. Tout ce que vous avez à faire est de passer au nœud final ou au nœud de queue. Pointez ensuite le nœud « suivant » du nœud final vers le nœud nouvellement créé. Si le nœud principal est nul, le nouveau nœud sera le nœud principal.
Voici les étapes :
Étape 1) Parcourez jusqu'à ce que le nœud « suivant » du nœud actuel devienne nul.
Étape 2) Créez un nouveau nœud avec la valeur spécifiée.
Étape 3) Attribuez le nouveau nœud comme nœud suivant du nœud de queue.
Le pseudo-code pour insérer un nœud en queue d'une liste unique :
function insertAtEnd( head, value ): newNode = Node(value) if head is NULL: head = newNode return head while head.next is not NULL: then head = head.next head.next = newNode newNode.next = NULL
Insertion après un nœud dans une liste à chaînage unique
L'insertion après un nœud comporte deux parties : rechercher le nœud et attacher après le nœud recherché. Nous devons parcourir tous les nœuds. Pour chaque nœud, nous devons faire correspondre l'élément de recherche. S'il y a une correspondance, nous ajouterons le nouveau nœud après le nœud recherché.
Voici les étapes :
Étape 1) Parcourez le nœud suivant jusqu'à ce que la valeur du nœud actuel soit égale à l'élément de recherche.
Étape 2) Le prochain pointeur du nouveau nœud sera le prochain pointeur du nœud actuel.
Étape 3) Le prochain nœud du nœud actuel sera le nouveau nœud.
Voici le pseudo-code pour insérer un nœud après un nœud :
function insertAfter( head, value, searchItem ): newNode = Node(value) while head.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
Insertion avant un nœud dans une liste à chaînage unique
Cette fonction est très similaire à l'insertion après un nœud. Nous devons créer un nouveau nœud et parcourir la liste chaînée jusqu'à ce que le nœud actuel corresponde au nœud de recherche. Après cela, nous ajouterons le nouveau nœud comme nœud précédent du nœud actuel.
Voici les étapes :
Étape 1) Parcourez jusqu'à ce que la valeur du nœud suivant soit égale à l'élément de recherche.
Étape 2) Créez un nouveau nœud et attribuez le « suivant » du nœud au prochain nœud suivant du nœud actuel.
Étape 3) Attribuez le nouveau nœud comme nœud suivant du nœud actuel.
Voici le pseudo-code :
function insertBefore( head, value, searchItem ): newNode = Node(value) while head.next.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
Supprimer l'en-tête de la liste à lien unique
Dans chaque fonction de la liste chaînée, le pointeur de tête est fourni comme paramètre. Vous devez supprimer le nœud principal et faire du nœud suivant du nœud principal le nouveau tête de la liste chaînée. Nous devons également libérer la mémoire du nœud supprimé. Sinon, la mémoire sera marquée comme occupée lorsqu'un autre programme tentera d'y accéder.
Voici les étapes à suivre pour supprimer l'en-tête de la liste à lien unique :
Étape 1) Attribuez le nœud suivant du nœud principal comme nouveau nœud principal.
Étape 2) Libérez la mémoire allouée par le nœud principal précédent.
Étape 3) Renvoie le nouveau nœud principal.
Le pseudo-code de suppression du nœud principal :
function deleteHead( head ): temp = head head = head.next free( temp ) return head
Supprimer la fin de la liste à chaînage unique
La suppression du nœud de queue est plus familière avec la suppression du nœud de tête. La différence est que nous devons aller jusqu'à la fin de la liste chaînée et la supprimer. Dans la liste à chaînage unique, le nœud avec le nœud suivant comme « NULL » est le nœud de queue.
Voici les étapes à suivre pour supprimer le nœud de queue de la liste chaînée :
Étape 1) Traversez avant le nœud de queue. Enregistrez le nœud actuel.
Étape 2) Libérez la mémoire du nœud suivant du nœud actuel.
Étape 3) Définissez le nœud suivant du nœud actuel sur NULL.
Voici le pseudo-code pour supprimer le nœud de queue :
function deleteTail( head ): while head.next.next is not NULL: head = head.next free( head.next ) head.next = NULL
Rechercher et supprimer un nœud d'une liste à lien unique
Cette fonction a deux tâches, rechercher et supprimer. Nous devons rechercher jusqu'à la fin des listes à lien unique. Si nous trouvons un nœud similaire, nous le supprimerons. Après cela, nous devons fusionner ou lier les nœuds gauche et droit du nœud supprimé. Voici les étapes à suivre pour ce faire :
Étape 1) Parcourez jusqu'à la fin de la liste chaînée. Vérifiez si le nœud actuel est égal au nœud de recherche ou non.
Étape 2) Si un nœud correspond, stockez le pointeur de nœud sur le nœud actuel.
Étape 3) Le « suivant » du nœud précédent sera le nœud suivant du nœud actuel.
Étape 4) Supprimez et libérez la mémoire du nœud actuel.
Pseudo-code pour rechercher et supprimer un nœud d'une liste à lien unique :
function searchAndDelete( head, searchItem ): while head.next.next is not NULL and head.next.value is not equals searchItem : head = head.next head.next = head.next.next delete(head.next)
Parcourez une liste à chaînage unique
Une liste chaînée unique n'a que la fonctionnalité permettant de parcourir la tête vers la queue. Il n'y a aucun pointeur vers le nœud précédent ; c'est pourquoi nous ne pouvons pas parcourir la liste à chaînage unique dans l'ordre inverse. Nous allons parcourir chaque nœud et imprimer la valeur du nœud actuel jusqu'à ce que nous obtenions null.
Voici les étapes :
Étape 1) Parcourez chaque nœud jusqu'à ce que nous obtenions null comme nœud suivant.
Étape 2) Imprime la valeur du nœud actuel.
Pseudo-code pour parcourir une liste à chaînage unique :
function traverse( head ): while head.next is not NULL: print the value of the head head = head.next
Exemple de liste à lien unique dans C++
#include<iostream>
using namespace std;
struct Node{
int data;
struct Node *next;
};
void insertAtHead(Node* &head, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
if(head!=NULL){
newNode->next = head;
}
head = newNode;
cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
if(head==NULL){
insertAtHead(head,value);
}
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *temp = head;
while(temp->next!=NULL){
temp = temp->next;
}
temp->next = newNode;
cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
Node *temp = new Node();
if( (*headPtr)->data == searchItem ){
temp = *headPtr;
*headPtr = (*headPtr)->next;
free(temp);
}else{
Node *currentNode = *headPtr;
while(currentNode->next != NULL){
if(currentNode->next->data == searchItem){
temp = currentNode->next;
currentNode->next = currentNode->next->next;
free(temp);
}else{
currentNode = currentNode->next;
}
}
}
cout<<"Deleted Node\t"<<searchItem<<endl;
return;
}
void insertAfter(Node * &headPtr, int searchItem, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *head = headPtr;
while(head->next!=NULL && head->data!=searchItem){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node * &headPtr, int searchItem, int value){
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
Node *head = headPtr;
while(head->next!=NULL && head->next->data!=searchItem){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
Node* tempNode = new Node();
tempNode = headPointer;
cout<<"Traversal from head:\t";
while(tempNode !=NULL){
cout<<tempNode->data;
if(tempNode->next)
cout<<" --> ";
tempNode = tempNode ->next;
}
cout<<endl;
}
int main(){
Node *head = NULL;
insertAtHead(head,5);
insertAtHead(head,6);
insertAtHead(head,7);
insertEnd(head,9);
traverse(head);
searchAndDelete(&head,6);
traverse(head);
insertAfter(head,7,10);
insertBefore(head,9,11);
traverse(head);
}
Sortie :
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Traversal from head: 7 → 6 → 5 → 9 Deleted Node 6 Traversal from head: 7 → 5 → 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversal from head: 7 → 10 → 5 → 11 → 9
Exemple de liste à lien unique dans Python Programme
class Node:
def __init__(self,data = None, next = None):
self.data = data
self.next = next
class SinglyLinkedList:
def __init__(self):
self.head = None
def insertAtHead(self, value):
newNode = Node(data=value)
if self.head is not None:
newNode.next = self.head
self.head = newNode
print(f'Added {newNode.data} at the front.')
return
def insertAtEnd(self,value):
if self.head is None:
self.insertAtHead(value)
newNode = Node(value)
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = newNode
print(f'Added {newNode.data} at the end.')
def searchAndDelete(self,searchItem):
temp = Node()
if self.head is searchItem:
temp = self.head
self.head = self.head.next
else:
currentNode = self.head
while currentNode.next is not None:
if currentNode.next.data is searchItem:
temp = currentNode.next
currentNode.next = currentNode.next.next
else:
currentNode = currentNode.next
print(f'Deleted node\t{searchItem}')
return
def insertAfter(self,searchItem,value):
newNode = Node(data=value)
temp = self.head
while temp.next is not None and temp.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
print(f'Inserted {value} after node\t{searchItem}')
return
def insertbefore(self,searchItem,value):
newNode = Node(data=value)
temp = self.head
while temp.next is not None and temp.next.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
print(f'Inserted {value} before node\t{searchItem}')
return
def traverse(self):
temp = self.head
print("Traversing from head:\t",end="")
while temp:
print("{}\t".format(temp.data),end="")
temp = temp.next
print()
SinglyLinkedList = SinglyLinkedList()
SinglyLinkedList.insertAtHead(5)
SinglyLinkedList.insertAtHead(6)
SinglyLinkedList.insertAtHead(7)
SinglyLinkedList.insertAtEnd(9)
SinglyLinkedList.traverse()
SinglyLinkedList.searchAndDelete(6)
SinglyLinkedList.traverse()
SinglyLinkedList.insertAfter(7,10)
SinglyLinkedList.insertbefore(9, 11)
SinglyLinkedList.traverse()
Sortie :
Added 5 at the front. Added 6 at the front. Added 7 at the front. Added 9 at the end. Traversing from head: 7 6 5 9 Deleted node 6 Traversing from head: 7 5 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversing from head: 7 10 5 11 9
Complexité de la liste à chaînage unique
Il existe deux types de complexité : la complexité temporelle et la complexité spatiale. La complexité temporelle du pire et du cas moyen est la même pour la liste à chaînage unique.
La complexité temporelle pour le meilleur des cas:
- L'insertion dans la tête peut se faire en O(1). Comme nous n’avons pas besoin de parcourir l’intérieur de la liste chaînée.
- L'opération de recherche et de suppression peut être effectuée dans O(1) si l'élément de recherche est présent dans le nœud principal.
La complexité temporelle pour le cas moyen :
- L'insertion dans une liste chaînée prendra O(n) si « n » éléments sont présents dans la liste chaînée unique.
- La recherche et la suppression peuvent également prendre O(n), car l'élément de recherche peut être présent dans le nœud de queue. Dans ce cas, vous devez parcourir toute la liste.
Complexité spatiale d'une liste à chaînage unique
La liste à chaînage unique alloue dynamiquement de la mémoire. Si nous voulons stocker n éléments, il allouera n unité de mémoire. Ainsi, la complexité spatiale est O(n).
