Listas enlazadas. Generalidades. C y C++

Listas enlazadas lineales

Listas simples enlazadas

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo (o indica que tiene la dirección en memoria del siguiente nodo) en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Listas doblemente enlazadas

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

En algún lenguaje de muy bajo nivel, XOR-Linking ofrece una vía para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque esta técnica no se suele utilizar.

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Listas enlazadas simples circulares

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo.

Listas enlazadas doblemente circulares

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.

Nodos centinelas

A veces las listas enlazadas tienen un nodo centinela (también llamado falso nodo o nodo ficticio) al principio o al final de la lista, el cual no es usado para guardar datos. Su propósito es simplificar o agilizar algunas operaciones, asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la lista (incluso alguna que no contenga datos) siempre tenga un “primer y último” nodo.

Aplicaciones de las listas enlazadas

Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.

El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta practica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.

A veces, las listas enlazadas son usadas para implementar vectores asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar éstas estructuras, por ejemplo con árboles binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas más eficientemente para recorrer ésta serie de datos.

Doblemente enlazadas vs. simplemente enlazadas

Las listas doblemente enlazadas requieren más espacio por nodo y sus operaciones básicas resultan más costosas pero ofrecen una mayor facilidad para manipular ya que permiten el acceso secuencial a lista en ambas direcciones. En particular, uno puede insertar o borrar un nodo en un número fijo de operaciones dando únicamente la dirección de dicho nodo (Las listas simples requieren la dirección del nodo anterior para insertar o suprimir correctamente). Algunos algoritmos requieren el acceso en ambas direcciones.

Circulares enlazadas vs. lineales enlazadas

Las listas circulares son más útiles para describir estructuras circulares y tienen la ventaja de poder recorrer la lista desde cualquier punto. También permiten el acceso rápido al primer y último elemento por medio de un puntero simple.

Implementaciones

Aquí se expone el código necesario para complementar el artículo a fin de poder realizar una lectura ágil sobre el artículo y a su vez quien necesite el código pueda fácilmente encontrar el mismo si está contenido.

Operaciones sobre listas enlazadas

Cuando se manipulan listas enlazadas, hay que tener cuidado con no usar valores que hayamos invalidado en asignaciones anteriores. Esto hace que los algoritmos de insertar y borrar nodos en las listas sean algo especiales. A continuación se expone el pseudocódigo para añadir y borrar nodos en listas enlazadas simples, dobles y circulares.

Listas enlazadas lineales

Listas simples enlazadas

Nuestra estructura de datos tendrá dos campos. Vamos a mantener la variables PrimerNodos que siempre apunta al primer nodo de tal lista, ó nulo para la lista vacía.

 record Node {
    data // El dato almacenado en el nodo
    next // Una referencia al nodo siguiente, nulo para el último nodo
 }
 record List {
     Node PrimerNodo   // Apunta al primer nodo de la lista; nulo para la lista vacía
 }

El recorrido en una lista enlazada es simple, empezamos por el primer nodo y pasamos al siguiente hasta que la lista llegue al final.

 node := list.PrimerNodo
 while node not null {
     node := node.next
 }

El siguiente código inserta un elemento a continuación de otro en una lista simple.

 function insertAfter(Node node, Node newNode) {
     newNode.next := node.next
     node.next    := newNode
 }

Insertar al principio de una lista requiere una función por separado. Se necesita actualizar PrimerNodo.

 function insertBeginning(List list, Node newNode) {
     newNode.next   := list.firstNode
     list.firstNode := newNode
 }

De forma similar, también tenemos funciones para borrar un nodo dado ó para borrar un nodo del principio de la lista.

 function removeAfter(Node node) { 
     obsoleteNode := node.next
     node.next := node.next.next
     destroy obsoleteNode
 }
 function removeBeginning(List list) { 
     obsoleteNode := list.firstNode
     list.firstNode := list.firstNode.next          
     destroy obsoleteNode
 }

Advertimos que BorrarPrincipio pone PrimerNodo a nulo cuando se borra el último elemento de la lista. Adjuntar una lista enlazada a otra puede resultar ineficiente a menos que se guarde una referencia a la cola de la lista, porque si no tendríamos que recorrer la lista en orden hasta llegar a la cola y luego añadir la segunda lista.

Listas doblemente enlazadas

Con estas listas es necesario actualizar muchos más punteros pero también se necesita menos información porque podemos usar un puntero para recorrer hacia atrás y consultar elementos. Se crean nuevas operaciones y elimina algunos casos especiales. Añadimos el campo anterior a nuestros nodos, apuntando al elemento anterior, y UltimoNodo a nuestra estructura, el cual siempre apunta al último elemento de la lista. PrimerNodo y UltimoNodo siempre están a nulo en la lista vacía.

 record Node {
    data // El dato almacenado en el nodo
    next // Una referencia al nodo siguiente, nulo para el último nodo
    prev // Una referencia al nodo anterior, nulo para el primer nodo
 }
 record List {
     Node firstNode   // apunta al primer nodo de la lista; nulo para la lista vacía
     Node lastNode    // apunta al último nodo de la lista; nulo para la lista vacía
 }

