Esta página se tradujo automáticamente con la API de traducción de Google Cloud.
Algunas páginas se pueden leer mejor en su totalidad.
Una lista enlazada es una estructura de datos lineal, en la que los elementos no se almacenan en ubicaciones de memoria contiguas. Los elementos de una lista enlazada se enlazan mediante punteros.
Una lista enlazada es una estructura de datos que consta de un grupo de nodos que juntos representan una secuencia. Cada nodo contiene dos campos:
- Campo de datos: contiene los datos reales.
- Campo de enlace: contiene la dirección del siguiente nodo en la secuencia.
El ejemplo anterior muestra una lista enlazada con cuatro nodos. El primer nodo se llama nodo cabeza y el último nodo se llama nodo cola. El nodo principal es el primer nodo de la secuencia y el nodo final es el último nodo de la secuencia.
Los nodos de una lista enlazada no se almacenan en ubicaciones de memoria contiguas. El campo de enlace de un nodo contiene la dirección del siguiente nodo en la secuencia. El puntero de cabeza apunta al primer nodo y el puntero de cola apunta al último nodo.
- Las listas enlazadas son estructuras de datos dinámicas. Es decir, pueden crecer y reducirse durante la ejecución de un programa.
- Las operaciones de inserción y eliminación se pueden implementar fácilmente en listas vinculadas.
- Las listas enlazadas se pueden implementar fácilmente de diferentes maneras. Por ejemplo, se pueden implementar como listas enlazadas individualmente o listas enlazadas doblemente.
- Las listas enlazadas circulares se pueden implementar fácilmente en listas enlazadas.
- El acceso aleatorio no es posible en listas enlazadas. Necesitamos acceder a los nodos secuencialmente desde el principio.
- Se requiere espacio de memoria adicional para almacenar los punteros.
- Las matrices tienen una mejor localidad de caché que puede hacerlas un poco más rápidas.
Hay dos formas de implementar listas enlazadas:
- Listas enlazadas individualmente: en este tipo de lista enlazada, cada nodo contiene un campo de datos y un campo de enlace, que contiene la dirección del siguiente nodo en la secuencia.
- Listas doblemente enlazadas: En este tipo de lista enlazada, cada nodo contiene dos campos de enlace, que contienen las direcciones de los nodos anterior y siguiente en la secuencia.
Las siguientes operaciones se pueden realizar en una lista enlazada:
- Inserción: agrega un nuevo nodo a la lista.
- Eliminación: elimina un nodo de la lista.
- Transversal: Muestra los datos almacenados en los nodos de la lista.
- Buscar: busca un elemento de datos determinado en la lista.
- Reverse: Invierte el orden de los nodos en la lista.
Hay tres formas de insertar un nodo en una lista enlazada:
- Inserción al principio de la lista: En este tipo de inserción, el nuevo nodo se inserta al principio de la lista.
- Inserción al final de la lista: En este tipo de inserción, el nuevo nodo se inserta al final de la lista.
- Inserción en medio de la lista: En este tipo de inserción, el nuevo nodo se inserta en medio de la lista.
Hay tres formas de eliminar un nodo en una lista enlazada:
- Eliminación al principio de la lista: En este tipo de eliminación, el nodo a eliminar es el primer nodo de la lista.
- Eliminación al final de la lista: En este tipo de eliminación, el nodo a eliminar es el último nodo de la lista.
- Eliminación en medio de la lista: En este tipo de eliminación, el nodo a eliminar se encuentra en la mitad de la lista.
Hay dos formas de recorrer una lista enlazada:
-
Recorrido iterativo: En este tipo de recorrido, usamos un bucle para visitar cada nodo de la lista.
-
Recorrido recursivo: En este tipo de recorrido, usamos una función recursiva para visitar cada nodo de la lista.
Hay dos formas de buscar un elemento de datos determinado en una lista vinculada:
-
Búsqueda iterativa: En este tipo de búsqueda, usamos un bucle para visitar cada nodo de la lista hasta encontrar el elemento de datos deseado.
-
Búsqueda recursiva: En este tipo de búsqueda, utilizamos una función recursiva para visitar cada nodo de la lista hasta encontrar el elemento de datos deseado.
Hay dos formas de invertir una lista enlazada:
-
Método iterativo: en este método, usamos un ciclo para invertir los punteros de los nodos en la lista.
-
Método recursivo: En este método, usamos una función recursiva para invertir los punteros de los nodos en la lista.