-1

I'm new to C++ thus the question. I've a toy implementation of a Singly Linked List in C++.

template<typename T>
class List {
    template<typename U>
    struct Node {
        U data_;
        Node<U>* next_;

        Node() : data_(0), next_(nullptr) {}
        Node(U data) : data_(data), next_(nullptr) {}
    };

private:
    Node<T>* head_;
    std::size_t size_;

public:
    List() : head_{nullptr}, size_{0} {}

    void insert(const T& item) {
        Node<T>* p(new Node<T>(item));
        if (size_ == 0) {
            head_ = p;
        } else {
            p->next_ = head_;
            head_ = p;
        }
        size_++;
    }
    std::size_t getSize() {
        return size_;
    }

    ~List(){
    while(head_){
        Node<T> p = head_;
        delete(p);
        head_ = head_->next_;
    }
};

This code seems to work. The problem though is that the objects allocated by new are never cleaned up, despite the ~List() destructor. Can someone help me understand, how I can write a destructor for this class that cleans up all the allocated nodes ?

Important remark: I am aware that this can be done using smart pointers, but I want to understand the old school way of managing heap.

Christophe
  • 68,716
  • 7
  • 72
  • 138
Melissa Stewart
  • 3,483
  • 11
  • 49
  • 88
  • Try writing the destructor, and then ask questions about any problems you are having with it - no-one is going to write it for you. –  Dec 30 '17 at 17:05
  • A destructor for a class `T` is a member function of no arguments named `~T`. – Cheers and hth. - Alf Dec 30 '17 at 17:05
  • 1
    Do you know how to iterate over the nodes in the list? Then you basically know all you need to know. – Some programmer dude Dec 30 '17 at 17:06
  • @Incomputable I've edited the question to add my implementation of the destructor. Is that the way to do it or is there a better way. – Melissa Stewart Dec 30 '17 at 17:15
  • @NeilButterworth I've edited the question to add my implementation of the destructor. Is that the way to do it or is there a better way. – Melissa Stewart Dec 30 '17 at 17:15
  • 2
    You can't delete before you dereference. Also p should be a pointer to a node. – drescherjm Dec 30 '17 at 17:15
  • @MelissaStewart, basically what drescherjm said. Copy the next then delete, then assign current to next. Also, after you made it work correctly, if you're interested in raising implementation quality I recommend coming to [CodeReview.se]. P.S. upvoted. – Incomputable Dec 30 '17 at 17:17
  • @Incomputable I'm new to C++, I vaguely understand what you're saying, but a line of code will really help. – Melissa Stewart Dec 30 '17 at 17:18
  • 1
    @MelissaStewart Urgently recommended read: [Are there any valid use cases to use new and delete, raw pointers or c-style arrays with modern C++?](https://stackoverflow.com/questions/46991224/are-there-any-valid-use-cases-to-use-new-and-delete-raw-pointers-or-c-style-arr) – user0042 Dec 30 '17 at 17:25
  • @MelissaStewart ***"... but I want to understand the old school way of managing heap. ..."*** There never was an _"old school way"_. RAII was existing from the beginning of the c++ language. If you want to learn c idioms, then go for c please. – user0042 Dec 30 '17 at 17:29
  • @user0042 At the same time, blindly using tools like smart pointers and containers without understanding what's going on internally is not ideal either. Understanding pointers may not be the best thing to start with in general, but some people prefer to start from the technical foundations to get better understanding. And from some skill level onwards, you *need* to understand the low-level details to be able to program correctly. – Angew is no longer proud of SO Dec 30 '17 at 17:31
  • Why is `Node` a template? Will a `List` ever contain nodes which store something else than `SomeType`? – Angew is no longer proud of SO Dec 30 '17 at 17:33
  • @Angew Though that's nothing fitting well for the OP's intro _"I'm new to C++ ..."_ – user0042 Dec 30 '17 at 17:33
  • 2
    In general, you might be interested in our [list of good C++ books](https://stackoverflow.com/q/388242/1782465). – Angew is no longer proud of SO Dec 30 '17 at 17:34
  • @NeilButterworth there is a destructor in the code. It just doesn't work as OP would have expected – Christophe Dec 30 '17 at 17:47
  • 2
    @Christophe There is one _now_. –  Dec 30 '17 at 17:51

2 Answers2

7
while(head_){
    Node<T> p = head_; <-- change to pointer
    delete(p); <-- you can't delete this right now
    head_ = head_->next_;
}

p should be a pointer. You cannot delete p right away. You have to find the next node, and delete p later. Also use delete p; instead of delete (p); as follows:

~List() {
    while(head_) {
        Node<T> *p = head_;
        head_ = head_->next_;
        delete p;
    }
}

As noted in comments, Node does not need to be a template. You can simplify your class. insert can also be simplified because head_ is initialized to nullptr, you can safely assign p->next_ = head_;

template<typename T> class List {
    struct Node {
        T data_;
        Node* next_;
        Node() : data_(0), next_(nullptr) {}
        Node(T data) : data_(data), next_(nullptr) {}
    };
    Node* head_;
    std::size_t size_;
public:
    List() : head_{ nullptr }, size_{ 0 } {}

    void insert(const T& item) {
        Node* p = new Node(item);
        p->next_ = head_;
        head_ = p;
        size_++;
    }

    std::size_t getSize() {
        return size_;
    }

    ~List() {
        while(head_) {
            Node *marked = head_;
            head_ = head_->next_;
            delete marked;
        }
    }
};
Barmak Shemirani
  • 30,904
  • 6
  • 40
  • 77
0

The general idea is that you have to figure out who is the owner of the object to decide who should delete it.

In relation to nodes, the List is the owner. So you should carefully develop all the methods in a way that once the List looses the ownership of the object, it makes sure that object is deleted or the ownership is taken over.

Obvious places when you want to free the memory is, first one you delete the list. Second, when you remove an element, for example pop it.

Lets look in both cases.

First delete the list. For that you need to write a destructor, which iterates over the list and deletes elements one by one. For that I refer to the answer of @barmak-shemiani.

For the case when you pop an element you can do following:

  T pop() {
    Node<T> *tmp = head_;
    if (head_ != nullptr) {
      head_ = head_->next_;
      T data = tmp->data_;
      delete tmp;
      return data;
    }

    throw std::runtime_error("Can't pop an empty list")
  }
mcsim
  • 1,647
  • 2
  • 16
  • 35