É mais eficiente para remover elementos de um ArrayList ou LinkedList?

Question

Em teoria, é mais eficiente para remover elementos de uma ArrayList ou um LinkedList?

Answer 1

É "mais fácil" (isto é, mais eficiente) para removê-los a partir de um LinkedList, porque a remoção de um ArrayList requer mover todos os elementos subsequentes para uma nova posição na lista de-todos os elementos subsequentes da matriz deve ser atribuído um novo valor. Com uma lista ligada, apenas um ponteiro (ou dois, com uma lista duplamente vinculada) deve ser atribuído-re.

Answer 2

Pois bem, a remoção de um elemento de uma (duplamente linked-) lista é O (1). Mas a remoção a partir de uma matriz, é necessário que os elementos restantes são deslocadas para baixo um espaço na matriz, que é O (n).

Dito isto, a obtenção de um elemento específico de uma lista índice é O (n), enquanto que a obtenção de um elemento específico de uma matriz por índice é O (1).

Assim, o de remoção real, LinkedList vai ser melhor. Há mais informações sobre matriz de contra LinkedList aqui .