{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Piles et files" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans ce notebook, vous allez implémenter les structures de données suivantes :\n", "- les piles;\n", "- les files.\n", "\n", "Pour ce faire, nous allons utiliser une autre structure de donnée : **les listes chaînées doubles**\n", "\n", "## Listes doublement chaînées.\n", "\n", "![Listes chaînées doubles](https://upload.wikimedia.org/wikipedia/commons/2/26/Liste_doublement_cha%C3%AEn%C3%A9e.png)\n", "\n", "Cette structure de donnée est une extension des listes chaînées déjà rencontrées. \n", "La différence avec une liste simplement chaînée est que, cette fois-ci, un pointeur vers l'élément précédent (ou prédécesseur) est ajouté. Ainsi l'accès peut se faire indifféremment dans les deux sens : de successeur en successeur, ou de prédécesseur en prédécesseur.\n", "\n", "Cette structure est plus coûteuse en mémoire (un pointeur supplémentaire par élément) et en nombre d'instructions pour la mise à jour : une insertion coûte quatre copies de pointeurs, contre deux dans le cas d'une liste simplement chaînée.\n", "\n", "En revanche, cela permet d'opérer une insertion avant ou après un élément, sans nécessairement disposer d'un pointeur sur un voisin, alors qu'une liste simplement chaînée n'autorise une insertion qu'à une seule position par rapport à un élément : en successeur ou (exclusivement) en prédécesseur.\n", "\n", " \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "