Quelle est la différence entre un tableau et une liste chaînée ?

Réponse publiée sur Quora

En principe un tableau est alloué en mémoire en un seul bloc, ce qui permet d’accéder instantanément (O(1)) au n-ème élément en calculant son adresse. Par contre l’agrandissement du tableau est coûteux car il faut allouer un autre bloc et copier le contenu.

La liste chaînée est constituée de plusieurs blocs alloués contenant quelques éléments voire un seul, et un pointeur vers le bloc suivant. L’accès au n-ème élément est plus lent (O(n)) mais l’agrandissement de la liste est rapide, surtout qu’en pratique on conserve toujours un pointeur vers le dernier bloc.