{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# POO2 - Structure de liste chaînée\n",
    "\n",
    "> Cours NSI Terminale - Thème 1.\n",
    "\n",
    "- toc: true \n",
    "- badges: true\n",
    "- comments: false\n",
    "- categories: [python, NSI, Terminale, Structure_donnees, TP]\n",
    "- image: images/nsi1.png"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Les listes chaînées\n",
    "\n",
    "## Description de la structure\n",
    "\n",
    "On rappelle que la structure d'une liste chaînée ressemble à ceci :\n",
    "![Liste chainée](my_icons/listechainee.svg)\n",
    "\n",
    "L'illustration montre une liste chaînée composée de 4 maillons. Chaque maillon est composé de 2 champs : une valeur et un pointeur vers le maillon suivant.\n",
    "\n",
    "Pour implémenter une liste chaînée en python nous pourrions utiliser \n",
    "- un tableau à 2 éléments décrivant un maillon\n",
    "    - le premier élément du tableau est la valeur du maillon\n",
    "    - le second élément est l'indice du maillon suivant (ou None pour le dernier élément)\n",
    "- un tableau constitué de la liste de tous les maillons\n",
    "\n",
    "La liste chaînée donnée en illustration pourrait donc être représentée ainsi : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3c78e5f7d4ac69497d88790b83bf2068",
     "grade": false,
     "grade_id": "cell-f6191439ce8d1247",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "maillons = [[3, 2], [8,None], [5, 1], [2,0]]\n",
    "premier = 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "2fee6a0b62927d9b81b30b674d565976",
     "grade": false,
     "grade_id": "cell-61efd5b783041ffd",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Vous constaterez que j'ai *volontairement* inscrit dans le tableau `maillons` les éléments de la liste dans le désordre car il n'y a aucune raison que l'ordre des éléments corresponde à l'ordre dans le tableau `maillons` si par exemple on insère en cours de route des éléments au milieu de la liste. \n",
    "\n",
    "la variable `premier` contient l'indice du premier élément de la liste, c'est donc le maillon `[2,0]` correspondant à la valeur 2. L'élément suivant sera le maillon à l'indice 0 dans le tableau donc `[3,2]` dont la valeur est 3. Ensuite on accède au maillon d'indice 2 donc `[5,1]` de valeur 5 pour terminer par le maillon `[8,None]` de valeur 8 marquant la fin de la liste. Au final la liste est donc bien $$2 - 3 - 5 - 8$$\n",
    "\n",
    "Cette approche a le mérite de se baser sur des types python standard que vous conaissez bien mais nous avons besoin de **deux variables** pour décrire un seul *objet*\n",
    "- le tableau contenant les maillons\n",
    "- l'indice du premier élément de la liste chaînée dans notre tableau\n",
    "\n",
    "Cela alourdit énormément l'écriture des programmes que d'avoir un *objet* unique décrit par deux variables distinctes. Il y a moyen de faire beaucoup mieux grâce à la structure d'objets.\n",
    "\n",
    "Dans ce TP, nous allons créer une classe **ListeChainee** permettant de créer et manipuler des objets de type liste chaînée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "7a2c06a8077741418b3b918f04ace2ab",
     "grade": false,
     "grade_id": "cell-530046415fc16854",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class ListeChainee:\n",
    "    \"\"\"Implementation d'une liste chaînée\"\"\"\n",
    "    def __init__(self, maillons=[], premier=None):\n",
    "        \"\"\"Initialisation de la liste chainée\"\"\"\n",
    "        # tableau contenant les maillons de la liste\n",
    "        self.__maillons = maillons\n",
    "        # indice du premier élément.\n",
    "        self.__premier = premier # None lorsque la liste est vide"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "d178122365201d9148dcb4a7574052a5",
     "grade": false,
     "grade_id": "cell-8bf17601a2564256",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Comme vous le voyez, la classe **ListeChainee** regroupe en un seul objet les deux informations nécessaires à la gestion de notre liste chaînée à savoir\n",
    "- les maillons qui sont une liste au format que nous venons de décrire\n",
    "- l'indice du premier élément\n",
    "\n",
    "Nous utilisons ici des *paramètres optionnels* qui permettent le cas échéant d'initialiser notre liste chaînée avec du contenu. \n",
    "\n",
    "## Propriété privée - défense d'entrer !\n",
    "\n",
    "Parfois nous ne voulons pas qu'il soit possible de modifier les valeurs des propriétés d'une classe autrement qu'en passant par les méthodes de la classe afin de préserver la cohérence des données.\n",
    "\n",
    "Afin de protéger les propriétés d'un objet, on ajoute **__** devant leur nom. Ainsi, elles ne seront accessibles que depuis les méthodes de la classe, pas au travers des instances de l'objet. On parle alors de propriétés *privées* (sous python, elles sont plutôt* cachées*)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "78be9209bc614da52c01e52cd5d23c1e",
     "grade": false,
     "grade_id": "cell-4ec5ae0b3fefed35",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## A vous de jouer\n",
    "\n",
    "Vous allez devoir implémenter les méthodes suivantes\n",
    "- `premier()` \n",
    "    - renvoye la valeur du premier élément de la liste ou **None** si la liste est vide\n",
    "- `longueur()`\n",
    "    - renvoie la longueur de la liste chainée (0 si elle est vide).\n",
    "- `valeurs()`\n",
    "    - renvoye un tableau avec toutes les valeurs de la liste\n",
    "- `insere_debut(v)`\n",
    "    - prend en paramètre la valeur à insérer `v`\n",
    "    - insère la valeur `v` au début de la liste \n",
    "- `insere_fin(v)`\n",
    "    - prend en paramètre la valeur à insérer `v`\n",
    "    - insère la valeur `v` à la fin de la liste \n",
    "    \n",
    "Avant de vous laisser implémenter ces fonctionnalités, nous allons faire ensemble la première méthode et tester le comportement de notre classe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "97cc6803553e6cdfef0379298b962da9",
     "grade": false,
     "grade_id": "cell-5975bef36a337ac6",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class ListeChainee:\n",
    "    \"\"\"Implementation d'une liste chaînée\"\"\"\n",
    "    def __init__(self, maillons=[], premier=None):\n",
    "        \"\"\"Initialisation de la liste chainée\"\"\"\n",
    "        # tableau contenant les maillons de la liste\n",
    "        self.__maillons = maillons\n",
    "        # indice du premier élément.\n",
    "        self.__premier = premier # None lorsque la liste est vide\n",
    "        \n",
    "    def premier(self):\n",
    "        \"\"\"renvoye la valeur du premier élément de la liste ou None si la liste est vide\"\"\"\n",
    "        return None if self.__premier is None else self.__maillons[self.__premier][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "liste1 = ListeChainee()\n",
    "# Aucun paramètre n'est passé, la liste1 est vide\n",
    "print(liste1.premier())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "fd91e2c77bfd8ed5095524d04a63a66c",
     "grade": false,
     "grade_id": "cell-88ecea8a531a5e2e",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Dans la cellule ci-desssus, j'ai fourni une liste de maillons et un premier élément à la création de la liste. Cela va permettre de l'initialiser avec du contenu. Nous allons pouvoir vérifier que le premier élément de la liste est bien **2** :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "liste1.premier()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "38a1dc0ee57f30285fbd93aa65e9d26d",
     "grade": false,
     "grade_id": "cell-b00ecd55c0027cb6",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Essayons de récupérer l'indice du premier élément stocké das la propriété **__premier** : Vous constaterez une erreur. Cette propriété est cachée, on ne peut y accéder ni pour la consulter ni pour la modifier. C'est une sécurité nous garantissant l'intégrité des données."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "liste1.__premier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "1477f4bdf0c10543c47a64b29473a583",
     "grade": false,
     "grade_id": "cell-ad18c1119336ff20",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Implémentez à présent les méthodes demandées\n",
    "\n",
    "L'ossature de la classe est déjà présente, il vous suffira de remplacer **pass** par la méthode que vous fabriquerez.\n",
    "Vous vous rappelez qu'une méthode se code comme une fonction, la seule différence est le paramètre **self** qui fait référence à l'objet qui contient la méthode. Ce paramètre est *toujours* le premier paramètre passé à la méthode."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "43511d68a83f528d8282b1317da438b1",
     "grade": false,
     "grade_id": "cell-f6272b63ae896abd",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class ListeChainee:\n",
    "    \"\"\"Implementation d'une liste chaînée\"\"\"\n",
    "    def __init__(self, maillons=[], premier=None):\n",
    "        \"\"\"Initialisation de la liste chainée\"\"\"\n",
    "        # tableau contenant les maillons de la liste\n",
    "        self.__maillons = maillons\n",
    "        # indice du premier élément.\n",
    "        self.__premier = premier # None lorsque la liste est vide\n",
    "        \n",
    "    def premier(self):\n",
    "        \"\"\"renvoye la valeur du premier élément de la liste ou None si la liste est vide\"\"\"\n",
    "        return None if self.__premier is None else self.__maillons[self.__premier][0]\n",
    "    \n",
    "    def longueur(self):\n",
    "        \"\"\"renvoie la longueur de la liste chainée (0 si elle est vide).\"\"\"\n",
    "        return 0 if self.__premier is None else len(self.__maillons)\n",
    "    \n",
    "    def valeurs(self):\n",
    "        \"\"\"renvoye un tableau avec toutes les valeurs de la liste\"\"\"\n",
    "        pass\n",
    "\n",
    "    def insere_debut(self, v):\n",
    "        \"\"\"prend en paramètre la valeur à insérer v\n",
    "        insère la valeur v au début de la liste\"\"\"\n",
    "        pass\n",
    "    \n",
    "    def insere_fin(self, v):\n",
    "        \"\"\"prend en paramètre la valeur à insérer v\n",
    "        insère la valeur v à la fin de la liste\"\"\"\n",
    "        pass\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4a0abc064a52505388ec4f4c0a8776b0",
     "grade": false,
     "grade_id": "cell-7673db08b1ef9959",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "0a42528ad5e4121e60f2ec848eab4c50",
     "grade": true,
     "grade_id": "cell-d3c0881bc873f714",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Test de la méthode valeur\n",
    "\n",
    "liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)\n",
    "assert liste1.valeurs() == [2, 3, 5, 8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "075052995ab4d181050b445b352d8188",
     "grade": true,
     "grade_id": "cell-e6771949547dcf3b",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Test de la méthode longueur\n",
    "\n",
    "liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)\n",
    "assert liste1.longueur() == 4\n",
    "liste2 = ListeChainee()\n",
    "assert liste2.longueur() == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b12979ccffdaedbbb7196386cbd7c789",
     "grade": true,
     "grade_id": "cell-1c504adf5448f2b5",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Test de la méthode insere_debut\n",
    "\n",
    "liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)\n",
    "liste1.insere_debut(-5)\n",
    "assert liste1.valeurs() == [-5, 2, 3, 5, 8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "efbb2cc3820a4f1e594cf3d6a1d5487b",
     "grade": true,
     "grade_id": "cell-8c4b6dad88f8a657",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Test de la méthode insere_fin\n",
    "\n",
    "liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)\n",
    "liste1.insere_fin(11)\n",
    "assert liste1.valeurs() == [2, 3, 5, 8, 11]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e1190b836102aac53672eba52e62476f",
     "grade": false,
     "grade_id": "cell-15ad6a10ad6e4ba7",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Nous allons poursuivre l'ajout de méthodes à notre classe. Nous voudrions implémenter la méthode suivante :\n",
    "- `insere_milieu(valeur, place)`\n",
    "    - prend en paramètre une `valeur` et un emplacement `place` dans la liste\n",
    "    - insère la `valeur` à l'emplaceemnt `place`\n",
    "\n",
    "Cette méthode va nécessiter d'accéder aux propriétés privées **__maillons** et **__premier**. Puisque ce n'est pas possible directement, nous allons écrite des méthodes qui permettent de renvoyer ces valeurs sans toutefois permettre leur modification.\n",
    "Afin de sécuriser davantage les données, on renverra une **copie** du tableau maillon et non l'objet original. On est ainsi assuré qu'aucune modification ne sera réalisée sur ce dernier.\n",
    "\n",
    "En *programmation orientée objet*, ces méthodes permettant d'accéder de manière sécurisée à des propriétés cachées s'appellent des **accesseurs**. Voici comment nous pouvons les implémenter :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "189a11e31b5db6eae5b146a6882cb80a",
     "grade": false,
     "grade_id": "cell-ff524b5f3040cb23",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class ListeChainee:\n",
    "    \"\"\"Implementation d'une liste chaînée\"\"\"\n",
    "    def __init__(self, maillons=[], premier=None):\n",
    "        \"\"\"Initialisation de la liste chainée\"\"\"\n",
    "        # tableau contenant les maillons de la liste\n",
    "        self.__maillons = maillons\n",
    "        # indice du premier élément.\n",
    "        self.__premier = premier # None lorsque la liste est vide\n",
    "        \n",
    "    def lire_premier(self):\n",
    "        return self.__premier\n",
    "    def lire_maillons(self):\n",
    "        return [[m[0], m[1]] for m in self.__maillons]\n",
    "    def remplace_maillons(self, maillons):\n",
    "        self.__maillons = maillons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ae396b6b3a300e590e4c5636e9e3ed90",
     "grade": false,
     "grade_id": "cell-fb41ae2356da36e4",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)\n",
    "print(liste1.lire_premier())\n",
    "print(liste1.lire_maillons())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "890af67098f1a9317e573844327442b2",
     "grade": false,
     "grade_id": "cell-d02b1b658b3f0906",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Ainsi, nous accédons aux données interne de notre classe sans pour autant risquer de compromettre ces dernières par une écriture malheureuse.\n",
    "Dans l'exemple suivant, nous allons voir comment utiliser ces accesseurs pour implémenter l'algorithme d'insertion dans une lliste chaînée. Il vous restera ensuite à terminer notre classe avec la méthode **concat()**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "07ec620d2a35b1ae389323412e6998b7",
     "grade": false,
     "grade_id": "cell-80536c9f3945dfd4",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class ListeChainee:\n",
    "    \"\"\"Implementation d'une liste chaînée\"\"\"\n",
    "    def __init__(self, maillons=[], premier=None):\n",
    "        \"\"\"Initialisation de la liste chainée\"\"\"\n",
    "        # tableau contenant les maillons de la liste\n",
    "        self.__maillons = maillons\n",
    "        # indice du premier élément.\n",
    "        self.__premier = premier # None lorsque la liste est vide\n",
    "        \n",
    "    def lire_premier(self):\n",
    "        return self.__premier\n",
    "    \n",
    "    def lire_maillons(self):\n",
    "        return [[m[0], m[1]] for m in self.__maillons]\n",
    "    \n",
    "    def remplace_maillons(self, maillons):\n",
    "        self.__maillons = maillons\n",
    "    \n",
    "    def premier(self):\n",
    "        \"\"\"renvoye la valeur du premier élément de la liste ou None si la liste est vide\"\"\"\n",
    "        return None if self.__premier is None else self.__maillons[self.__premier][0]\n",
    "    \n",
    "    def longueur(self):\n",
    "        \"\"\"renvoie la longueur de la liste chainée (0 si elle est vide).\"\"\"\n",
    "        return 0 if self.__premier is None else len(self.__maillons)\n",
    "    \n",
    "    def insere_milieu(self, valeur, pos):\n",
    "        \"\"\"prend en paramètre la valeur et la position\n",
    "        insère la valeur dans la liste à la position demandée\n",
    "        Si la position n'existe pas dans la liste, on insère à la fin\"\"\"\n",
    "        \n",
    "        # On récupère les données internes\n",
    "        maillons = self.lire_maillons()\n",
    "        premier = self.lire_premier()\n",
    "        \n",
    "        # On utilise les méthodes existantes pour les cas limites\n",
    "        if pos >= self.longueur():\n",
    "            self.insere_fin(valeur)\n",
    "        elif pos == 0:\n",
    "            self.insere_debut(valeur)\n",
    "        else:\n",
    "            # parcour de la liste à la recherche de la position\n",
    "            i = premier\n",
    "            for _ in range(pos-1):\n",
    "                if maillons[i][1] is not None:\n",
    "                    i = maillons[i][1]\n",
    "            # On crée un nouveau maillon à la fin de la liste\n",
    "            maillons.append([valeur, maillons[i][1]])\n",
    "            # On change les liens de manière à insérer le maillon\n",
    "            maillons[i][1] = len(maillons)-1\n",
    "            self.remplace_maillons(maillons)\n",
    "    \n",
    "    # Recopiez ici vos méthodes valeurs() et insere*()\n",
    "            \n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b468a1bab0d61ae0eff624ab3b37f53c",
     "grade": true,
     "grade_id": "cell-2879ce9d9564ca32",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Test de la méthode insere_milieu\n",
    "\n",
    "liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)\n",
    "liste1.insere_milieu(10,2)\n",
    "assert liste1.valeurs() == [2, 3, 10, 5, 8]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "5efaaa36c95f4892c394384637c9793d",
     "grade": false,
     "grade_id": "cell-de125ac7dceae318",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## A vous de jouer\n",
    "\n",
    "Il ne vous reste plus à présent qu'à terminer notre classe **ListeChainee** en y ajoutant la méthode **concat()** :\n",
    "\n",
    "- `concat(liste_c)`\n",
    "    - prend en paramètre une liste`liste_c`\n",
    "    - concatène (met bout à bout) `liste_c` à la fin de la liste courante"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8942fe444e44654edbccb768e999ac54",
     "grade": false,
     "grade_id": "cell-a77760646a53fef4",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class ListeChainee:\n",
    "    \"\"\"Implementation d'une liste chaînée\"\"\"\n",
    "    def __init__(self, maillons=[], premier=None):\n",
    "        \"\"\"Initialisation de la liste chainée\"\"\"\n",
    "        # tableau contenant les maillons de la liste\n",
    "        self.__maillons = maillons\n",
    "        # indice du premier élément.\n",
    "        self.__premier = premier # None lorsque la liste est vide\n",
    "        \n",
    "    def lire_premier(self):\n",
    "        return self.__premier\n",
    "    \n",
    "    def lire_maillons(self):\n",
    "        return [[m[0], m[1]] for m in self.__maillons]\n",
    "    \n",
    "    def remplace_maillons(self, maillons):\n",
    "        self.__maillons = maillons\n",
    "    \n",
    "    def premier(self):\n",
    "        \"\"\"renvoye la valeur du premier élément de la liste ou None si la liste est vide\"\"\"\n",
    "        return None if self.__premier is None else self.__maillons[self.__premier][0]\n",
    "    \n",
    "    def longueur(self):\n",
    "        \"\"\"renvoie la longueur de la liste chainée (0 si elle est vide).\"\"\"\n",
    "        return 0 if self.__premier is None else len(self.__maillons)\n",
    "    \n",
    "    def insere_milieu(self, valeur, pos):\n",
    "        \"\"\"prend en paramètre la valeur et la position\n",
    "        insère la valeur dans la liste à la position demandée\n",
    "        Si la position n'existe pas dans la liste, on insère à la fin\"\"\"\n",
    "        \n",
    "        # On récupère les données internes\n",
    "        maillons = self.lire_maillons()\n",
    "        premier = self.lire_premier()\n",
    "        \n",
    "        # On utilise les méthodes existantes pour les cas limites\n",
    "        if pos >= self.longueur():\n",
    "            self.insere_fin(valeur)\n",
    "        elif pos == 0:\n",
    "            self.insere_debut(valeur)\n",
    "        else:\n",
    "            # parcour de la liste à la recherche de la position\n",
    "            i = premier\n",
    "            for _ in range(pos-1):\n",
    "                if maillons[i][1] is not None:\n",
    "                    i = maillons[i][1]\n",
    "            # On crée un nouveau maillon à la fin de la liste\n",
    "            maillons.append([valeur, maillons[i][1]])\n",
    "            # On change les liens de manière à insérer le maillon\n",
    "            maillons[i][1] = len(maillons)-1\n",
    "            self.remplace_maillons(maillons)\n",
    "    \n",
    "    # Recopiez ici vos méthodes valeurs() et insere*()\n",
    "            \n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "45aae377ea68dcca2d66e99c2a3a9fc9",
     "grade": true,
     "grade_id": "cell-c09ef77d15576f1c",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Test de la méthode concat\n",
    "\n",
    "liste1 = ListeChainee([[3, 2], [8,None], [5, 1], [2,0]], 3)\n",
    "liste2 = ListeChainee([[6, 2], [8,None], [7, 1]], 0)\n",
    "liste1.concat(liste2)\n",
    "assert liste1.valeurs() == [2, 3, 5, 8, 6, 7, 8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Éditer les Méta-Données",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}