Quais são as complexidades de tempo de várias estruturas de dados?

Estou tentando listar complexidades de tempo de operações de estruturas de dados comuns, como Arrays, árvore de pesquisa binária, heap, lista vinculada, etc. e, especialmente, estou me referindo a Java. Eles são muito comuns, mas acho que alguns de nós não estão 100% confiantes sobre a resposta exata. Qualquer ajuda, especialmente referências, é muito apreciada.

Por exemplo, para lista vinculada individualmente: Alterar um elemento interno é O (1). Como você pode fazer isso? Você TEM que pesquisar o elemento antes de alterá-lo. Além disso, para o vetor, adicionar um elemento interno é dado como O (n). Mas por que não podemos fazer isso em tempo constante amortizado usando o índice? Por favor, me corrija se eu estiver faltando alguma coisa.

Estou postando minhas descobertas / suposições como a primeira resposta.

Arrays

• Definir, verificar elemento em um índice específico: O (1)
• Pesquisando : O (n) se a matriz não estiver classificada e O (log n) se a matriz for classificada e algo como uma pesquisa binária for usada,
• Conforme apontado por Aivean , não háDelete operação disponível em Arrays. Podemos excluir simbolicamente um elemento definindo-o para algum valor específico, por exemplo, -1, 0, etc., dependendo de nossos requisitos
• Da mesma forma, Insertpara matrizes é basicamente Setcomo mencionado no início

ArrayList:

• Adicionar : O amortizado (1)
• Remover : O (n)
• Contém : O (n)
• Tamanho : O (1)

Lista vinculada:

• Inserindo : O (1) , se feito no cabeçalho, O (n) se em qualquer outro lugar, uma vez que temos que atingir essa posição percorrendo a lista vinculada linearmente.
• Excluindo : O (1) , se feito no cabeçalho, O (n) se em qualquer outro lugar, já que temos que alcançar essa posição percorrendo a lista vinculada linearmente.
• Pesquisando : O (n)

Lista duplamente vinculada:

• Inserindo : O (1) , se feito na ponta ou na cauda, O (n) se em qualquer outro lugar, pois temos que alcançar essa posição percorrendo a lista vinculada linearmente.
• Excluindo : O (1) , se feito na ponta ou na cauda, O (n) se em qualquer outro lugar, pois temos que alcançar essa posição percorrendo a lista vinculada linearmente.
• Pesquisando : O (n)

Pilha:

• Empurre : O (1)
• Pop : O (1)
• Superior : O (1)
• Pesquisar (algo como lookup, como uma operação especial): O (n) (acho que sim)

Queue / Deque / Circular Queue:

• Inserção : O (1)
• Remover : O (1)
• Tamanho : O (1)

Árvore de pesquisa binária:

• Inserir, excluir e pesquisar : Caso médio: O (log n) , Pior caso: O (n)

Árvore Vermelho-Preto:

• Inserir, excluir e pesquisar : Caso médio: O (log n) , Pior caso: O (log n)

Heap / PriorityQueue (min / max):

• Encontre Mín / Encontre Máx : O (1)
• Inserir : O (log n)
• Excluir Min / Excluir Max : O (log n)
• Extrair Min / Extrair Max : O (log n)
• Lookup, Delete (se for fornecido): O (n) , teremos que verificar todos os elementos, pois eles não estão ordenados como BST

HashMap / Hashtable / HashSet:

• Inserir / Excluir : O (1) amortizado
• Redimensionar / hash : O (n)
• Contém : O (1)