Formas de recorrer la lista:

Hacia Delante

 node := list.firstNode
 while node ≠ null
     <do something with node.data>
     node := node.next

Hacia Atrás

 node := list.lastNode
 while node ≠ null
     <do something with node.data>
     node := node.prev

Estas funciones simétricas añaden un nodo después o antes de uno dado:

 function insertAfter(List list, Node node, Node newNode)
     newNode.prev := node
     newNode.next := node.next
     if node.next = null
         node.next := newNode
         list.lastNode := newNode
     else
         node.next.prev := newNode
         node.next := newNode
 function insertBefore(List list, Node node, Node newNode)
     newNode.prev := node.prev
     newNode.next := node
     if node.prev is null
         node.prev := newNode
         list.firstNode := newNode
     else
         node.prev.next := newNode
         node.prev := newNode

También necesitamos una función para insertar un nodo al comienzo de una lista posiblemente vacía.

 function insertBeginning(List list, Node newNode)
     if list.firstNode = null
         list.firstNode := newNode
         list.lastNode  := newNode
         newNode.prev := null
         newNode.next := null
     else
         insertBefore (list, list.firstNode, newNode)

Una función simétrica que inserta al final:

 function insertEnd(List list, Node newNode)
     if list.lastNode = null
         insertBeginning (list, newNode)
     else
         insertAfter (list, list.lastNode, newNode)

Borrar un nodo es fácil, solo requiere usar con cuidado firstNode y lastNode.

 function remove(List list, Node node)
   if node.prev = null
       list.firstNode := node.next
   else
       node.prev.next := node.next
   if node.next = null
       list.lastNode := node.prev
   else
       node.next.prev := node.prev
   destroy node

Una consecuencia especial de este procedimiento es que borrando el último elemento de una lista se ponen PrimerNodo y UltimoNodo a nulo, habiendo entonces un problema en una lista que tenga un único elemento.

Listas enlazadas circulares

Estas pueden ser simples o doblemente enlazadas. En una lista circular todos los nodos están enlazados como un círculo, sin usar nulo. Para listas con frente y final (como una cola), se guarda una referencia al último nodo de la lista. El siguiente nodo después del último sería el primero de la lista. Los elementos se pueden añadir por el final y borrarse por el principio en todo momento. Ambos tipos de listas circulares tienen la ventaja de poderse recorrer completamente empezando desde cualquier nodo. Esto nos permite normalmente evitar el uso de PrimerNodo y UltimoNodo, aunque si la lista estuviera vacía necesitaríamos un caso especial, como una variable UltimoNodo que apunte a algún nodo en la lista o nulo si está vacía. Las operaciones para estas listas simplifican el insertar y borrar nodos en una lista vacía pero introducen casos especiales en la lista vacía.

Listas enlazadas doblemente circulares

Asumiendo que someNodo es algún nodo en una lista no vacía, esta lista presenta el comienzo de una lista con someNode.

Hacia Delante

 node := someNode
 do
     do something with node.value
     node := node.next
 while node != someNode

Hacia Atrás

 node := someNode
 do
     do something with node.value
     node := node.prev
 while node := someNode


Esta función inserta un nodo en una lista enlazada doblemente circular después de un elemento dado:

 function insertAfter(Node node, Node newNode)
     newNode.next := node.next
     newNode.prev := node
     node.next.prev := newNode
     node.next      := newNode

Para hacer “insertBefore”, podemos simplificar “insertAfter (node.prev, newNode)”. Insertar un elemento en una lista que puede estar vacía requiere una función especial.

 function insertEnd(List list, Node node)
     if list.lastNode = null
         node.prev := node
         node.next := node
     else
         insertAfter (list.lastNode, node)
     list.lastNode := node

Para insertar al principio simplificamos “insertAfter (list.lastNode, node)”.

 function remove(List list, Node node)
     if node.next = node
         list.lastNode := null
     else
         node.next.prev := node.prev
         node.prev.next := node.next
         if node = list.lastNode
             list.lastNode := node.prev;
     destroy node

Como una lista doblemente enlazada, “removeAfter” y “removeBefore” puede ser implementada con “remove (list, node.prev)” y “remove (list, node.next)”.

Listas enlazadas usando vectores de nodos

Previamente se crea una estructura que contiene los apuntadores:

record Entry {
    integer next; // índice de la nueva entrada en el vector
    integer prev; // entrada previa
    string name;
    real balance;
 }

Y finalmente se declara el vector: integer listHead;

Entry Records[1000];

Implementación de una lista enlazada en C

Las listas enlazadas son típicamente construidas usando referencias junto con el tipo de dato record

#include <stdio.h>   /* for printf */
#include <stdlib.h>  /* for malloc */
 
typedef struct ns {
	int data;
	struct ns *next;
} node;
 
node *list_add(node **p, int i) {
    /* algunos compiladores no requieren un casting del valor del retorno para malloc  */
    node *n = (node *)malloc(sizeof(node));
    if (n == NULL)
        return NULL;
    n->next = *p;                                                                            
    *p = n;
    n->data = i;
    return n;
}
 
