mardi 20 février 2018

C++11 doubly linked list implementation issue

I'm learning data structures now. I decided to create my own doubly linked list.

Currently, I'm trying to implement 4 function for my doubly linked list.

void push_front(const T& data);
void push_back(const T& data);
void pop_front();
void pop_back();

I was trying to troubleshoot this over the weekend. I can't see whats missing in my code.

There's a mistake in my functions. Am I missing something?

So, I codded this:

#include <iostream>

template <typename T>
class DList{
    struct Node{
        T data_;
        Node* next_;
        Node* prev_;
        Node(const T& data=T{},Node* next=nullptr, Node* prev=nullptr){
            data_=data;
            next_=next;
            prev_=prev;
        }
    };
    Node* front_;
    Node* back_;
public:
    DList(){
        front_=nullptr;
        back_=nullptr;
    }
    void push_front(const T& data);
    void push_back(const T& data);
    void pop_front();
    void pop_back();
    void print() const;
    void reversePrint() const;
    ~DList();
};


template <typename T>
void DList<T>::push_front(const T& data){
    Node* tmp = new Node(data, front_, nullptr); // new node
    if (front_ != nullptr){
        front_->prev_ = tmp;
    }
    else{
        back_ = tmp;
    }
    front_ = tmp;

}
template <typename T>
void DList<T>::push_back(const T& data){
    Node* tmp = new Node(data,back_,nullptr);
    if(back_ != nullptr){
        back_->next_=tmp;
    }
    else{
        front_ = tmp;
    }
    back_ = tmp;
}

template <typename T>
void DList<T>::pop_front(){
    if(front_ != nullptr){
        Node* rm = front_;
        if(front_!=back_){  //make sure we have more than one node
            front_=front_->next_; //front_=rm->next_;
            front_->prev_=nullptr;
        }
        else{
            front_=back_=nullptr;
        }
    delete rm;
    }

}
template <typename T>
void DList<T>::pop_back(){
    if(back_ != nullptr){
        Node* rm = back_;
        if(back_!=front_){
            back_=back_->prev_;
            back_->next_=nullptr;
        }
        else{
            back_=front_=nullptr;
        }
    delete rm;
    }

}
template <typename T>
void DList<T>::print() const{
    Node* curr=front_;
    while(curr!=nullptr){
        std::cout << curr->data_ << " ";
        curr=curr->next_;
    }
    std::cout << std::endl;
}
template <typename T>
void DList<T>::reversePrint() const{
    Node* curr=back_;
    while(curr!=nullptr){
        std::cout << curr->data_ << " ";
        curr=curr->prev_;
    }
    std::cout << std::endl;
}
template <typename T>
DList<T>::~DList(){
    Node* curr=front_;
    while(curr){
        Node* rm=curr;
        curr=curr->next_;
        delete rm;
    }
}

Aucun commentaire:

Enregistrer un commentaire