C++ Circular doubly linked list (com nó sentinela)

[Visitante]

Alguém sabe qual a maneira correta de implementar o ~List() e a função reverse()? Essa clear() provavelmente também tem algum problema, porque os nodes n são deletados, apenas parei de apontar pra eles, infelizmente n achei mt coisa sobre, e o que vi na gringa era em java e n usavam nó sentinela, se puderem dar um Norte, eu agradeço.

obs: as outras funções estão ok, eu as coloquei caso ajude a entender o tipo de estrutura q tô tentando desenvolver.

 

List.h

#ifndef LIST_H
#define LIST_H
#include <iostream>

using Ost = std::ostream;

struct Node
{
    int data;
    Node *next;
    Node *prev;

    Node(int value = 0) : data(value) {this->next = this, this->prev = this;}
};

class List 
{
    private:
        int m_size;
        Node *head;
        Node *sentinel;

    public:
        List();
        //~List();
        //List(const List& lst); // Copy constructor

    public:
        void push_back(const int& value);
        void push_front(const int& value);
        size_t size() const; 
        bool empty() const;
        void clear();
        void pop_back();
        void pop_front();
        void insertAt(int index, const int& value);
        void removeAt(int index);
        int& front();
        int& back();
        //void reverse();
        int& operator[](int index);
        //void swap(List& lst);
        //void concat(List& lst);
        //List& operator=(const List& lst);

        friend Ost& operator<<(Ost& out, const List& l);
};

#endif

 

List.cpp

#include "List.h"
#include <iostream>


List::List() : m_size(0) 
{
    sentinel->next = sentinel->prev = sentinel;
    sentinel->data = 0;
    head = sentinel; 
    std::cerr << "Created circular doubly linked list\n";
}

/*
List::~List()
{
    clear();
    std::cerr << "Destroyed list\n";
}

/*
void List::reverse()
{
    if(sentinel->next == sentinel)
    {
        return throw new std::out_of_range("erro: empty list");
    }
    Node *temp = new Node(0);
    Node *aux = sentinel->next;
    while(sentinel->next != sentinel)
    {
        temp = sentinel->next;
        sentinel->next = sentinel->prev;
        sentinel->prev = temp;
        sentinel = sentinel->prev;
    }
    
}
*/

bool List::empty() const {return sentinel->next == sentinel;}

void List::clear()
{
    sentinel->next = sentinel->prev = sentinel;
    m_size = 0;
}
 
void List::push_back(const int& value)
{
    Node *novo       = new Node(value);
    novo->next       = sentinel;
    novo->prev       = sentinel->prev;
    novo->prev->next = novo;
    sentinel->prev   = novo;
    m_size++;
}

void List::push_front(const int& value)
{
    Node *novo       = new Node(value);
    novo->next       = sentinel->next;
    sentinel->next   = novo;
    novo->prev       = sentinel;
    novo->next->prev = novo;
    m_size++;
}

size_t List::size() const {return m_size;}

void List::pop_back()
{
    if(sentinel->next == sentinel)
    {
        return throw std::out_of_range("error: empty list");
    }
    Node *last       = sentinel->prev;
    sentinel->prev   = last->prev;
    last->prev->next = sentinel;
    delete last;
    m_size--;
}

void List::pop_front()
{
    if(sentinel->next == sentinel)
    {
        return throw std::out_of_range("error: empty list");
    }
    Node *aux       = sentinel->next;
    sentinel->next  = aux->next;
    aux->next->prev = sentinel;
    delete aux;
    m_size--;
}

void List::insertAt(int index, const int& value)
{
    if(index < 0 || index > m_size) 
    {
        return throw std::out_of_range("error");
    }
    if(index == 0)
    {
        Node *novo = new Node(value);
        novo->next = sentinel->next;
        novo->prev = sentinel;
        sentinel->next->prev = novo;
        sentinel->next = novo;
        m_size++;
        return;
    }
    Node *novo = new Node(value);
    Node *aux = sentinel->next;
    int cont = 0;
    while (cont < index - 1)
    {
        aux = aux->next;
        cont++;
    }
    novo->next = aux->next;
    novo->prev = aux;
    aux->next->prev = novo;
    aux->next = novo;
    m_size++;
}

void List::removeAt(int index)
{
    if(index < 0 || index > m_size) 
    {
        return throw new std::out_of_range("error");
    }
    if(index == 0)
    {
        Node *out = sentinel->next;
        out->next->prev = sentinel;
        sentinel->next = out->next;
        delete out;
        m_size--;
    }
    Node *aux = sentinel->next;
    int cont = 0;
    while(cont < index - 1)
    {
        aux = aux->next;
        cont++;
    }
    Node *out = aux->next;
    out->next->prev = aux;
    aux->next = out->next;
    delete out;
    m_size--;
}

int& List::front()
{
    return sentinel->next->data;
}

int& List::back()
{
    if(sentinel->next == sentinel)
    {
        throw std::out_of_range("error: empty list");
    }
    return sentinel->prev->data;
}

int& List::operator[](int index)
{
    if(index < 0 || index >= m_size) 
    {
        throw std::out_of_range("error: invalid index");
    }
    int cont = 0;
    Node *aux = sentinel->next;
    while(cont < index)
    {
        aux = aux->next;
        cont++;
    }
    return aux->data;
}

Ost& operator<<(Ost& out, const List& l) 
{
    out << "(" <<  l.m_size << " Elementos)\n";
    Node *temp = l.sentinel->next;
    out << "[ ";
    while(temp->next != l.sentinel)
    {
        out << temp->data << " ";
        temp = temp->next;
    }
    out << temp->data;
    out << " ]";
    return out;
}

 

