Implementación de Listas de Listas Encadenadas y Circulares en C++

Listas de Listas Encadenadas

A continuación se detallan las operaciones fundamentales de inserción y eliminación para una estructura de datos basada en listas de listas encadenadas implementadas mediante vectores de nodos.

Inserción en una Sublista Encadenada

bool Insertar(int aplista, int p, Nodo A)
{
    int i;
    if (ListaLlena())
    {
        return false;
    }
    else
    {
        i = Buscar_Nodo();
        lista[i].Dato(A.Dato());
        if (p == -1)
        {
            if (ListaVacia(aplista))
            {
                lista[aplista].ApuntadorAbajo(i);
                lista[i].ApuntadorAbajo(-1);
                lista[i].Apuntador(-1);
            }
            else
            {
                lista[i].ApuntadorAbajo(lista[aplista].ApuntadorAbajo());
                lista[i].Apuntador(-1);
                lista[aplista].ApuntadorAbajo(i);
            }
        }
        else
        {
            lista[i].ApuntadorAbajo(lista[p].ApuntadorAbajo());
            lista[p].ApuntadorAbajo(i);
            lista[p].Apuntador(-1);
        }
        return true;
    }
}

Eliminación en la Lista Principal

bool Eliminar(int p, Nodo &A)
{
    int i;
    if (ListaVacia())
    {
        return false;
    }
    else
    {
        if (p == -1)
        {
            A = lista[list];
            i = list;
            list = lista[list].Apuntador();
        }
        else
        {
            i = lista[p].Apuntador();
            A = lista[i];
            lista[p].Apuntador(lista[i].Apuntador());
        }
        Liberar_Nodo(i);
        return true;
    }
}

Eliminación en una Sublista Encadenada

bool Eliminar(int aplista, int p, Nodo &A)
{
    int i;
    if (ListaVacia(aplista))
    {
        return false;
    }
    else
    {
        if (p == -1)
        {
            A = lista[lista[aplista].ApuntadorAbajo()];
            i = lista[aplista].ApuntadorAbajo();
            lista[aplista].ApuntadorAbajo(lista[i].ApuntadorAbajo());
        }
        else
        {
            i = lista[p].ApuntadorAbajo();
            A = lista[i];
            lista[p].ApuntadorAbajo(lista[i].ApuntadorAbajo());
        }
        Liberar_Nodo(i);
        return true;
    }
}

Listas de Listas Circulares Encadenadas

En esta variante, los nodos de la estructura se interconectan de forma circular tanto en la lista principal como en sus niveles inferiores.

Inserción Ordenada en Sublista Circular

void InsertarOrdenadamente(int aplista, Nodo x)
{
    int i, ap;
    i = this->Primero(aplista);
    ap = -1;
    if (this->ListaVacia(aplista))
    {
        this->Insertar(aplista, -1, x);
    }
    else
    {
        while ((x.Dato() > Lista(i).Dato()) && (i != this->FinDeLista(aplista)))
        {
            ap = i;
            i = this->ProximoAbajo(i);
        }
        this->Insertar(aplista, ap, x);
    }
}

Inserción en la Lista Circular Principal

bool Insertar(int p, Nodo A)
{
    int i;
    if (ListaLlena())
    {
        return false;
    }
    else
    {
        i = BuscarNodo();
        lista[i].Dato(A.Dato());
        if (A.ApuntadorAbajo() == -1)
        {
            lista[i].ApuntadorAbajo(i);
        }
        else
        {
            lista[i].ApuntadorAbajo(A.ApuntadorAbajo());
            if (lista[i].ApuntadorAbajo() != i)
            {
                lista[A.Apuntador()].ApuntadorAbajo(i);
            }
        }
        if (p == -1)
        {
            if (ListaVacia())
            {
                lista[i].Apuntador(i);
                list = i;
            }
            else
            {
                lista[i].Apuntador(lista[list].Apuntador());
                lista[list].Apuntador(i);
            }
        }
        else
        {
            if (p == list)
            {
                lista[i].Apuntador(lista[list].Apuntador());
                list = i;
            }
            else
            {
                lista[i].Apuntador(lista[p].Apuntador());
            }
            lista[p].Apuntador(i);
        }
        return true;
    }
}

Inserción en Sublista Circular

bool Insertar(int aplista, int p, Nodo A)
{
    int i;
    if (ListaLlena())
    {
        return false;
    }
    else
    {
        i = BuscarNodo();
        lista[i].Dato(A.Dato());
        if (p == -1)
        {
            if (ListaVacia(aplista))
            {
                lista[aplista].ApuntadorAbajo(i);
                lista[i].ApuntadorAbajo(aplista);
                lista[i].Apuntador(-1);
            }
            else
            {
                lista[i].ApuntadorAbajo(lista[aplista].ApuntadorAbajo());
                lista[i].Apuntador(-1);
                lista[aplista].ApuntadorAbajo(i);
            }
        }
        else
        {
            lista[i].ApuntadorAbajo(lista[p].ApuntadorAbajo());
            lista[p].ApuntadorAbajo(i);
            lista[p].Apuntador(-1);
        }
        return true;
    }
}

Eliminación en la Lista Circular Principal

bool Eliminar(int p, Nodo &A)
{
    int i;
    if (ListaVacia())
    {
        return false;
    }
    else
    {
        if (p == -1)
        {
            A = lista[lista[list].Apuntador()];
            i = lista[list].Apuntador();
            if (A.ApuntadorAbajo() != i)
            {
                A.Apuntador(Ultimo(i));
            }
            else
            {
                A.ApuntadorAbajo(-1);
            }
            if (list == lista[list].Apuntador())
            {
                list = -1;
            }
            else
            {
                lista[list].Apuntador(lista[i].Apuntador());
            }
        }
        else
        {
            i = lista[p].Apuntador();
            A = lista[i];
            if (A.ApuntadorAbajo() != i)
            {
                A.Apuntador(Ultimo(i));
            }
            else
            {
                A.ApuntadorAbajo(-1);
            }
            lista[p].Apuntador(lista[i].Apuntador());
            if (i == list)
            {
                list = p;
            }
        }
        LiberarNodo(i);
        return true;
    }
}

Eliminación en Sublista Circular

bool Eliminar(int aplista, int p, Nodo &A)
{
    int i;
    if (ListaVacia(aplista))
    {
        return false;
    }
    else
    {
        if (p == -1)
        {
            A = lista[lista[aplista].ApuntadorAbajo()];
            i = lista[aplista].ApuntadorAbajo();
            lista[aplista].ApuntadorAbajo(lista[i].ApuntadorAbajo());
        }
        else
        {
            i = lista[p].ApuntadorAbajo();
            A = lista[i];
            lista[p].ApuntadorAbajo(lista[i].ApuntadorAbajo());
        }
        LiberarNodo(i);
        return true;
    }
}