Exercices

TP1 — Complexités, piles, files et listes

Le but de cette page est surtout de pouvoir refaire les bons exercices pendant le blocus. On garde donc une courte remise en route théorique, puis uniquement les implémentations qui valent la peine d’être recodées.

Questions d’introduction

1. ADT et implémentation

Qu’est-ce qu’un Abstract Data Type (ADT) ? Quelle différence fais-tu entre l’ADT et son implémentation concrète en Java ?

2. Stack avec une linked list

Où placer le top dans une singly linked list pour obtenir des push et pop efficaces ? Quelle complexité obtient-on ?

3. Parcours d’une LinkedList

Pourquoi ce parcours peut-il être mauvais ?

for (int i = 0; i < list.size(); i++) {
    process(list.get(i));
}

Quel pattern faut-il utiliser à la place ?

4. Complexité amortie

Pourquoi un tableau dynamique peut-il avoir un push en $\Theta(1)$ amorti, alors qu’un redimensionnement coûte ponctuellement $\Theta(n)$ ?

Voir les solutions

---

Exercices INGInious à refaire

Pendant le blocus, refaire les exercices suivants sans regarder la solution au départ.

StackWithTwoQueues

À refaire entièrement.

Points à maîtriser :

• invariant entre les deux queues ;
• transformation FIFO → comportement LIFO ;
• push, pop, peek ;
• complexité de chaque opération.

SegmentedList

À refaire entièrement.

Points à maîtriser :

• indices globaux sur plusieurs segments ;
• parcours d’un segment au suivant ;
• implémentation de Iterable ;
• itérateur fail-fast ;
• gestion correcte des cas limites.

CircularLinkedList

À refaire entièrement.

Points à maîtriser :

• invariant circulaire ;
• manipulation des références ;
• enqueue ;
• remove(index) ;
• itérateur fail-fast.

---

Réponses aux questions d’introduction

Réponse 1

Un ADT définit les données manipulées, les opérations disponibles et leur comportement, sans fixer la représentation interne.

Une implémentation choisit ensuite comment réaliser ce contrat : liste chaînée, tableau dynamique, etc.

Réponse 2

Dans une singly linked list, placer le top en tête permet de modifier seulement quelques références.

node.next = first;
first = node;

On obtient ainsi push et pop en $\Theta(1)$.

Placer le top en fin peut imposer un parcours pour retrouver le prédécesseur, donc $\Theta(n)$.

Réponse 3

Sur une LinkedList, get(i) peut nécessiter un parcours de la liste. Répéter cet accès pour chaque indice peut donc mener à $\Theta(n^2)$.

Préférer :

for (E x : list) {
    process(x);
}

ou un Iterator, qui parcourt la liste en $\Theta(n)$.

Réponse 4

Quand un tableau dynamique double sa capacité, certains push coûtent $\Theta(n)$, mais ces redimensionnements deviennent de plus en plus espacés.

Les copies successives ont un coût total de l’ordre de :

$$1 + 2 + 4 + 8 + \dots < 2n$$

Sur $n$ insertions, le coût total reste donc $\Theta(n)$, soit $\Theta(1)$ amorti par insertion.