LinkedList
# Estructura
Es una lista que tiene dobles conexiones, basada en nodos conectados. Dependiendo de la implementacion especifica podriamos referirnos a una Single Linked-List o a una Double Linked-List.
Un Nodo se refiere a un espacio extra que en realidad guarda las referencias en memoria (Hexadecimal) para los siguientes datos.
# Operaciones
- Obtener y Actualizar un elemento por su indice en cualquier posicion toma O(n). Se determina el camino mas corto si es desde el inicio o desde el final
- Insertar o Remover elementos en cualquier posicion solo requiere del cambio de dos cosas, el elemento nodo siguiente del nodo anterior y el elemento nodo anterior del nodo siguiente al indice donde queremos reinsertar nuestro elemento. El tiempo que tomara dependera de que tan lejos o cerca esten del inicio o final de la lista, en promedio toma O(1) pero en el peor de los casos puede tomar O(n)
- Introducir, Remover o Editar el elemento al Inicio y al Final toman O(1)
# Usos
Al ser una estructura de datos tan versatil, esta puede servirnos para implementar no solo listas si no otras estructuras como Deque, Queue y Stacks. Podemos ver un ejemplo de esto en LinkedList como implementacion de Queue en Java.
Relaciones: ArrayList