Qu'est-ce qu'un type de données abstrait (TDA) et pourquoi le séparer de son implémentation ?

Question

Accepted Answer

Un **type de données abstrait** définit un ensemble de valeurs et les **opérations** autorisées sur elles, décrites purement par le **comportement** — non par le code. L'implémentation est la structure concrète (array, linked list, tree) qui réalise ce comportement.

## La même TDA, différentes implémentations

```text
ADT "Queue":  enqueue, dequeue, peek  (FIFO contract)

Implementation A: array + two indices (ring buffer)
Implementation B: doubly linked list with head/tail pointers
Both honor the SAME contract; cost profiles differ.
```

## Pourquoi les séparer

```python
# Callers depend on the CONTRACT, not the internals
class Stack:
    def push(self, x): ...
    def pop(self): ...
    def peek(self): ...
# Swap a list for a linked list internally — callers never change.
```

## TDAs courants et implémentations typiques

| TDA | Implémentations courantes |
|---|---|
| List | dynamic array, linked list |
| Stack | array, linked list |
| Queue | ring buffer, linked list |
| Map | hash table, balanced tree |
| Priority Queue | binary heap |

## Pourquoi c'est important

Programmer pour une TDA (une interface) garde le code flexible : vous pouvez optimiser l'implémentation plus tard sans casser les appelants.

Cela affine aussi le raisonnement — vous décidez d'abord du *comportement* dont vous avez besoin, puis choisissez la structure la moins coûteuse qui le fournit.

TDA	Implémentations courantes
List	dynamic array, linked list
Stack	array, linked list
Queue	ring buffer, linked list
Map	hash table, balanced tree
Priority Queue	binary heap