void Lista::insere(const int val)
{
No* novo = new No(val);
if (tamanho == 0)
{
ini = fim = novo;
tamanho = 1;
return;
};
// busca a posicao
No* p = ini;
while (p != nullptr)
{ // enquanto nao acabar a lista
if (val < p->info)
{ // vai inserir antes de p
if (p->ant == nullptr)
{
// insere no inicio
novo->ant = nullptr;
novo->prox = ini;
ini->ant = novo;
ini = novo;
tamanho += 1;
return;
}
else
{ // insere no meio
p->ant->prox = novo;
novo->ant = p->ant;
novo->prox = p;
tamanho += 1;}
tamanho += return;1;
}return;
}
else
{
// no fim da lista?
if (p->prox == nullptr)
{
p->prox = novo;
novo->ant = p;
novo->prox = nullptr;
fim = novo;
tamanho += 1;
return;
}
else
{
// ainda na busca, avanca
p = p->prox;
}
}; // if()
}; // while()
return;
};
#include <iostream>
using namespace std;
#include "Lista.h"
int main(void)
{
Lista uma;
cout << uma; // vazia
// insere os impares de 1 a 19
cout << uma;
for (int i = 1; i < 20; i += 2) uma.insere(i);
// insere os pares de 20 a 2
for (int i = 20; i > 1; i -= 2) uma.insere(i);
// insere de 0 a -9
for (int i = 0; i > -10; i -= 1) uma.insere(i);
// devem ser 30 elementos
cout << uma;
return 0;
}
#include <iostream>
#include "Lista.h"
Lista::Lista() : tamanho(0), ini(nullptr), fim(nullptr){};
Lista::~Lista()
{ // apaga todo mundo
std::cout << "Apaga: ";
if (tamanho == 0) return; // vazia
No* p = ini;
No* prox = p->prox;
for (size_t i = 0; i < tamanho-1; i += 1)
{
std::cout << p->info << ", ";
delete p;
p = prox;
prox, prox = p->prox;
}
std::cout << p->info << "\n";
delete p;
}
void Lista::insere(const int val)
{
No* novo = new No(val);
if (tamanho == 0)
{
ini = fim = novo;
tamanho = 1;
return;
};
// busca a posicao
No* p = ini;
while (p != nullptr)
{ // enquanto nao acabar a lista
if (val < p->info)
{ // vai inserir antes de p
if (p->ant == nullptr)
{
// insere no inicio
novo->ant = nullptr;
novo->prox = ini;
ini->ant = novo;
ini = novo;
tamanho += 1;
return;
}
else
{ // insere no meio
p->ant->prox = novo;
novo->ant = p->ant;
novo->prox = p;
tamanho += 1;}
tamanho += return;1;
}return;
}
else
{
// no fim da lista?
if (p->prox == nullptr)
{
p->prox = novo;
novo->ant = p;
novo->prox = nullptr;
fim = novo;
tamanho += 1;
return;
}
else
{
// ainda na busca, avanca
p = p->prox;
}
}; // if()
}; // while()
return;
};
size_t Lista::size() { return tamanho; }
bool Lista::vazia() { return tamanho == 0; };
std::ostream& operator<<(std::ostream& out, Lista& L)
{
if (L.vazia())
{
out << "Lista vazia\n";
return out;
}
std::cout << "Lista tem " << L.tamanho << " elementos:\n";
Lista::No* p = L.ini; // inicio
for (size_t i = 0; i < L.tamanho - 1; i += 1)
{
out << p->info << ", ";
p = p->prox;
};
out << p->info << "\n\n";
return out;
}
A memória é liberada ao final e deixei uns cout
para o teste, mas pode ser exagero: é só para ilustrar o funcionamento.
O programa todo tem então esses 3 arquivos que mostrei apenas: List.h Lista.cpp e main.cpp