Différence entre la liste<T> et la liste liée<T>

Question

Nous utilisons List chaque fois que nous avons besoin d'une liste. Je remarque maintenant qu'il y a une LinkedList.

Je me demandais quelle était la différence entre ces deux-là, et quand vous deviez utiliser l'un 2 plutôt que l'autre.

Answer 1

Un List<T> est en fait un tableau, ce qui signifie que son opération Add est O(1) à la fin et O(n) à l'avant, mais vous pouvez l'indexer dans O(1). Un LinkedList<T> est, comme il est dit, une liste liée. Comme il est doublement lié, vous pouvez ajouter des éléments à l'avant ou à l'arrière dans O(1), mais l'indexation dans celui-ci est O(n).

Answer 2

Dans presque tous les scénarios, une liste va surpasser une liste liée. Les résultats du monde réel diffèrent souvent avec la théorie de la complexité Big O.