Lista enlazada para niños

En el mundo de la informática, una lista enlazada es una forma especial de organizar la información. Imagina que tienes una serie de cajas, pero en lugar de estar una al lado de la otra en un estante (como en un array), cada caja tiene una nota que te dice dónde encontrar la siguiente caja. Así es como funciona una lista enlazada.

Cada "caja" se llama nodo. Un nodo guarda un dato (como un número o una palabra) y también una "dirección" o "enlace" que apunta al siguiente nodo en la secuencia. La gran ventaja de las listas enlazadas es que puedes añadir o quitar nodos fácilmente en cualquier lugar, sin tener que mover todas las demás cajas. Sin embargo, no puedes ir directamente a una caja específica; tienes que seguir los enlaces desde el principio hasta encontrarla.

Existen varios tipos de listas enlazadas, como las simples, las doblemente enlazadas y las circulares. Muchos lenguajes de programación como Lisp, Scheme y Haskell ya tienen herramientas para trabajar con ellas. Otros lenguajes como C, C++ y Java usan referencias para construirlas.

Historia de las Listas Enlazadas

¿Quién inventó las listas enlazadas?

Las listas enlazadas fueron creadas entre 1955 y 1956 por Cliff Shaw y Herbert Simón en la empresa RAND Corporation. Las usaron como la base para su lenguaje de programación llamado Lenguaje de Procesamiento de la Información (IPL).

¿Para qué se usaron al principio?

IPL se utilizó para desarrollar programas de inteligencia artificial, como la Máquina de la Teoría General y el Solucionador de Problemas Generales. También se usó para un programa de ajedrez en computadora. Los diagramas que muestran los nodos como bloques con flechas que apuntan al siguiente nodo aparecieron en un trabajo de Newell y Shaw. En 1975, Newell y Simón recibieron un premio importante, el ACM Turing Award, por sus contribuciones a la inteligencia artificial y al procesamiento de listas.

Otros usos tempranos

Víctor Yngve del Instituto Tecnológico de Massachusetts (MIT) también usó listas enlazadas en su lenguaje de programación COMIT, que ayudaba a traducir lenguajes naturales. Esto fue importante para la Lingüística computacional.

En 1958, se creó LISP, un lenguaje muy importante que se enfoca en el "procesamiento de listas". Las listas enlazadas son una de sus estructuras de datos principales.

Para la década de 1960, la utilidad de las listas enlazadas ya era muy reconocida. Bert Green del MIT publicó un estudio en 1961 que resumía sus ventajas.

Listas enlazadas en sistemas operativos

Algunos sistemas operativos, como los desarrollados por Technical Systems Consultants (TSC), usaron listas enlazadas simples para organizar sus archivos. Un archivo podía apuntar al primer sector de datos, y luego cada parte del archivo indicaba dónde estaba la siguiente.

El sistema operativo TSS de IBM también usaba listas doblemente enlazadas para su catálogo de archivos. Esto permitía organizar los directorios de forma similar a como lo hace Unix, con carpetas dentro de otras carpetas.

Tipos de Listas Enlazadas

¿Cuáles son los tipos principales de listas enlazadas?

Existen diferentes formas de construir listas enlazadas, cada una con sus propias características.

Listas Simples Enlazadas

En este tipo, cada nodo tiene solo un enlace que apunta al siguiente nodo. Una variable especial guarda la referencia al primer nodo de la lista. El último nodo apunta a un valor especial llamado NULL (o nulo), que indica que es el final de la lista.

Una lista simplemente enlazada que contiene tres valores enteros

Listas Doblemente Enlazadas

Estas listas son más avanzadas. Cada nodo tiene dos enlaces: uno que apunta al nodo anterior y otro que apunta al nodo siguiente. Si es el primer nodo, el enlace anterior es nulo; si es el último, el enlace siguiente es nulo. Esto permite recorrer la lista en ambas direcciones.

Una lista doblemente enlazada que contiene tres valores enteros

Listas Enlazadas Circulares

