Lista enlazada

Una lista enlazada  es una estructura de datos dinámica básica en informática, que consta de nodos que contienen datos y enlaces ("enlaces") al nodo siguiente y/o anterior de la lista. [1] La ventaja fundamental sobre una matriz es la flexibilidad estructural: el orden de los elementos de una lista enlazada puede no coincidir con el orden de los elementos de datos en la memoria de la computadora [2] , y el orden de recorrido de la lista siempre es establecido explícitamente por sus enlaces internos.

Tipos de listas enlazadas

Lista enlazada lineal

Lista enlazada individualmente (lista enlazada individualmente)

Una lista lineal de dirección única es una estructura de datos que consta de elementos del mismo tipo, vinculados secuencialmente a través de punteros. Cada elemento de la lista tiene un puntero al siguiente elemento. El último elemento de la lista apunta a NULL . El elemento al que no se apunta es el primer elemento (encabezado) de la lista. Aquí, el enlace en cada nodo apunta al siguiente nodo de la lista. En una lista enlazada individualmente, solo puede moverse hacia el final de la lista. Es imposible averiguar la dirección del elemento anterior en función del contenido del nodo actual.

En informática , una lista lineal generalmente se define como un tipo de datos abstractos (ADT) que formaliza la noción de una colección ordenada de datos . En la práctica, las listas lineales suelen implementarse mediante matrices y listas enlazadas. A veces, el término "lista" también se usa informalmente como sinónimo de "lista enlazada". Por ejemplo, un ADT de lista mutable sin tipo se puede definir como un conjunto de constructor y operaciones básicas:

  • Una operación que comprueba si una lista está vacía.
  • Tres operaciones de agregar un objeto a la lista (al principio, al final o dentro después de cualquier (n-ésimo) elemento de la lista);
  • Una operación que evalúa el primer elemento (cabeza) de una lista;
  • Una operación para acceder a una lista que consta de todos los elementos de la lista original excepto el primero.
Características
  • Longitud de la lista . El número de elementos en la lista.
  • Las listas pueden escribirse o no escribirse . Si se escribe una lista, entonces se da el tipo de sus elementos, y todos sus elementos deben ser de tipos que sean compatibles con el tipo dado de elementos de la lista. La mayoría de las listas están escritas.
  • La lista puede estar ordenada o no ordenada .
  • Dependiendo de la implementación, puede ser posible el acceso aleatorio a los elementos de la lista.
Lista de enlaces simples en lenguajes de programación

xi

lista de estructuras { campo int ; // lista de estructura de campo de datos * siguiente ; // puntero al siguiente elemento };

usando una lista enlazada simple:

lista de estructuras * l1 = ( lista de estructuras * ) malloc ( tamaño de ( lista de estructuras )); l1 -> campo = 1 ; l1 -> siguiente = ( lista de estructuras * ) malloc ( tamaño de ( lista de estructuras )); l1 -> siguiente -> campo = 2 ; l1 -> siguiente -> siguiente = ( lista de estructuras * ) malloc ( tamaño de ( lista de estructuras )); /* etc. */ Lista doblemente enlazada (lista doblemente enlazada)

Aquí, los enlaces en cada nodo apuntan al nodo anterior y siguiente de la lista. Al igual que una lista con enlace simple, una lista con enlace doble permite solo el acceso secuencial a los elementos, pero también permite el movimiento en ambas direcciones. En esta lista, es más fácil eliminar y reorganizar elementos, ya que las direcciones de aquellos elementos de la lista cuyos punteros se dirigen al elemento que se está modificando son fácilmente accesibles.

Lista enlazada XOR

Raramente usado.

Lista enlazada circular

Un tipo de lista enlazada es una lista en anillo (cíclica, cerrada). También puede ser de enlace simple o de enlace doble. El último elemento de una lista circular contiene un puntero al primero y el primero (en el caso de una lista doblemente enlazada) al último.

Por regla general, dicha estructura se implementa sobre la base de una lista lineal. Cada lista circular almacena adicionalmente un puntero al primer elemento. No hay ninguna referencia a NULL en esta lista.

También hay listas circulares con un elemento de encabezado dedicado para que sea más fácil recorrer toda la lista.

Saltar lista

Lista enlazada ampliada

Beneficios

  • eficiente (en tiempo constante) agregando y quitando elementos
  • el tamaño está limitado solo por la cantidad de memoria de la computadora y la profundidad de bits de los punteros
  • adición y eliminación dinámica de elementos

Desventajas

Las desventajas de las listas enlazadas se derivan de su propiedad principal: el acceso secuencial a los datos:

  • la complejidad del acceso directo al elemento, es decir, determinar la dirección física por su índice (número de serie) en la lista
  • los campos de puntero (punteros al elemento siguiente y anterior) consumen memoria adicional (en matrices , por ejemplo, no se necesitan punteros)
  • algunas operaciones con listas son más lentas que con matrices, ya que solo se puede acceder a un elemento arbitrario de la lista pasando por todos los elementos que lo preceden
  • los elementos de la lista vecinos pueden asignarse de forma no local en la memoria, lo que reducirá la eficiencia del almacenamiento en caché de datos en el procesador
  • en comparación con las matrices, es mucho más difícil (aunque posible) realizar operaciones de vectores paralelos en listas vinculadas, como calcular la suma: la sobrecarga de iterar sobre los elementos reduce la eficiencia de la paralelización

Véase también

Notas

  1. ↑ Cormen, Leiserson, Rivest y Stein. Introducción a los Algoritmos, 2ª edición. La prensa del MIT, 2001. ISBN 0-262-03293-7
  2. ↑ Alineación de datos
 Estructuras de datos
Liza
Árboles
cuenta
Otro