Accès au 
𝑖
i-ème élément d'une liste chaînée simple : 
𝑂
(
𝑖
)
O(i), soit 
𝑂
(
𝑛
)
O(n) dans le pire des cas.

Pourquoi

Structure : chaque nœud contient une valeur et un pointeur vers le suivant. Aucun adressage direct par indice.
Parcours séquentiel obligatoire : il faut partir de la tête et suivre 
𝑖
i liens pour atteindre l'élément d'indice 
𝑖
i.
Détail des coûts :

coût exact : 
𝑖
i déréférencements, donc 
𝑂
(
𝑖
)
O(i) ;
pire des cas (
𝑖
=
𝑛
−
1
i=n−1, dernier élément) : 
𝑂
(
𝑛
)
O(n) ;
cas moyen sur un indice tiré uniformément : 
𝑛
2
2
n
	​

 étapes, soit 
𝑂
(
𝑛
)
O(n) ;
meilleur cas (
𝑖
=
0
i=0, tête) : 
𝑂
(
1
)
O(1).

Comparaison

Structure Accès par indice

Tableau 
𝑂
(
1
)
O(1)
Liste simplement chaînée 
𝑂
(
𝑖
)
O(i) 
𝑂
(
𝑛
)
O(n)
Liste doublement chaînée 
𝑂
(
min
⁡
(
𝑖
,
𝑛
−
𝑖
)
)
O(min(i,n−i)) 
𝑂
(
𝑛
)
O(n)

À retenir
La liste chaînée est inadaptée à l'accès aléatoire. Son avantage est l'insertion/suppression en 
𝑂
(
1
)
O(1) lorsqu'on possède déjà le pointeur sur le nœud concerné (typiquement en tête) ; si la position doit d'abord être trouvée par indice, le coût redevient 
𝑂
(
𝑛
)
O(n).