¿Cuáles son las complejidades temporales de varias estructuras de datos?

Estoy tratando de enumerar las complejidades temporales de las operaciones de estructuras de datos comunes como Arrays, Binary Search Tree, Heap, Linked List, etc. y especialmente me refiero a Java. Son muy comunes, pero supongo que algunos de nosotros no estamos 100% seguros de la respuesta exacta. Cualquier ayuda, especialmente referencias, es muy apreciada.

Por ejemplo, para una lista enlazada individualmente: cambiar un elemento interno es O (1). ¿Cómo puedes hacerlo? Usted TIENE para buscar el elemento antes de cambiarlo. Además, para el vector, agregar un elemento interno se da como O (n). Pero, ¿por qué no podemos hacerlo en tiempo constante amortizado utilizando el índice? Por favor corríjame si me falta algo.

Estoy publicando mis hallazgos / conjeturas como primera respuesta.

Matrices

• Establecer, comprobar elemento en un índice particular: O (1)
• Buscando : O (n) si la matriz no está ordenada y O (log n) si la matriz está ordenada y se usa algo así como una búsqueda binaria,
• Como señaló Aivean , no hay ninguna Deleteoperación disponible en Arrays. Podemos eliminar simbólicamente un elemento estableciendo un valor específico, por ejemplo, -1, 0, etc., dependiendo de nuestros requisitos.
• Del mismo modo, Insertpara matrices es básicamente Setcomo se mencionó al principio

Lista de arreglo:

• Agregar : Amortizado O (1)
• Eliminar : O (n)
• Contiene : O (n)
• Tamaño : O (1)

Lista enlazada:

• Insertar : O (1) , si se hace en la cabecera, O (n) si en cualquier otro lugar, ya que tenemos que llegar a esa posición recorriendo la lista enlazada linealmente.
• Eliminando : O (1) , si se hace en la cabecera, O (n) si en cualquier otro lugar, ya que tenemos que alcanzar esa posición recorriendo la lista enlazada linealmente.
• Buscando : O (n)

Lista doblemente vinculada:

• Insertar : O (1) , si se hace en la cabeza o en la cola, O (n) si en cualquier otro lugar, ya que tenemos que alcanzar esa posición recorriendo la lista enlazada linealmente.
• Eliminando : O (1) , si se hace en la cabeza o en la cola, O (n) si en cualquier otro lugar, ya que tenemos que llegar a esa posición recorriendo la lista enlazada linealmente.
• Buscando : O (n)

Apilar:

• Empuje : O (1)
• Pop : O (1)
• Arriba : O (1)
• Buscar (algo así como buscar, como una operación especial): O (n) (supongo que sí)

Cola / Deque / Cola circular:

• Insertar : O (1)
• Eliminar : O (1)
• Tamaño : O (1)

Árbol de búsqueda binaria:

• Insertar, eliminar y buscar : Caso promedio: O (log n) , Caso peor: O (n)

Árbol rojo-negro:

• Insertar, eliminar y buscar : Caso promedio: O (log n) , peor caso: O (log n)

Heap / PriorityQueue (min / max):

• Encontrar mínimo / Encontrar máximo : O (1)
• Insertar : O (log n)
• Eliminar mínimo / Eliminar máximo : O (log n)
• Extraer mínimo / Extraer máximo : O (log n)
• Buscar, Eliminar (si se proporciona): O (n) , tendremos que escanear todos los elementos ya que no están ordenados como BST

HashMap / Hashtable / HashSet:

• Insertar / Eliminar : O (1) amortizado
• Cambiar el tamaño / hash : O (n)
• Contiene : O (1)