Qual é a complexidade assintótica das operações com elementos na lista?

Depende do tipo de lista e da operação.

Normalmente consideram-se os seguintes tipos de listas:

• Lista ligada simples
• Lista ligada duplamente
• Array (como caso particular de lista)

Operações:

• Acesso por índice
• Inserção
• Remoção
• Pesquisa de valor

Operação	Lista ligada simples	Lista ligada duplamente	Array
Acesso por índice	O(n)	O(n)	O(1)
Inserção	O(1) (no início)	O(1) (no início/no fim)	O(n)
Remoção	O(n)	O(n)	O(n)
Pesquisa de valor	O(n)	O(n)	O(n)

Explicações:

• O(1) (Tempo constante): A operação leva um tempo fixo, independentemente do tamanho da lista. Por exemplo, acesso a um elemento por índice em um array.
• O(n) (Tempo linear): O tempo de execução da operação é proporcional ao tamanho da lista. Por exemplo, procurar um elemento numa lista não ordenada.
• O(log n) (Tempo logarítmico): O tempo de execução aumenta logaritmicamente com o tamanho da lista. Encontra-se frequentemente em operações com dados ordenados (por exemplo, busca binária).

Detalhes:

• Em uma lista ligada simples: Inserção no início - O(1). Inserção no fim ou inserção/remoção por índice requer percorrer a lista até ao elemento desejado, o que dá O(n).
• Em uma lista duplamente ligada: Inserção no início e no fim - O(1). Inserção/remoção numa posição dada - O(1), mas procurar esse nó por valor ou índice - O(n).
• Num array: Acesso por índice - O(1). Inserção ou remoção no meio do array requer deslocar elementos, o que dá O(n). Inserção/remoção no fim, se houver capacidade reservada (por exemplo, em std::vector com certa capacidade), pode ser O(1) em média, mas O(n) no pior caso (reallocação).