void list_remove(node **p) { /* borrar cabeza*/
    if (*p != NULL) {
        node *n = *p;
	*p = (*p)->next;
	free(n);
    }
}
 
node **list_search(node **n, int i) {
    while (*n != NULL) {
        if ((*n)->data == i) {
            return n;
        }
        n = &(*n)->next;
    }
    return NULL;
}
 
void list_print(node *n) {
    if (n == NULL) {
        printf("lista esta vacía\n");
    }
    while (n != NULL) {
        printf("print %p %p %d\n", n, n->next, n->data);
        n = n->next;
    }
}
 
int main(void) {
    node *n = NULL;
 
    list_add(&n, 0); /* lista: 0 */
    list_add(&n, 1); /* lista: 1 0 */
    list_add(&n, 2); /* lista: 2 1 0 */
    list_add(&n, 3); /* lista: 3 2 1 0 */
    list_add(&n, 4); /* lista: 4 3 2 1 0 */
    list_print(n);
    list_remove(&n);            /* borrar primero(4) */
    list_remove(&n->next);      /* borrar nuevo segundo (2) */
    list_remove(list_search(&n, 1)); /* eliminar la celda que contiene el 1 (primera) */
    list_remove(&n->next);      /* eliminar segundo nodo del final(0)*/
    list_remove(&n);            /* eliminar ultimo nodo (3) */
    list_print(n);
 
    return 0;
}

Implementación de una lista enlazada en C++

#include <iostream>    // Para cout
#include <sstream>     // Utilizado para validar entradas del teclado
#include <new>         // Utilizado para validad reservacion de memoria al utilizar el operator NEW.
using namespace std
 
struct camera_t {
     int idcam;
     string serial;
     int idroom;
     camera_t *next;
 };
 
 
//Insertar al principio de una lista requiere una función por separado. Se necesita actualizar PrimerNodo.
void list_add(camera_t **node_cam)
{
    camera_t *newnode = new (nothrow) camera_t;
    if(newnode==NULL){
        cout << "Error. No possible allocate memory to new node.";
    }
    else{
        newnode->next = *node_cam;
        *node_cam = newnode;
        cout << "Hola";
    }
}
 
//El recorrido en una lista enlazada es simple, empezamos por el primer nodo y pasamos al siguiente hasta
// que la lista llegue al final.
void list_print(camera_t *node_cam)
{
    if (node_cam == NULL){
        cout << "Lista vacia";
    }
    else{
        while (node_cam!=NULL)
        {
            cout << "idcam: " << node_cam->idcam << "\nName: " << node_cam->name << "\nModel: " << node_cam->model;
            cout << "\nSerial: " << node_cam->serial << "\nIdRoom: " << node_cam->idroom << "\nNameRoom: " << node_cam->room;
            cout << "\n\n";
            node_cam = node_cam->next;
        }
    }
}
 
int main(void)
{
     string mystr;
     camera_t *node_cam = 0;
 
     cout << "Ingrese los datos de la camara." << endl;
 
     list_add(&node_cam);
 
     cout << "Indentificador de camara: 23";
     node_cam->idcam = N_globalCamera;
     node_cam->name = "PanSonyc";
     cout << "Precione una tecla para regresar al menu principal.";
     getline(cin,mystr);
 
    list_print(node_cam);
}

Ejemplos de almacenamiento interno y externo

Suponiendo que queremos crear una lista enlazada de familias y sus miembros. Usando almacenamiento interno, la estructura podría ser como la siguiente:

 record member { // miembro de una familia 
     member next
     string firstName
     integer age
 }
 record family { // // la propia familia 
     family next
     string lastName
     string address
     member members // de la lista de miembros de la familia
 }

Para mostrar una lista completa de familias y sus miembros usando almacenamiento interno podríamos escribir algo como esto:

 aFamily := Families // comienzo de la lista de familias
 while aFamily ≠ null { // bucle a través de la lista de familias
     print information about family
     aMember := aFamily.members // coger cabeza de esta lista de miembros de esta familia
     while aMember ≠ null { //bucle para recorrer la lista de miembros
         print information about member
         aMember := aMember.next
     }
     aFamily := aFamily.next
 }

Usando almacenamiento externo, nosotros podríamos crear las siguientes estructuras:

 record node { // estructura genérica de enlace
     node next
     pointer data // puntero genérico del dato al nodo
 }
 record member { // estructura de una familia
     string firstName
     integer age
 }
 record family { // estructura de una familia
     string lastName
     string address
     node members // cabeza de la lista de miembros de esta familia
 }

Para mostrar una lista completa de familias y sus miembros usando almacenamiento externo, podríamos escribir:

 famNode := Families // comienzo de la cabeza de una lista de familias
 while famNode ≠ null { // bucle de lista de familias
     aFamily = (family) famNode.data // extraer familia del nodo
     print information about family
     memNode := aFamily.members // coger lista de miembros de familia
     while memNode ≠ null { bucle de lista de miembros
         aMember := (member) memNode.data // extraer miembro del nodo
         print information about member
         memNode := memNode.next
     }
     famNode := famNode.next
 }

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *