How to write a simple chained list in C++ without using <list>?

Asked

Viewed 89 times

-1

I’m using the operator delete to release an allocated memory block via new, however, when executing the code by the terminal it seems not to perform. No code error, it simply does not execute on the terminal. If I comment on the line of code on which I use the delete, ai yes the code runs normally in the terminal. I tried to run the same code in the Dev-C++ IDE and it works fine. Would anyone know why this happens? And how to fix it? the Delete is commented on the function RemovePosicao() on line 157, when running with it commented then runs on the terminal, if you take the comment then it happens what has been mentioned previously.

    #include <iostream>
    using namespace std;

    /*
    1 - instanciar lista
    2 - inserir início
    3 - inserir fim
    4 - inserir por posição
    5 - imprimir
    5.5 - tamanho
    6 - remover inicio
    7 - remover fim
    8 - remover posição
    */

// delete apontador
void ExibirMenu()
{
    cout << "\n[1] - Inserir no inicio da lista\n";
    cout << "[2] - Inserir no fim da lista\n";
    cout << "[3] - Inserir por posicao\n";
    cout << "[4] - Imprimir lista\n";
    cout << "[5] - Remover no inicio da lista\n";
    cout << "[6] - Remover no fim da lista\n";
    cout << "[7] - Remover por posicao\n";
}

struct noLista
{
    int      dado;
    noLista *prox;
};

noLista *inicializar() { return NULL; }

void inserirInicio(noLista *&l, int info)
{
    noLista *novo = new noLista;
    novo->dado    = info;
    novo->prox    = l;
    l             = novo;
}

bool RemoveInicio(noLista *&ApontadorInicioLista)
{
    if (ApontadorInicioLista != NULL)
    {
        noLista *PonteiroPegaPosicaoExcluir = ApontadorInicioLista;
        ApontadorInicioLista = ApontadorInicioLista->prox;
        // delete (PonteiroPegaPosicaoExcluir);
        return true;
    }
    else
    {
        return false;
    }
}

void inserirFim(noLista *&l, int info)
{
    noLista *novo = new noLista;
    novo->dado    = info;
    novo->prox    = NULL;
    if (l == NULL) { l = novo; }
    else
    {
        noLista *p = l;
        while (p->prox != NULL) { p = p->prox; }
        p->prox = novo;
    }
}

bool RemoveFim(noLista *&ApontadorInicioLista)
{
    noLista *PonteiroPercorre = ApontadorInicioLista;
    noLista *PonteiroGuardaPosicaoAnterior;
    if (ApontadorInicioLista == NULL) { return false; }
    else if (ApontadorInicioLista->prox == NULL)
    {
        ApontadorInicioLista = NULL;
        return true;
    }
    else
    {
        while (PonteiroPercorre->prox != NULL)
        {
            PonteiroGuardaPosicaoAnterior = PonteiroPercorre;
            PonteiroPercorre              = PonteiroPercorre->prox;
        }
        PonteiroGuardaPosicaoAnterior->prox = NULL;
        return true;
    }
}

void imprimir(noLista *l)
{
    while (l != NULL)
    {
        cout << l->dado << "\n";
        l = l->prox;
    }
}

int tamanho(noLista *l)
{
    int cont = 0;
    while (l != NULL)
    {
        cont++;
        l = l->prox;
    }
    return cont;
}

bool inserir_posicao(noLista *&l, int info, int pos)
{
    int tam = tamanho(l);
    if (pos > tam + 1) { return false; }
    else if (pos <= 0)
    {
        return false;
    }
    else
    {
        if (pos == 1) { inserirInicio(l, info); }
        else if (pos == tam + 1)
        {
            inserirFim(l, info);
        }
        else
        {
            int      cont = 1;
            noLista *novo = new noLista;
            novo->dado    = info;
            // novo->prox
            noLista *p = l;
            while (cont < pos - 1)
            {
                p = p->prox;
                cont++;
            }
            novo->prox = p->prox;
            p->prox    = novo;
        }
        return true;
    }
}

bool RemovePosicao(noLista *&ApontadorInicioLista, int Posicao)
{
    int Tamanho = tamanho(ApontadorInicioLista);
    if (Posicao > Tamanho) { return false; }
    else if (Posicao <= 0)
    {
        return false;
    }
    else
    {
        if (Posicao == 1) { RemoveInicio(ApontadorInicioLista); }
        else
        {
            int      Contador = 1;
            noLista *PonteiroPegaPosicaoAnterior;
            noLista *PonteiroPegaPosicaoDelete = ApontadorInicioLista;
            noLista *PonteiroPegaPosicaoPosteriro;
            while (Contador != Posicao)
            {
                PonteiroPegaPosicaoAnterior = PonteiroPegaPosicaoDelete;
                PonteiroPegaPosicaoDelete =
                    PonteiroPegaPosicaoDelete->prox;
                PonteiroPegaPosicaoPosteriro =
                    PonteiroPegaPosicaoDelete->prox;
                Contador++;
            }
            PonteiroPegaPosicaoAnterior->prox =
                PonteiroPegaPosicaoPosteriro;
            // delete PonteiroPegaPosicaoDelete;
        }
        return true;
    }
}

