Est-il plus efficace de supprimer des éléments d'une liste de tableaux ou d'une liste de liens?

Question

En théorie, est-il plus efficace de supprimer des éléments d'un ArrayList ou d'un LinkedList ?

Answer 1

C’est "plus facile" (c’est-à-dire plus efficace) pour les supprimer d’un LinkedList , car leur suppression d’un ArrayList nécessite le déplacement de tous les éléments suivants vers un nouvel emplacement de la liste & # 8212; tous les suivants les éléments du tableau doivent recevoir une nouvelle valeur. Avec une liste liée, un seul pointeur (ou deux, avec une liste à double liaison) doit être réaffecté.

Answer 2

Eh bien, le retrait d’un élément d’une liste (à liaison double) est O (1). Mais le retrait d’un tableau nécessitera que les éléments restants soient décalés d’un espace vers le bas dans le tableau, qui est O (n).

Cela dit, obtenir un élément spécifique dans une liste par index est O (n), tandis qu’obtenir un élément spécifique dans un tableau par index est O (1).

Donc, pour la suppression réelle, LinkedList sera mieux. ici contient plus d'informations sur Array par rapport à LinkedList.