En una lista enlazada circular, el último nodo se conecta con el primer nodo, formando un círculo. Esto se puede hacer tanto con listas simples como con doblemente enlazadas. Puedes empezar a recorrer la lista desde cualquier nodo y seguir los enlaces hasta volver al punto de partida.

Una lista enlazada circular que contiene tres valores enteros

Listas Simples Enlazadas Circulares

Son como las listas simples, pero el último nodo apunta al primero. Esto es útil para añadir elementos rápidamente al principio o para acceder al primer nodo desde el último.

Listas Doblemente Enlazadas Circulares

Combinan las características de las listas doblemente enlazadas y las circulares. Cada nodo tiene dos enlaces, y el primer nodo se conecta con el último, y viceversa. Esto facilita las inserciones y eliminaciones en cualquier punto y permite recorrer la lista en ambas direcciones sin un principio o fin definidos.

Nodos Centinelas

A veces, las listas enlazadas tienen un "nodo centinela" (también llamado nodo ficticio) al principio o al final. Este nodo no guarda datos, sino que ayuda a simplificar las operaciones. Asegura que siempre haya un nodo anterior o posterior, incluso si la lista está vacía, lo que facilita la programación.

Aplicaciones de las Listas Enlazadas

¿Para qué se usan las listas enlazadas?

Las listas enlazadas son como bloques de construcción para otras estructuras de datos importantes, como las pilas (donde el último elemento que entra es el primero en salir, como una pila de platos) y las colas (donde el primer elemento que entra es el primero en salir, como una fila para comprar).

También se pueden usar para crear estructuras de datos más complejas, donde el dato de un nodo es, a su vez, otra lista enlazada. Esto es común en la programación funcional.

A veces, se usan para implementar "vectores asociativos" o "listas asociativas", que son como diccionarios donde cada elemento tiene una clave y un valor. Sin embargo, hay otras estructuras más eficientes para esto, como los árboles binarios.

Ventajas y Desventajas de las Listas Enlazadas

¿Por qué usar listas enlazadas en lugar de arrays?

No hay una única forma "correcta" de resolver un problema en programación. Las listas enlazadas son muy útiles en ciertas situaciones, pero pueden no ser la mejor opción en otras.

• Flexibilidad de tamaño: Las listas enlazadas pueden crecer o encogerse indefinidamente, mientras que los arrays tienen un tamaño fijo y, si se llenan, necesitan ser redimensionados, lo cual puede ser complicado.
• Ahorro de memoria: En algunos casos, se puede ahorrar memoria si varias listas comparten una parte de sus elementos.
• Inserción y eliminación: Es muy eficiente añadir o quitar elementos en cualquier parte de una lista enlazada (si ya sabes dónde quieres hacerlo). En un array, si quitas un elemento del medio, tienes que mover todos los demás.

Desventajas

• Acceso a elementos: No puedes acceder directamente a un elemento por su posición (como el elemento número 5). Tienes que empezar desde el principio y seguir los enlaces uno por uno hasta llegar a él. Esto hace que buscar un elemento por su índice sea más lento.
• Memoria extra: Cada nodo necesita espacio adicional para guardar el enlace al siguiente nodo, lo que puede ser un problema si los datos son muy pequeños.
• Asignación de memoria: Crear un nuevo nodo cada vez que añades un elemento puede ser un proceso lento.

Un ejemplo que muestra estas ventajas y desventajas es el problema de Flavio Josefo. Imagina un grupo de personas en un círculo. Cada cierto número de personas, una es eliminada. Con una lista enlazada circular, eliminar a una persona es fácil, pero encontrar a la siguiente persona a eliminar puede ser lento. Con un array, encontrar a la persona es rápido, pero eliminarla y reorganizar el resto es más complicado.

Listas Doblemente Enlazadas vs. Simples

Las listas doblemente enlazadas usan más memoria por nodo porque tienen dos enlaces, pero son más fáciles de manejar. Permiten moverse hacia adelante y hacia atrás, y puedes insertar o eliminar un nodo conociendo solo su dirección, sin necesidad de saber la del nodo anterior.

Listas Circulares vs. Lineales

Las listas circulares son buenas para representar cosas que son naturalmente circulares. Permiten recorrer la lista desde cualquier punto y acceder rápidamente al primer y último elemento con un solo puntero.