int main(int argc, char const *argv[])
{
    noLista *l1 = inicializar();
    int      Terminar, opcao, valor, posicao;
    do {
        ExibirMenu();
        cout << "\nDigite uma opcao : ";
        cin >> opcao;
        switch (opcao)
        {
            case 1:
                cout << "\nQual valor a ser inserido ? ";
                cin >> valor;
                inserirInicio(l1, valor);
                cout << "\nOperacao realizada com sucesso ! \n";
                break;
            case 2:
                cout << "\nQual valor a ser inserido ? ";
                cin >> valor;
                inserirFim(l1, valor);
                cout << "\nOperacao realizada com sucesso ! \n";
                break;
            case 3:
                cout << "\nQual valor a ser inserido ? ";
                cin >> valor;
                cout << "\nEm qual posicao ? ";
                cin >> posicao;
                if (inserir_posicao(l1, valor, posicao))
                {
                    cout << "\nOperacao realizada com sucesso ! \n";
                }
                else
                {
                    cout << "\nPosicao invalida ! \n";
                }
                break;
            case 4:
                cout << "\nAbaixo estao os elementos da lista \n\n";
                imprimir(l1);
                break;
            case 5:
                if (RemoveInicio(l1))
                {
                    cout << "\nOperacao realizada com sucesso ! \n";
                }
                else
                {
                    cout << "\nLista vazia, impossivel realizar "
                            "operacao ! \n";
                }
                break;
            case 6:
                if (RemoveFim(l1))
                {
                    cout << "\nOperacao realizada com sucesso ! \n";
                }
                else
                {
                    cout << "\nLista vazia, impossivel realizar "
                            "operacao ! \n";
                }
                break;
            case 7:
                cout << "\nQual a posicao que voce deseja excluir ? ";
                cin >> posicao;
                if (RemovePosicao(l1, posicao))
                {
                    cout << "\nOperacao realizada com sucesso ! \n";
                }
                else
                {
                    cout << "\nPosicao invalida ! \n";
                }
        }

        cout << "\n\
Deseja encerrar as operacoes com a lista ? Digite [0] para encerrar : ";
        cin >> Terminar;

    } while (Terminar != 0);
}
  • This is Undefined behaviour. You are probably accessing the memory block after using delete. But since you didn’t put in the code, hard to be sure.

  • 1

    post the code... And consider that programs running within the IDE as well as programs compiled in debug mode, are different things than the program compiled and running on the terminal.

  • Well, I posted the code, since I thought the problem was with the VS Code settings !

  • Good in this same code I managed to solve the problem, just putting the Brackets after delete and before the pointer. I wanted to know why in this case we need the brackets! delete [] PonteiroPegaPosicaoDelete;

  • You don’t need the clasps

1 answer

-2

The code as written has some problems. But on Windows 10 machine I am using worked on gcc and MSVC despite the Microsoft compiler’s uninitialized variable warnings.

  • In RemoveFim() there is no delete to the knot.
  • If you have void inserirInicio() and void inserirInicio() then instead of bool inserir_posicao() should have bool inserirPosicao(). And if all three return bool the code becomes simpler.
  • incredibly long names, as in
  bool RemovePosicao(noLista *&ApontadorInicioLista, int Posicao)
{
    int Tamanho = tamanho(ApontadorInicioLista);
    if (Posicao > Tamanho) { return false; }
    else if (Posicao <= 0)
    {
        return false;
    }
    else
    {
        if (Posicao == 1) { RemoveInicio(ApontadorInicioLista); }
        else
        {
            int      Contador = 1;
            noLista *PonteiroPegaPosicaoAnterior;
            noLista *PonteiroPegaPosicaoDelete = ApontadorInicioLista;
            noLista *PonteiroPegaPosicaoPosteriro;
            while (Contador != Posicao)
            {
                PonteiroPegaPosicaoAnterior = PonteiroPegaPosicaoDelete;
                PonteiroPegaPosicaoDelete =
                    PonteiroPegaPosicaoDelete->prox;
                PonteiroPegaPosicaoPosteriro =
                    PonteiroPegaPosicaoDelete->prox;
                Contador++;
            }
            PonteiroPegaPosicaoAnterior->prox =
                PonteiroPegaPosicaoPosteriro;
            // delete PonteiroPegaPosicaoDelete;
        }
        return true;
    }
}

do not help at all to read the code.

See this option, which also works:

bool noLista::RemovePosicao(int Posicao)
{
    if (Posicao > tamanho) return false;
    if (Posicao < 1) return false;
    if (Posicao == 1) return RemoveInicio();
    int   Contador = 1;
    Node* ant      = nullptr;
    Node* p        = inicio;
    Node* prox     = nullptr;
    while (Contador != Posicao)
    {
        ant  = p;
        p    = p->prox;
        prox = p->prox;
        Contador++;
    };  // while()
    ant->prox = prox;
    delete p;
    tamanho -= 1;
    return true;
}
  • There is no reason to use these functions like this in C++ and pass a reference to the pointer at the beginning of the list. Functions are part of the class (struct in your case). Just state there and everything gets simpler.

  • understand that a list is not a node and a node is not a list. Don’t program like that. A list is a set, possibly empty, of nodes. And each node has or indicates a given, the element of the list. In your case it is only one int. And in general within the element has a field that is called key, because in the list is in general implicit a question of order, a notion of comparison. In simple terms must be defined the operator < for the class of things you have within the list.

  • main() should be the first function of your program, if possible in a separate file.

  • one cout 7-line is much better than 7 cout one-line

You wrote:

void ExibirMenu()
{
    cout << "\n[1] - Inserir no inicio da lista\n";
    cout << "[2] - Inserir no fim da lista\n";
    cout << "[3] - Inserir por posicao\n";
    cout << "[4] - Imprimir lista\n";
    cout << "[5] - Remover no inicio da lista\n";
    cout << "[6] - Remover no fim da lista\n";
    cout << "[7] - Remover por posicao\n";
}
Mas void ExibirMenu() podia ser simplesmente int menu() e retornar a opção.     

Compare with:


char menu()
{
    char opcao[30]{0};
    do {
        cout << "\
\n\
[0] - Sair\n\
[1] - Inserir no inicio da lista\n\
[2] - Inserir no fim da lista\n\
[3] - Inserir por posicao\n\
[4] - Imprimir lista\n\
[5] - Remover no inicio da lista\n\
[6] - Remover no fim da lista\n\
[7] - Remover por posicao\n\
\n\
      Digite uma opcao (0 para sair): ";
        cin.getline(opcao, 30);

    } while ((opcao[0] < '0') || (opcao[0] > '7'));

    return (opcao[0] - '0');
}

Which has the advantage of reading the whole line. And is possibly easier to read and change. And in main() can already use the value directly as in

    while(true)
    {
        switch (menu())
        {
        }
    }   

And in a single call to cout.

Consider these definitions:

// noLista.h
struct Node
{
    int   dado;
    Node* prox;
};

struct noLista
{
    Node*   Inicio();
    void    Imprimir();
    bool    InserirFim(int info);
    bool    InserirInicio(int info);
    bool    InserirPosicao(int info, int pos);
    bool    RemoveFim();
    bool    RemoveInicio();
    bool    RemovePosicao(int Posicao);
    int     Tamanho();

    noLista();  // inicializar
    ~noLista(); // apaga tudo

   private:
    Node* inicio;
    int   tamanho;
};
// fim de noLista.h

This would be a simpler way to write what you did in C++. So the list functions are associated with a list. In general it is written that the methods of noLista are associated with instances class.

And the tamanho is part of the list, inside the struct, so you don’t have to go through the list every time you need its size. And you can use this value to control other functions.

Example:

    noLista l1; // l1 e uma lista
    l1.imprimir(); // se refere a lista l1.
    
    noLista minhalista[10]; // 10 listas ligadas
    minha_lista[4],imprimir(); // imprime o conteudo da 5a lista

A C++ example of a simple chained list

I’ll leave an example (with your code) below.

  • Understand that unless you are required by a statement or a project or a machine without resources, you should not use pointers to one side: it is more complicated and not simpler. No pointers on both sides every time you need to navigate the list you may need to reposition at the beginning (or end) and start again. Or save the missing pointer in the function again and again and again... See the example below for the functions that remove or insert at the end.

  • avoid mixing input and output with list functions. Use generic structures and you will always be able to use the same functions

  • C++ has lists in <list>. It’s always about seeing the methods offered,

  • In general functions that insert or remove by position are not so useful in lists and stacks, and a function that lists all exist only for testing. list is a container to simple navigation and quick insertion. And in general inserts and removes in an order determined by the operator < which must exist for the class of the list.

  • see in the example how to encode the functions that manipulate the list: they stay INSIDE the structure and therefore do not need to pass a pointer to the list. This is encapsulation and is generally much more convenient.

