Dans ce didacticiel, vous découvrirez la structure de données de liste chaînée et son implémentation en Python, Java, C et C ++.
Une structure de données de liste liée comprend une série de nœuds connectés. Ici, chaque nœud stocke les données et l'adresse du nœud suivant. Par exemple,
Structure de données LinkedList
Vous devez commencer quelque part, nous donnons donc à l'adresse du premier nœud un nom spécial appelé HEAD.
En outre, le dernier nœud de la liste liée peut être identifié car sa partie suivante pointe vers NULL.
Vous avez peut-être joué au jeu Treasure Hunt, où chaque indice comprend des informations sur l'indice suivant. C'est ainsi que fonctionne la liste chaînée.
Représentation de LinkedList
Voyons comment chaque nœud de LinkedList est représenté. Chaque nœud se compose:
- Un élément de données
- Une adresse d'un autre nœud
Nous enveloppons à la fois l'élément de données et la référence de nœud suivant dans une structure comme:
struct node ( int data; struct node *next; );
Comprendre la structure d'un nœud de liste chaînée est la clé pour bien le comprendre.
Chaque nœud struct a un élément de données et un pointeur vers un autre nœud struct. Créons une simple liste liée avec trois éléments pour comprendre comment cela fonctionne.
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data=3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;
Si vous ne comprenez aucune des lignes ci-dessus, tout ce dont vous avez besoin est un rappel sur les pointeurs et les structures.
En quelques étapes seulement, nous avons créé une simple liste chaînée avec trois nœuds.
Représentation LinkedList
La puissance de LinkedList vient de la capacité de rompre la chaîne et de la rejoindre. Par exemple, si vous vouliez mettre un élément 4 entre 1 et 2, les étapes seraient:
- Créez un nouveau nœud struct et allouez-lui de la mémoire.
- Ajoutez sa valeur de données à 4
- Pointez son pointeur suivant sur le nœud struct contenant 2 comme valeur de données
- Remplacez le pointeur suivant de "1" par le nœud que nous venons de créer.
Faire quelque chose de similaire dans un tableau aurait nécessité de déplacer les positions de tous les éléments suivants.
En python et Java, la liste chaînée peut être implémentée à l'aide de classes comme indiqué dans les codes ci-dessous.
Utilitaire de liste liée
Les listes sont l'une des structures de données les plus populaires et les plus efficaces, avec une implémentation dans tous les langages de programmation tels que C, C ++, Python, Java et C #.
En dehors de cela, les listes liées sont un excellent moyen d'apprendre comment fonctionnent les pointeurs. En vous entraînant à manipuler des listes chaînées, vous pouvez vous préparer à apprendre des structures de données plus avancées telles que des graphiques et des arbres.
Implémentations de listes liées dans des exemples Python, Java, C et C ++
Python Java C C + # Linked list implementation in Python class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print the linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next
// Linked list implementation in Java class LinkedList ( // Creating a node Node head; static class Node ( int value; Node next; Node(int d) ( value = d; next = null; ) ) public static void main(String() args) ( LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) ( System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; ) ) )
// Linked list implementation in C #include #include // Creating a node struct node ( int value; struct node *next; ); // print the linked list value void printLinkedlist(struct node *p) ( while (p != NULL) ( printf("%d ", p->value); p = p->next; ) ) int main() ( // Initialize nodes struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); )
// Linked list implementation in C++ #include using namespace std; // Creating a node class Node ( public: int value; Node* next; ); int main() ( Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; // allocate 3 nodes in the heap one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // print the linked list value head = one; while (head != NULL) ( printf("%d ", head->value); head = head->next; ) )
Complexité de la liste liée
Complexité temporelle
| Pire cas | Cas moyen | |
|---|---|---|
| Chercher | Sur) | Sur) |
| Insérer | O (1) | O (1) |
| Effacement | O (1) | O (1) |
Complexité spatiale: O (n)
Applications de liste liées
- Allocation de mémoire dynamique
- Implémenté dans la pile et la file d'attente
- In Annuler la fonctionnalité des logiciels
- Tables de hachage, graphiques
Lectures recommandées
1. Tutoriels
- Opérations LinkedList (Traverser, Insérer, Supprimer)
- Types de LinkedList
- Liste LinkedList Java
2. Exemples
- Obtenez l'élément central de LinkedList en une seule itération
- Convertir la LinkedList en un tableau et vice versa
- Détecter la boucle dans une LinkedList