Nodos Centinelas (Nodos de Cabecera)

Usar nodos centinelas puede simplificar los algoritmos de búsqueda y ordenación. Estos nodos especiales siempre apuntan a otro elemento y nunca a nulo. El nodo centinela de cabecera, por ejemplo, apunta al primer elemento y también al último. Esto elimina la necesidad de manejar casos especiales para listas vacías o para el primer/último elemento, aunque usan un poco más de memoria.

Listas Enlazadas Usando Arrays de Nodos

En lenguajes de programación que no manejan bien las referencias directas, se pueden simular las listas enlazadas usando arrays. En lugar de punteros, cada "nodo" en el array guarda el índice (la posición) del siguiente nodo en el mismo array.

Ventajas:

• La lista se puede mover fácilmente en la memoria o guardarse en un disco.
• Para listas pequeñas, los arrays indexados pueden ocupar menos espacio que los punteros.
• Los nodos pueden guardarse juntos en la memoria, lo que mejora el rendimiento.

Desventajas:

• La implementación es más compleja.
• Si la lista es más pequeña de lo esperado, se puede desperdiciar memoria.
• Un array tiene un tamaño fijo, mientras que una lista enlazada puede crecer dinámicamente.

Este método se usa principalmente en lenguajes que no permiten asignar memoria de forma dinámica.

Lenguajes de Programación que Soportan Listas Enlazadas

Muchos lenguajes de programación como Lisp y Scheme tienen listas enlazadas simples ya integradas. En estos lenguajes, los nodos se llaman "celdas cons" y tienen dos partes: una para el dato y otra para la referencia al siguiente nodo.

En otros lenguajes que soportan tipos de datos abstractos o plantillas, se pueden usar estas herramientas para construir listas enlazadas. En lenguajes como C o Java, se construyen usando referencias y estructuras de datos.

Almacenamiento Interno y Externo

Cuando creas una lista enlazada, puedes elegir cómo guardar los datos:

• Almacenamiento interno: Los datos se guardan directamente dentro del nodo de la lista. Esto es más eficiente para acceder a los datos y simplifica la gestión de la memoria.
• Almacenamiento externo: El nodo de la lista solo guarda una referencia (un puntero) a los datos, que están guardados en otro lugar. Esto es más flexible, ya que la misma estructura de lista puede usarse para diferentes tipos de datos, y un mismo dato puede estar en varias listas.

En general, si un dato necesita estar en varias listas, el almacenamiento externo es mejor. Si un dato solo estará en una lista, el almacenamiento interno es un poco más eficiente.

Agilización de la Búsqueda

¿Cómo buscar más rápido en una lista enlazada?

Buscar un elemento específico en una lista enlazada, incluso si está ordenada, suele ser lento (se necesita tiempo O(n), lo que significa que el tiempo de búsqueda aumenta con el número de elementos). Esta es una de las principales desventajas.

Una forma sencilla de mejorar la búsqueda en una lista desordenada es mover el elemento encontrado al principio de la lista. Así, si se busca de nuevo, se encontrará más rápido. Esto es útil para crear "cachés" simples.

Otra forma es crear un "índice" externo para la lista enlazada, usando una estructura de datos más rápida como un árbol rojo-negro o una tabla hash. Estos índices apuntan a los nodos de la lista enlazada. La desventaja es que estos índices deben actualizarse cada vez que se añade o quita un nodo.

Estructuras de Datos Relacionadas

• Pilas y Colas: A menudo se implementan usando listas enlazadas, pero con reglas más estrictas sobre cómo añadir y quitar elementos.
• Lista por saltos: Es una lista enlazada mejorada con "capas" de punteros que permiten saltar grandes cantidades de elementos para una búsqueda más rápida.
• Árbol binario: Se puede ver como un tipo de lista enlazada donde los nodos se conectan de una manera más compleja, formando ramas.
• Lista enlazada desenrollada: Es una lista enlazada donde cada nodo contiene un pequeño array de datos. Esto mejora el rendimiento porque los datos están más juntos en la memoria.
• Tabla hash: Puede usar listas enlazadas para manejar situaciones donde varios elementos intentan ocupar la misma posición en la tabla.