The code of the example

There are many reasons to write like this, but C++ programs often have a code file and a header file for each class.

In that case here is the class Node, that here is a struct, and the class noLista which is also a struct.

So in this example the normal is to have 3 files: noList. h with the statements, noList.cpp with the implementation of the functions, and the file . cpp calling the functions.

So you can write various programs that use noLista.cpp. Or you can write several test implementations for struct defined in noLista.h

noLista. h

// noLista.h
struct Node
{
    int   dado;
    Node* prox;
};

struct noLista
{
    Node*   Inicio();
    void    Imprimir();
    bool    InserirFim(int info);
    bool    InserirInicio(int info);
    bool    InserirPosicao(int info, int pos);
    bool    RemoveFim();
    bool    RemoveInicio();
    bool    RemovePosicao(int Posicao);
    int     Tamanho();

    noLista();  // inicializar
    ~noLista(); // apaga tudo

   private:
    Node* inicio;
    int   tamanho;
};
// fim de noLista.h

an implementation of NoLista.h

#include <iomanip>
#include <iostream>
#include "noLista.h"
using namespace std;

// constroi uma lista vazia
noLista::noLista()
{
    inicio  = nullptr;
    tamanho = 0;
};  // inicializar

// apaga a lista
noLista::~noLista()
{
    for (int i = 0; i < tamanho; i += 1) RemoveInicio();
};

// os metodos 

Node* noLista::Inicio() { return inicio; }

void noLista::Imprimir()
{
    int   nc = 0;
    cout << "Total de " << tamanho << " elementos:\n\n";
    Node* p = inicio;
    for ( int i = 0; i<tamanho; i+=1, p=p->prox)
    {
        cout << setw(4) << p->dado << " ";
        if (++nc % 10 == 0) cout << "\n";  // 10 por linha
    }
    cout << "\n";
}

bool noLista::InserirInicio(int info)
{
    Node* novo = new Node;
    novo->dado = info;
    novo->prox = inicio;
    inicio     = novo;
    tamanho += 1;
    return true;
}

bool noLista::InserirFim(int info)
{
    Node* novo = new Node;
    novo->dado = info;
    novo->prox = NULL;
    if (tamanho == 0) return InserirInicio(info);
    Node* p = inicio;
    while (p->prox != NULL) { p = p->prox; }
    p->prox = novo;
    tamanho += 1;
    return true;
}

bool noLista::InserirPosicao(int info, int pos)
{
    if (pos > tamanho + 1) return false;
    if (pos <= 0) return false;
    if (pos == 1) return InserirInicio(info);
    if (pos == tamanho) return InserirFim(info);
    Node* novo = new Node;
    novo->dado = info;

    Node* p = inicio;
    // avanca pos - 1 nodes
    for (int cont = 1; cont < pos; cont += 1) p = p->prox;
    novo->prox = p->prox;
    p->prox    = novo;
    tamanho += 1;
    return true;
}

bool noLista::RemoveFim()
{
    if (tamanho == 0) return false;
    if (tamanho == 1) { return RemoveInicio(); }
    Node* ant = nullptr;
    Node* p = inicio;
    while (p->prox != NULL)
    {
        ant = p;
        p              = p->prox;
    }
    if (ant != nullptr)
        ant->prox = NULL;
    else
        inicio = nullptr;
    delete p;
    tamanho -= 1;
    return true;
}

bool noLista::RemoveInicio()
{
    if (tamanho == 0) return true;  // vazia
    Node* novo_inicio = inicio->prox;
    delete inicio;
    inicio = novo_inicio;
    tamanho -= 1;
    return true;
}

bool noLista::RemovePosicao(int Posicao)
{
    if (Posicao > tamanho) return false;
    if (Posicao < 1) return false;
    if (Posicao == 1) return RemoveInicio();
    int   Contador = 1;
    Node* ant      = nullptr;
    Node* p        = inicio;
    Node* prox     = nullptr;
    while (Contador != Posicao)
    {
        ant  = p;
        p    = p->prox;
        prox = p->prox;
        Contador++;
    };  // while()
    ant->prox = prox;
    delete p;
    tamanho -= 1;
    return true;
}

int noLista::Tamanho() { return tamanho; }

The functions usually have about 10 lines of code and there is not much to comment on. It is practical your code after all.

main() with my original

#include <iostream>
using namespace std;

