Estructura de datos: Lista Enlazada

Clase 2 de 41 • Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Walter Oswaldo Pleitez Torres

student•

Ventaja de la Lista Enlazada; Cuando se quiere insertar o remover algún nodo de la Lista Enlazada no se tiene que mover la posición de los demás Nodos porque esta estructura realiza un proceso de conexion o desconexión con los nodos que se encuentran en la posición anterior y siguiente de la Lista Enlazada. Esta complejidad se llama O(1) o constante y es mucho más eficiente, con esto no se busca o recorre sino que se accede directamente para remover o insertar La Lista Enlazada no usa espacios de memoria contiguos.

Jairo Fernández

student•

muy buena explicación!

Juan Pablo Reina Gutierrez

student•

Si por ejemplo quiero insertar un elemento en la penúltima posición de una lista enlazada, ya no sería o(1) la complejidad sino o(n) porque debo recorrer toda la lista?

Camila Londoño

teacher•

Si, es O(n)

Miguel Angel Reyes Moreno

student•

Estructura de dato: Lista Enlazada

Representan datos que no están contiguos, seguidos en memoria, pero podemos crear relaciones entre ellos para que estén enlazados. La relación puede ser unidireccional o bidireccional.

O ← O O → O

O ↔ O

Podemos fácilmente manipular los apuntadores de los nodos. Podemos tener complejidad O(1), en lugar de O(n) como pasaría con arrays comunes.

Ramses Acosta

student•

Como determinas que algo es O(n) o O(1), en el anterior curso vi que explicas cada notacion pero que herramienta o analisis se aplica para saber cual la O notation ?

Juan Castro

teacher•

Esta clase te lo explica: https://platzi.com/clases/4591-algoritmos-avanzados-entrevistas/55738-calculando-la-complejidad-de-algoritmos/

Ramses Acosta

student•

en este otro curso tambien https://platzi.com/clases/2517-complejidad-js/42451-evaluacion-de-complejidad-temporal-con-big-o/

Ulises Alejandro Mánica Caricio

student•

Las estructuras de datos funcionan para mejorar la calidad de nuestros algoritmos... ahorrando tiempo u memoria al proyecto... mejorando por consecuente la eficiencia del mismo.

Además que permiten en casos especiales manejar datos especiales... que con listas u arrays no se podrían o sería muy costoso manejar

Walter Oswaldo Pleitez Torres

student•

Desventaja una Lista: Cuando se quiere insertar un nuevo Nodo en la Lista se mueven (hacia un lado) todos los nodos que se encuentran después de la ubicación indicada. Esto cambia la direccion de memoria de todos los nodos. La complejidad de insertar de esta manera se le llama O(n); que significa Lineal.

Ivan Camilo Buitrago Buitrago

student•

Estructura de datos: Listas Enlazadas

Una lista enlazada es una colección de elementos, donde cada elemento contiene dos partes principales: el dato que queremos almacenar y un enlace (o puntero) al siguiente elemento de la lista. Cada elemento se llama "nodo".

Imagina que tienes una cadena de cuentas de cuentos (nodos), y cada cuenta tiene una página con una parte de la historia (dato) y un marcador para decirte dónde está la siguiente página (enlace al siguiente nodo). Así, puedes leer la historia de principio a fin siguiendo las páginas.

En términos más técnicos:

Nodo: Cada elemento de la lista. Contiene dos partes: el dato y un enlace al siguiente nodo.
Enlace (o puntero): Un elemento que apunta al siguiente nodo en la lista.
Inicio de la lista: El primer nodo de la lista.
Fin de la lista: El último nodo de la lista que tiene un enlace que apunta a null o a ningún otro nodo, indicando el final.

La principal ventaja de las listas enlazadas es que permiten la inserción y eliminación eficientes de elementos en cualquier posición, ya que solo necesitas actualizar los enlaces, en lugar de reorganizar toda la estructura como en otros tipos de listas. Sin embargo, el acceso a un elemento específico puede ser un poco más lento, ya que debes seguir los enlaces desde el inicio de la lista hasta el elemento deseado.

Reinaldo Mendoza

student•

aka Linked Lists

Nicolas Alpargatero

student•

La profe se hace entender super bien. Me gusta que tenga super clarísimo el Big O notation, pues da a conocer mejor en qué casos usar lo que enseña.

William Rodriguez

student•

Super claro. Gracias camila.

Estructura de datos: Lista Enlazada

Introducción

¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

Estructura de datos: Lista Enlazada

Programando listas enlazadas con Java

Cómo Invertir una Lista Enlazada

Odd Even Linked List: análisis del problema

Solución de Odd Even Linked List

Playground: Odd Even Liked List

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Playground: Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de Palindrome Linked List

Playground: Palindrome Linked List

Programando Palindrome Linked List con Java

Reorder List: análisis del problema

Solución de Reorder List

Programando Reorder List con JavaScript

Playground: Reorder List Without Repeated Values

Reto: LRU Caché

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Pilas y colas

Estructura de datos: Pilas y Colas

Paréntesis Válido: análisis del problema

Solución de Paréntesis Válido

Playground: Paréntesis Válido

Programando Paréntesis Válido con C++

Comparación de Cadenas con Backspaces

Colas de prioridad

Estructura de datos: Colas de Prioridad

K Closest Points to Origin: análisis del problema

Solución de K Closest Points to Origin

Playground: K Closest Points to Origin

Programando K Closest Points to Origin con Python

Reorganize String: análisis del problema

Solución de Reorganize String

Playground: Reorganize String

Programando Reorganize String con Python

Colas de Prioridad: Ejercicios Prácticos y Soluciones

Colas de Prioridad y Gestión de Eventos

Próximos pasos

Toma el Curso Avanzado de Algoritmos: Grafos y Árboles