Implementaciones

Aquí se muestran ejemplos de cómo se pueden programar las listas enlazadas en diferentes lenguajes.

Operaciones sobre listas enlazadas

Al trabajar con listas enlazadas, es importante tener cuidado al añadir o borrar nodos para no perder la conexión entre ellos.

Listas enlazadas lineales

Listas simples enlazadas

Un nodo simple tiene un dato y un puntero al siguiente nodo. La lista tiene un puntero al primer nodo.

record Node { data // El dato guardado en el nodo next // Una referencia al nodo siguiente, nulo para el último nodo }

record List { Node firstNodo // Apunta al primer nodo de la lista; nulo para la lista vacía }

Para recorrer la lista, empiezas por el primer nodo y sigues el puntero `next` hasta que llegas a `null`.

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

Para insertar un elemento después de un nodo existente:

Diagrama de cómo insertar un elemento después de otro en una lista simple.

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

Para insertar al principio de la lista:

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

Para borrar un nodo después de uno dado:

Diagrama de cómo eliminar un elemento después de otro en una lista simple.

function removeAfter(Node node) { obsoleteNode := node.next node.next := node.next.next destroy obsoleteNode }

Para borrar el primer nodo:

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

Listas doblemente enlazadas

Cada nodo tiene un dato, un puntero al siguiente y un puntero al anterior. La lista tiene punteros al primer y último nodo.

record Node { data // El dato guardado 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 }

Puedes recorrer la lista hacia adelante o hacia atrás:

Hacia Delante node := list.firstNode while node ≠ null <hacer algo con node.data> node := node.next

Hacia Atrás node := list.lastNode while node ≠ null <hacer algo con node.data> node := node.prev

Para insertar un nodo después 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

Para borrar un nodo:

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

Listas enlazadas circulares

En una lista circular, los nodos forman un bucle. No hay `null`. Si la lista no está vacía, puedes empezar a recorrerla desde cualquier nodo.

Listas enlazadas doblemente circulares

Para recorrer una lista doblemente circular desde un nodo `someNode`:

Hacia Delante node := someNode do hacer algo con node.value node := node.next while node != someNode

Hacia Atrás node := someNode do hacer algo con node.value node := node.prev while node := someNode

Para insertar un nodo después de uno dado:

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

Para borrar un nodo:

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

Listas enlazadas usando arrays de nodos

Aquí se muestra cómo se puede definir una estructura de "entrada" que contiene los índices del siguiente y anterior elemento en un array, junto con los datos.

record Entry { integer next; // índice de la nueva entrada en el array integer prev; // entrada previa string name; real balance; } Y finalmente se declara el array: integer listHead; Entry Records[1000];

Implementación de una lista enlazada en C

#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 simplemente enlazada en C++ empleando clases

//--Unit2.h-------------------------------------------------------------------------
#ifndef Unit2H
#define Unit2H
#include <iostream.h>
//---------------------------------------------------------------------------
class TElemento{
protected:
    int aInfo;
    TElemento *aSeguinte ;
public:
    TElemento(int pInfo){aInfo = pInfo; aSeguinte=NULL;};  //Construtor
    ~TElemento(){};    //Destruidor
          //Operações
    int LerInfo(){return  aInfo;};          //Ler
    void EscInfo(int pInfo){aInfo = pInfo;};  //Escrever
    TElemento *LerSeguinte(){return aSeguinte;};     //Ler
    void EscSeguinte(TElemento *pSeguinte){aSeguinte = pSeguinte;};  //Escrever
};

class TListaSL{
private:
    TElemento *aPrimeiro;
    int alongitude;
public:
    TListaSL(){aPrimeiro = NULL; alongitude = 0;}; //Construtor
    TListaSL(int pnovoelemento);                 //Construtor
    ~TListaSL(); //Destruidor
        //Operações
    int Longitud(){return alongitude;};
    bool Vazia(){return !alongitude;};
    void Adicionar(int pnovoelemento);
    void Inserir(int pnovoelemento, int pIndice);
    void Eliminar(int pIndice);
    int Obter(int pIndice);
    void Mostrar();
};

#endif
//--Final Unit2.h-------------------------------------

//--Unit2.cpp-------------------------------------------------------------------------
#pragma hdrstop
#include "Unit2.h"
#include <vcl.h>
#pragma argsused
//---------------------------------------------------------------------------

TListaSL::TListaSL(int pnovoelemento){
    aPrimeiro = new TElemento(pnovoelemento);
    alongitude = 1;
}

TListaSL::~TListaSL(){
    TElemento *cursor;
    while(aPrimeiro){
        cursor = aPrimeiro;
        cursor = aPrimeiro->LerSeguinte();
        delete cursor;
    }
}

void TListaSL::Adicionar(int pnovoelemento){
    TElemento *novoNodo = new TElemento(pnovoelemento);
    if (Vazia())
        aPrimeiro = novoNodo;
    else{
        TElemento *cursor = aPrimeiro;
        while(cursor->LerSeguinte())
            cursor = cursor->LerSeguinte();
        cursor->EscSeguinte(novoNodo);
    }
    alongitude++;
}

void  TListaSL:: Eliminar(int  pIndice  ){
    if ((pIndice<0) || (pIndice>=alongitude))
        printf("\n Nao elimino. Posicao fora de rango");   // Posiçao fora a rango
    TElemento *cursor = aPrimeiro;
    if (pIndice != 0){
        for (int i = 0; i < pIndice - 1; i++){
            cursor = cursor->LerSeguinte();
        }
        TElemento *nodoEliminar = cursor->LerSeguinte(); //referência ao nodo
        cursor->EscSeguinte(nodoEliminar->LerSeguinte());  // tirar da lista
        cursor = nodoEliminar;
    }
    else  // Eliminar o primeiro nodo
        aPrimeiro= aPrimeiro->LerSeguinte();
    delete cursor;
    alongitude--;
}

void TListaSL::Inserir(int pnovoelemento, int pIndice){
    if ((pIndice<0) || (pIndice >= alongitude))
        printf("\n Nao insiriou. Posicao fora de rango");      //Posiçao fora a rango
    TElemento *novoNodo = new TElemento(pnovoelemento);
    if (pIndice != 0){
        TElemento *cursor = aPrimeiro;
        int  contador = 1;
        while (contador < pIndice){
            cursor = cursor->LerSeguinte();  //Posicionar-se no nodo anterior
            contador++;
        }
        novoNodo->EscSeguinte(cursor->LerSeguinte());
        cursor->EscSeguinte(novoNodo);
    }
    else {
        novoNodo->EscSeguinte(aPrimeiro);       //Inserir na primeira posição
        aPrimeiro = novoNodo;
    }
    alongitude++;
}

int TListaSL::Obter(int pIndice){
    if ((pIndice<0) || (pIndice>=alongitude))
        printf("\n Nao posso mostrar. Posicao fora de rango");  //Posiçao fora a rango
    TElemento *cursor = aPrimeiro;
    for (int i = 0; i < pIndice; i++){ //Percorrer a lista até chegar ao elemento  pIndice
        cursor = cursor->LerSeguinte();
    }
    return cursor->LerInfo();
}

void TListaSL::Mostrar(){
    TElemento *cursor = aPrimeiro;
    for(int i = 0; i <= alongitude - 1; i++){
        printf("%i ", cursor->LerInfo());
        cursor = cursor->LerSeguinte();
    }
}

/* Programa principal de la aplicación con algunas operaciones de prueba */
int main(int argc, char* argv[])
{
    char espera;
    TListaSL *Lista = new TListaSL();
    Lista->Adicionar(0);
    Lista->Adicionar(3);
    Lista->Adicionar(2);
    Lista->Adicionar(12);
    Lista->Adicionar(6);
    Lista->Adicionar(9);
    Lista->Adicionar(7);
    printf("\n Lista de elementos: ");
    Lista->Mostrar();
    //printf("\n%i", Lista->Obter(3));
    Lista->Inserir(20,2);
    printf("\n Lista mas uno insertado: ");
    Lista->Mostrar();
    Lista->Eliminar(6);
    printf("\n Lista menos uno eliminado: ");
    Lista->Mostrar();
    cin >> espera;
    return 0;
};
//---------------------------------------------------------------------------

#pragma package(smart_init)

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);
}

Implementación de una lista enlazada en Maude

fmod LISTA-GENERICA {X :: TRIV} is

protecting NAT .

*** tipos

sorts ListaGenNV{X} ListaGen{X} .

subsort ListaGenNV{X} < ListaGen{X} .

*** generadores

op crear : -> ListaGen{X} [ctor] .

op cons : X$Elt ListaGen{X} -> ListaGenNV{X} [ctor] .

*** constructores

op _::_ : ListaGen{X} ListaGen{X} -> ListaGen{X} [assoc id: crear ] . *** concatenación

op invertir : ListaGen{X} -> ListaGen{X} .

op resto    : ListaGenNV{X} -> ListaGen{X} .

*** selectores

op primero : ListaGenNV{X} -> X$Elt .

op esVacia? : ListaGen{X} -> Bool .

op longitud : ListaGen{X} -> Nat .

*** variables

vars L L1 L2 : ListaGen{X} .

vars E E1 E2 : X$Elt .

*** ecuaciones

eq esVacia?(crear) = true .
eq esVacia?(cons(E, L)) = false .

eq primero(cons(E, L)) = E .

eq resto(cons(E, L)) = L .

eq longitud(crear) = 0 .
eq longitud(cons(E, L)) = 1 + longitud(L) .

eq cons(E1, L1) :: cons(E2, L2) = cons(E1, L1 :: cons(E2, L2)) .

eq invertir(crear) = crear .
eq invertir(cons(E, L)) = invertir(L) :: cons(E, crear) .

endfm

Implementación de una lista simplemente enlazada en Java empleando clases

class NodoSimple{
    int informacion;
    NodoSimple siguiente;

