Une **liste chaînée** est une structure de données composée d'une séquence d'éléments appelés **nœuds**, où chaque nœud contient des données et une **référence** au nœud suivant dans la séquence.     
Contrairement aux tableaux, les listes chaînées **n'ont pas de taille fixe en mémoire** et **ne stockent pas les éléments dans des emplacements mémoire contigus**. Au lieu de cela, elles utilisent des pointeurs pour connecter les nœuds, permettant une allocation dynamique de mémoire et une insertion et suppression efficaces des éléments.

La section suivante du code illustre ce concept.

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Linked List vs Array Comparison</title>
<style>
    table {
        width: 80%;
        margin: 20px auto;
        border-collapse: collapse;
        border: 1px solid #ddd;
    }

    th,
    td {
        padding: 10px;
        text-align: left;
    }

    th {
        background-color: #f2f2f2;
    }

    tr:nth-child(even) {
        background-color: #f2f2f2;
    }

    tr:hover {
        background-color: #ddd;
    }

    th strong {
        font-weight: bold;
    }

    td strong {
        font-weight: bold;
    }
</style>
</head>
<body>

<table>
    <tr>
        <th><strong>Feature</strong></th>
        <th><strong>Linked List</strong></th>
        <th><strong>Array</strong></th>
    </tr>
    <tr>
        <td><strong>Dynamic Size</strong></td>
        <td>Linked lists can dynamically grow or shrink in size by allocating or deallocating memory for nodes.</td>
        <td>Arrays have a fixed size defined at the time of declaration and cannot easily change size during runtime.</td>
    </tr>
    <tr>
        <td><strong>Memory Allocation</strong></td>
        <td>Each node in a linked list occupies memory dynamically, allowing for efficient memory usage.</td>
        <td>Arrays store elements in contiguous memory locations, which may lead to memory wastage or insufficient memory for large arrays.</td>
    </tr>
    <tr>
        <td><strong>Insertion/Deletion</strong></td>
        <td>Linked lists offer efficient insertion and deletion operations by adjusting pointers.</td>
        <td>Arrays may require shifting elements to accommodate insertions or deletions in the middle, resulting in less efficient operations.</td>
    </tr>
    <tr>
        <td><strong>Random Access</strong></td>
        <td>Linked lists do not support efficient random access to elements, requiring traversal from the beginning to locate an element.</td>
        <td>Arrays support efficient random access to elements using indexing, allowing direct access to any element in constant time.</td>
    </tr>
    <tr>
        <td><strong>Traversal</strong></td>
        <td>Linked lists require traversal from the beginning to the desired position, which may result in slower access time for large lists.</td>
        <td>Arrays allow for fast traversal using indexing, providing efficient access to elements at any position.</td>
    </tr>
</table>

</body>
</html>


from lolviz import *
from IPython.display import display_png

class Node:

  def __init__(self, data):
    self.value = data
    self.next = None

# Let's create some nodes
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

# Then let's couple them into a linked list
node1.next = node2
node2.next = node3

display_png(objviz(node1))

>Remarque
>
>Faites attention au fait que la structure `list` intégrée de Python n'est pas conceptuellement une liste - la structure `list` est implémentée comme un **tableau dynamique** qui peut contenir des éléments de différents types de données. Elle est similaire à un tableau mais avec des fonctionnalités et optimisations supplémentaires.

Contrairement à un tableau où nous avons un accès direct à n'importe quel élément, dans la liste chaînée, nous avons **un accès direct uniquement au premier élément**, et nous pouvons accéder à tout autre élément uniquement par la chaîne de références.

Dans une liste chaînée, quel est le but du pointeur "next" ?

La compréhension des structures de données et des algorithmes : c'est ce qui distingue les professionnels avancés des autres. Dans le monde moderne des données croissantes, il est très important de pouvoir traiter de grandes quantités de données efficacement. 

Dans ce cours, vous étudierez les structures de données les plus basiques qui nous aident à gérer d'énormes quantités de données ainsi qu'à implémenter les concepts les plus basiques et cruciaux par vous-même afin que vous obteniez une compréhension plus profonde de la façon dont chaque structure de données fonctionne et que vous puissiez décider quelle structure de données est la mieux adaptée à votre tâche.

Lorsque nous commençons à apprendre quelque chose de nouveau, il est très important de se familiariser d'abord avec le sujet de notre étude. Alors plongeons plus profondément dans ce que nous allons apprendre dans ce cours.

Les tableaux et les listes servent de structures de données fondamentales en programmation, avec une utilisation intensive en Python. Cette section offre un aperçu de ces structures, en explorant leurs concepts et en mettant en lumière leurs nuances d'implémentation dans le langage de programmation Python.

Il existe de nombreuses tâches appliquées dans lesquelles il est nécessaire de manipuler de grandes quantités de données structurées et des structures de données simples telles qu'un array ou une liste chaînée peuvent ne plus suffire à ces fins. Dans cette section, nous examinerons le concept de type de données abstrait et comment différents ADT nous permettent de gérer efficacement de grandes quantités de données.

Dans le monde réel, on doit souvent faire face à des tâches où il est nécessaire de modéliser des dépendances complexes entre divers nœuds d'un système ou d'un domaine. Les graphes peuvent nous aider à cela. Dans cette section, nous apprendrons ce qu'est un graphe et comment le représenter efficacement en mémoire informatique.

Aperçu des Algorithmes et des Structures de Données

Structure de Données de Liste Chaînée

Liste chaînée vs Tableau

Implémentation de la liste chaînée