Celdas contiguas
Una lista estática guarda sus datos en un arreglo: celdas seguidas en memoria contigua. Por eso obtener(1) es una sola cuenta: salta directo a la celda 1 sin recorrer. Lectura en O(1).
Una lista estática guarda sus datos en un arreglo: celdas seguidas en memoria contigua.
Por eso obtener(1) es una sola cuenta: salta directo a la celda 1 sin recorrer. Lectura en O(1).
Una lista estática guarda sus datos en un arreglo: celdas seguidas en memoria contigua. Por eso obtener(1) es una sola cuenta: salta directo a la celda 1 sin recorrer. Lectura en O(1).
agregarAlInicio(10) necesita libre la celda 0: antes debe desplazar cada elemento una posición.
El for corre el 30 y luego el 20; con n elementos son n movimientos. Insertar al inicio cuesta O(n).
agregarAlInicio(10) necesita libre la celda 0: antes debe desplazar cada elemento una posición. El for corre el 30 y luego el 20; con n elementos son n movimientos. Insertar al inicio cuesta O(n).
La lista enlazada usa otra pieza: el Nodo, un objeto con un dato y una referencia siguiente.
Los nodos quedan dispersos por el Heap. Solo cabeza sabe dónde empieza; el último apunta a null.
La lista enlazada usa otra pieza: el Nodo, un objeto con un dato y una referencia siguiente. Los nodos quedan dispersos por el Heap. Solo cabeza sabe dónde empieza; el último apunta a null.
agregarAlInicio(10) crea nuevo con new Nodo(10): nace aislado, con siguiente en null.
Si cabeza = nuevo va primero, se pierde el 20: compila, pero el recolector se lleva el resto de la lista.
agregarAlInicio(10) crea nuevo con new Nodo(10): nace aislado, con siguiente en null. Si cabeza = nuevo va primero, se pierde el 20: compila, pero el recolector se lleva el resto de la lista.
El orden correcto: nuevo.siguiente = cabeza engancha primero al 20, que la lista ya tenía.
Recién después cabeza = nuevo adopta al 10 como primero. Ningún nodo se movió: inserción en O(1).
El orden correcto: nuevo.siguiente = cabeza engancha primero al 20, que la lista ya tenía. Recién después cabeza = nuevo adopta al 10 como primero. Ningún nodo se movió: inserción en O(1).
mostrar() recorre con una variable auxiliar: actual arranca en cabeza, que nunca se mueve.
Cada vuelta imprime actual.dato y avanza con actual = actual.siguiente hasta llegar a null.
mostrar() recorre con una variable auxiliar: actual arranca en cabeza, que nunca se mueve. Cada vuelta imprime actual.dato y avanza con actual = actual.siguiente hasta llegar a null.
Para quitar el 20 hay que pararse en el nodo anterior: desde el 20 no se puede volver atrás.
anterior.siguiente = anterior.siguiente.siguiente salta el 20; sin referencias, el recolector se lo lleva.
Para quitar el 20 hay que pararse en el nodo anterior: desde el 20 no se puede volver atrás. anterior.siguiente = anterior.siguiente.siguiente salta el 20; sin referencias, el recolector se lo lleva.
El arreglo paga la inserción para que la lectura sea gratis: leer es O(1), insertar al inicio, O(n).
La lista enlazada paga la lectura para que la inserción sea gratis: caminar es O(n), enganchar es O(1).
El arreglo paga la inserción para que la lectura sea gratis: leer es O(1), insertar al inicio, O(n). La lista enlazada paga la lectura para que la inserción sea gratis: caminar es O(n), enganchar es O(1).