    public NodoSimple(int info){
        informacion=info;
        siguiente=null;
    }
}

class ListaSimplementeEnlazada{
    NodoSimple inicio, fin;

    public ListaSimplementeEnlazada(){
        inicio=fin=null;
    }

    void estaVacia(){
        if(inicio == null && fin == null)
            return true;
        return false;
    }

    void insertarEnfrente(int dato){
        NodoSimple nodito=new NodoSimple(dato);
        if(estaVacia()==true){
            inicio=nodito;
            fin=nodito;
        }
        else{
            nodito.siguiente=inicio;
            inicio=nodito;
        }

    }

    void insertarAtras(int dato){
        NodoSimple nodito=new NodoSimple(dato);
        if(estaVacia()==true){
            inicio=nodito;
            fin=nodito;
        }
        else{
            fin.siguiente=nodito;
            fin=nodito;
        }

    }

    void eliminarEnfrente(){
        if(estaVacia()==true){
            System.out.println("Lista vacía, no se puede eliminar");
        }
        else if(inicio == fin){
            inicio=null;
            fin=null;
        }
        else{
            NodoSimple auxiliar=inicio;
            System.out.println("El dato que fue eliminado es: "+inicio.informacion);
            inicio=inicio.siguiente;
            auxiliar.siguiente=null;
        }
    }

