What is a Linked List?

Une liste chaînée est une séquence de valeurs où chaque valeur réside dans son propre nœud, et chaque nœud contient un pointeur vers le nœud suivant. La liste connaît son premier nœud (la tête) ; à partir de là, vous atteignez tous les autres nœuds en suivant la chaîne de pointeurs next.

Contrairement à un tableau, une liste chaînée n'a pas besoin d'un seul bloc de mémoire contigu. Ajouter un élément à la tête est en O(1) : il suffit de créer un nouveau nœud et de le faire pointer vers la tête actuelle. Le compromis est que l'accès au n-ième élément est en O(n), car nous devons parcourir la chaîne un nœud à la fois.

Les cinq opérations principales sur une liste chaînée sont :

1. AddFirst : Ajoute une valeur au début de la liste.
2. AddLast : Ajoute une valeur à la fin de la liste.
3. Get : Renvoie la valeur à un index donné.
4. Remove : Supprime la valeur à un index donné.
5. Size : Renvoie le nombre de valeurs actuellement stockées.

Créons d'abord une classe Node, puis construisons la LinkedList par-dessus !