Enlazos De C++

LISTAS ENLAZADAS DEFENICION

Qué es una lista? Una lista enlazada es un conjunto de elementos llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo, donde el orden de los mismos se establece mediante punteros. La idea básica es que cada componente de la lista incluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista. El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista. El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.

Listas Enlazadas frente a Arrays

Las listas enlazadas tienen las siguientes ventajas sobre los arrays:

• No requieren memoria extra para soportar la expansión. Por el contrario, los arrays requieren memoria extra si se necesita expandirlo (una vez que todos los elementos tienen datos no se pueden añadir datos nuevos a un array).

• Ofrecen una inserción/borrado de elementos más rápida que sus operaciones equivalentes en los arrays. Sólo se tienen que actualizar los enlaces después de identificar la posición de inserción/borrado. Desde la perspectiva de los arrays, la inserción de datos requiere el movimiento de todos los otros datos del array para crear un elemento vacío. De forma similar, el borrado de un dato existente requiere el movimiento de todos los otros datos para eliminar el elemento vacío.

En contraste, los arrays ofrecen las siguiente ventajas sobre las listas enlazadas:

• Los elementos de los arrays ocupan menos memoria que los nodos porque no requieren campos de enlace.

• Los arrays ofrecen un aceso más rápido a los datos, medante índices basados en enteros.

LISTA ENLAZADA SIMPLE

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

LISTAS ENLAZADAS DOBLES

Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL o a la lista vacía si es el primer nodo; y otro que apunta al siguiente nodo siguiente, o apunta al valor NULL o a la lista vacía si es el último nodo.

Listas enlazadas circulares

En una lista enlazada circular,

...