     void eliminarAtras(){
        if(estaVacia() == true){
            System.out.println("Lista vacía, no se puede eliminar");
        }
        else if(inicio == fin){
            inicio=null;
            fin=null;
        }
        else{
            NodoSimple auxiliar=inicio;
            while(auxiliar.siguiente != fin){
                auxiliar=auxiliar.siguiente;
            }
            System.out.println("El dato que fue eliminado es: "+fin.informacion);
            fin=auxiliar;
            fin.siguiente=null;
        }
    }

     void imprimirLista(){
        if(estaVacia() == true){
            System.out.println("Lista vacía");
        }
        else if(inicio == fin){
           System.out.println(inicio.informacion);
        }
        else{
            NodoSimple auxiliar=inicio;
            while(auxiliar != null){
                System.out.println(auxiliar.informacion+" ");
                auxiliar=auxiliar.siguiente;
            }
        }
    }

    public static void main(String arrr[]){
        ListaSimplementeEnlazada listita = new ListaSimplementeEnlazada();
        listita.insertarEnfrente(9);
        listita.insertarAtras(8);
        listita.insertarEnfrente(11);
        listita.insertarAtras(5);
        listita.insertarAtras(9);
        listita.imprimirLista();
        listita.eliminarAtras();
        listita.imprimirLista();
    }
}

Implementación de una lista doblemente enlazada en Java

class NodoDoble{
    int informacion;
    NodoDoble siguiente, anterior;