#include "noLista.h"
char        menu();

int main(void)
{
    noLista l1;
    int     posicao = 0;
    int     valor = 0;

    while(true)
    {
        switch (menu())
        {
            case 0:
                return 0; // fim
                break;

            case 1:
                cout << "\nQual valor a ser inserido ? ";
                cin >> valor;
                l1.InserirInicio(valor);
                cout << "\nOperacao realizada com sucesso ! \n";
                break;

            case 2:
                cout << "\nQual valor a ser inserido ? ";
                cin >> valor;
                l1.InserirFim(valor);
                cout << "\nOperacao realizada com sucesso ! \n";
                break;

            case 3:
                cout << "\nQual valor a ser inserido ? ";
                cin >> valor;
                cout << "\nEm qual posicao ? ";
                cin >> posicao;
                if ( l1.InserirPosicao(valor, posicao))
                    cout << "\nOperacao realizada com sucesso ! \n";
                else
                    cout << "\nPosicao invalida ! \n";
                break;

            case 4:
                cout << "\nAbaixo estao os elementos da lista \n\n";
                l1.Imprimir();
                break;

            case 5:
                if (l1.RemoveInicio())
                    cout << "\nOperacao realizada com sucesso ! \n";
                else
                    cout << "\nLista vazia, impossivel realizar "
                            "operacao ! \n";
                break;

            case 6:
                if (l1.RemoveFim())
                    cout << "\nOperacao realizada com sucesso ! \n";
                else
                    cout << "\nLista vazia, impossivel realizar "
                            "operacao ! \n";
                break;

            case 7:
                cout << "\nQual a posicao que voce deseja excluir ? ";
                cin >> posicao;
                if (l1.RemovePosicao(posicao))
                    cout << "\nOperacao realizada com sucesso ! \n";
                else
                    cout << "\nPosicao invalida ! \n";
        }
    };  // while()
    return 0; // para contentar o compilador
}

char menu()
{
    char opcao[30]{0};
    do
    {
        cout << "\
\n\
[0] - Sair\n\
[1] - Inserir no inicio da lista\n\
[2] - Inserir no fim da lista\n\
[3] - Inserir por posicao\n\
[4] - Imprimir lista\n\
[5] - Remover no inicio da lista\n\
[6] - Remover no fim da lista\n\
[7] - Remover por posicao\n\
\n\
      Digite uma opcao (0 para sair): ";
        cin.getline(opcao, 30);

    }   while ((opcao[0] < '0') || (opcao[0] > '7'));

    return (opcao[0] - '0');
}

And you can see how it looks simpler.

On the other hand, as the files are separated, you can use other test programs without touching nonLista.cpp...

a test program for functions

#include <iostream>
using namespace std;
#include "noLista.h"
int main(void)
{
    noLista l1;
    int     posicao = 0;
    int     valor   = 0;
    for ( int valor = 20; valor>=1; valor-=1 ) 
       l1.InserirPosicao(valor,1);
    l1.Imprimir();
    cout << "Tamanho agora: " << l1.Tamanho() << endl;
    while (1)
    {
        if (l1.RemovePosicao(1)) 
            cout << "RemoveFim() ok, restam " << l1.Tamanho() << "\n";
        else
        {
            cout << "RemoveFim() Erro restam " << l1.Tamanho() << "\n";
            break;
        }
    }
    l1.Imprimir();
    return 0;  // para contentar o compilador
}

This test only inserts 20 stops in the first position, shows and then removes the first one until it is wrong, so the list at the end will be empty...

So you can write small programs and test the functions without tampering with the list code...

Exit from this test

Total de 20 elementos:

   1    2    3    4    5    6    7    8    9   10
  11   12   13   14   15   16   17   18   19   20

Tamanho agora: 20
RemoveFim() ok, restam 19
RemoveFim() ok, restam 18
RemoveFim() ok, restam 17
RemoveFim() ok, restam 16
RemoveFim() ok, restam 15
RemoveFim() ok, restam 14
RemoveFim() ok, restam 13
RemoveFim() ok, restam 12
RemoveFim() ok, restam 11
RemoveFim() ok, restam 10
RemoveFim() ok, restam 9
RemoveFim() ok, restam 8
RemoveFim() ok, restam 7
RemoveFim() ok, restam 6
RemoveFim() ok, restam 5
RemoveFim() ok, restam 4
RemoveFim() ok, restam 3
RemoveFim() ok, restam 2
RemoveFim() ok, restam 1
RemoveFim() ok, restam 0
RemoveFim() Erro restam 0
Total de 0 elementos:

Browser other questions tagged

You are not signed in. Login or sign up in order to post.