Representación y manipulación de estructuras lineales dinámicas; tablas de dispersión

Listas

Es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio.

Pseudocógicos

<estructura> elemento {

elemento* siguiente = NULL;

int dato;

}

void main() {

elemento* primero = NULL;

primero = inserta(3, primero);

primero = inserta(7, primero);

primero = elimina(3, primero);

return;

}

Enlazado doble

• En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al último nodo de la lista, y el puntero derecho del último nodo apunta al primer nodo de la lista.

Debido a que las listas dobles circulares son más eficientes, los algoritmos que en esta sección se traten serán sobre listas dobles circulares.

En la figura siguiente se muestra un ejemplo de una lista doblemente ligada lineal que almacena números:

Añadir un elemento entre elementos existentes

Cuando añadimos al final, actualizamos un solo puntero.

Eliminar un elemento entre elementos existentes

Si eliminamos el primer elemento, simplemente actualizamos el puntero desde nuestro programa al inicio de la lista.