    public NodoDoble(int info){
        informacion=info;
        siguiente=null;
        anterior=null;
    }
}

class ListaDoblementeEnlazada{
    NodoDoble inicio, fin;

    public ListaDoblementeEnlazada(){
        inicio=fin=null;
    }

    void estaVacia(){
        if(inicio == null && fin == null)
            return true;
        return false;
    }

    void insertarEnfrente(int dato){
        NodoSimple nodito=new NodoSimple(dato);
        if(estaVacia()==true){
            inicio=nodito;
            fin=nodito;
        }
        else{
            nodito.siguiente=inicio;
            inicio.anterior=nodito;
        }
        inicio=nodito;
    }

    void insertarAtras(int dato){
        NodoSimple nodito=new NodoSimple(dato);
        if(estaVacia()==true){
            inicio=nodito;
            fin=nodito;
        }
        else{
            fin.siguiente=nodito;
            nodito.anterior=fin;
        }
        fin=nodito;
    }

    void eliminarEnfrente(){
        if(estaVacia()==true){
            System.out.println("Lista vacía, no se puede eliminar");
        }
        else if(inicio == fin){
            inicio=null;
            fin=null;
        }
        else{
            NodoSimple auxiliar=inicio;
            System.out.println("El dato que fue eliminado es: "+inicio.informacion);
            inicio=inicio.siguiente;
            auxiliar.anterior=null;
            auxiliar.siguiente=null;
            inicio.anterior=null;
        }
    }

    void eliminarAtras(){
        if(estaVacia() == true){
            System.out.println("Lista vacía, no se puede eliminar");
        }
        else if(inicio == fin){
            inicio=null;
            fin=null;
        }
        else{
            NodoSimple auxiliar=fin;
            System.out.println("El dato que fue eliminado es: "+fin.informacion);
            fin=fin.anterior;
            fin.siguiente=null;
            auxiliar.anterior=null;
            auxiliar.siguiente=null;
        }
    }

    void imprimirListaIzqDer(){//Impresion de inicio a fin
        if(estaVacia() == true){
            System.out.println("Lista vacía");
        }
        else if(inicio == fin){
           System.out.println(inicio.informacion);
        }
        else{
            NodoSimple auxiliar=inicio;
            while(auxiliar != null){
                System.out.println(auxiliar.informacion+" ");
                auxiliar=auxiliar.siguiente;
            }
        }
    }

    void imprimirListaDerIzq(){//Impresion de fin a inicio
        if(estaVacia() == true){
            System.out.println("Lista vacía");
        }
        else if(inicio == fin){
           System.out.println(inicio.informacion);
        }
        else{
            NodoSimple auxiliar=fin;
            while(auxiliar != null){
                System.out.println(auxiliar.informacion+" ");
                auxiliar=auxiliar.anterior;
            }
        }
    }

    public static void main(String arrr[]){
        ListaDoblementeEnlazada listita = new ListaDoblementeEnlazada();
        listita.insertarEnfrente(19);
        listita.insertarAtras(28);
        listita.insertarEnfrente(11);
        listita.insertarAtras(51);
        listita.insertarAtras(9);
        listita.imprimirListaIzqDer();
        listita.eliminarAtras();
        listita.imprimirListaDerIzq();
    }
}

Ejemplos de almacenamiento interno y externo

Imagina que quieres crear una lista de familias y sus miembros.

Usando almacenamiento interno, la estructura podría ser así:

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:

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, 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 un miembro 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:

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 }

Véase también

En inglés: Linked list Facts for Kids