main.cpp

#include <iostream>
#include "List.h"

using namespace std;

int main()
{   
    int i = 1;
    List lista;

    cout << lista << "\n\n";

    while(i < 11) 
    {
        lista.push_back(i);
        i++;  
    }

    cout << lista << "\n";

    cout << "\n====> retornou de operator[6]()\n";
    cout << lista[6] << "\n";

    lista.insertAt(2, 90);
    cout << "\n====> retornou de insertAt(2, 90)\n";
    cout << lista << "\n"; 

    lista.removeAt(0);
    cout << "\n====> retornou de removeAt(0)\n";
    cout << lista << "\n"; 
  
    lista.pop_back();
    cout << "\n====> retornou de pop_back()\n";
    cout << lista << "\n";

    lista.pop_front();
    cout << "\n====> retornou de pop_front()\n";
    cout << lista << "\n";

    cout << "\n====> retornou de front()\n";
    cout << lista.front() << "\n";

    cout << "\n====> retornou de back()\n";
    cout << lista.back() << "\n";

    lista.clear();
    cout << "\n====> retornou de clear()\n";
    cout << lista << "\n"; 


    return 0;
}

 

3 minutos atrás, Prodigy085 disse:

obs: as outras funções estão ok, eu as coloquei caso ajude a entender o tipo de estrutura q tô tentando desenvolver.

 

[arfneto]

Em 14/01/2022 às 00:09, Prodigy085 disse:

Alguém sabe qual a maneira correta de implementar o ~List() e a função reverse()? Essa clear() provavelmente também tem algum problema, porque os nodes n são deletados, apenas parei de apontar pra eles, infelizmente n achei mt coisa sobre, e o que vi na gringa era em java e n usavam nó sentinela, se puderem dar um Norte, eu agradeço.

obs: as outras funções estão ok, eu as coloquei caso ajude a entender o tipo de estrutura q tô tentando desenvolver

 

Em geral uma lista circular não usa alocação de memória. Essas listas são usadas para controlar recursos importantes e limitados, como buffers de transmissão, segmentos de vídeo, ou pools de threads,  onde o que chega TEM que ser tratado e o mais antigo é descarado.

 

Mas continua sendo uma lista e pode usar os exemplos que te mostrei na semana passada e repor a alocação de memória. Ou nem isso, porque como eu te disse nessas listas se procura performance máxima.

 

reverse() com ponteiros para os dois lados é trivial. Qual a dificuldade que está tendo?

 

Com ponteiros para os dois lados --- que é bem mais simples que sua lista anterior --- pode usar size() e não precisa de uma sentinela. 

 

Se precisa usar pelo enunciado ou por decisão, apenas crie um registro a mais na criação da lista e defina o conteúdo para esse que será o registro sentinela.

 

Em geral NÃO se usa sentinela em listas circulares porque pode gastar justamente dos recursos que está tentando gerenciar.

 

 

[Visitante]

13 horas atrás, arfneto disse:

Em geral uma lista circular não usa alocação de memória. Essas listas são usadas para controlar recursos importantes e limitados, como buffers de transmissão, segmentos de vídeo, ou pools de threads,  onde o que chega TEM que ser tratado e o mais antigo é descarado.

Entendi, é que nesse caso eu deveria fazer dessa maneira, com nó sentinela e alocação de memória.

 

13 horas atrás, arfneto disse:

reverse() com ponteiros para os dois lados é trivial. Qual a dificuldade que está tendo?

Então, é que a função deveria trocar tudo que era next por prev e depois a função operator<< deveria imprimir a lista invertida, se fosse apenas para a reverse() imprimir a lista invertida ia ser bem mais simples, era só começar um laço em sentinel->prev e ir incrementando sentinel, mas eu consegui implementar da maneira que foi pedido.

 

Outra função que eu estava com problema era a destrutora, o programa simplesmente travava quando deveria destruir a lista, no caso estava faltando uma função Node construtora apenas para a sentinela, porque diferente dos outros Nodes ela não precisa de um valor (sentinel->data), antes eu inicializava sentinel->data = 0, e isso realmente seria um problema caso eu resolvesse usar a lista com strings, só fiz isso e a destrutora voltou a funcionar, algo assim:

Node() : next(this), prev(this) { } // Sentinel constructor

Node(Item data) : data(data) {next = nullptr, prev = nullptr // Node constructor

 

A destrutora ficou assim:

List::~List()
{
    clear();
    std::cerr << "Destroyed list\n";
}

 

clear:

void List::clear() {while(!this->empty()) this->pop_back();}

 

[arfneto]

7 horas atrás, Prodigy085 disse:

Então, é que a função deveria trocar tudo que era next por prev e depois a função operator<< deveria imprimir a lista invertida, se fosse apenas para a reverse() imprimir a lista invertida ia ser bem mais simples

 

Um ponteiro não sabe se aponta para frente ou para trás. Então se usar apenas um ponteiro na função que lista tanto faz se vai para frente ou para tras... O código não vai saber. E a condição de parada nem precisa de empty() ou sentinela, memo que tenha. Porque? por que sabe --- ou deveria saber --- exatamente quantos elementos listar: size()

 

7 horas atrás, Prodigy085 disse:

clear:

void List::clear() {while(!this->empty()) this->pop_back();}

 

Provavelmente é mais simples usar size() para destruir a lista...