title: Is my implementation of stack pop leaking memory?
body: <p>I am doing this for learning purpose. From what I have learnt, every <code>new</code> needs to have corresponding <code>delete</code>. Is my <code>pop()</code> definition causing memory leak? It pops out <code>head</code>, but I don't know how to delete just the <code>head</code>. </p>
  
  <p>From my understanding, it may not have memory leak, but I am not sure (Valgrind didn't find anything):</p>
  
  <ol>
  <li>save the <code>head</code> pointer in <code>temp</code> pointer.</li>
  <li>point <code>head</code> to <code>head-&gt;next</code>.</li>
  <li>return the <code>data</code> in <code>temp</code>.</li>
  <li>the memory free automatically at the end of <code>}</code> block.</li>
  </ol>
  
  <p>But from my understanding, what I really really want to do is to call <code>delete head</code>. Because <code>head</code> is in the heap and it needs to be deleted when popped. But I am also thinking that since its a recursive data structure, if I call <code>delete head</code>, I will delete everything recursively like I defined it in <code>~Node()</code>, right? If I want to save <code>head</code> in a <code>temp</code> point like this <code>Node* temp = head</code>, won't I just make a copy? So I tried using <code>Node*temp = std::move(head); head = std::move(temp-&gt;next); delete temp;</code>, then an error pops up <code>free(): double free detected in tcache 2</code>, what does that mean? At this point, I don't know how to proceed. I have searched everywhere and can't find a solution. Tried this, with no success:</p>
  
  <ol>
  <li>save the <code>head</code> pointer in <code>temp</code> pointer.</li>
  <li>save the <code>data</code> from <code>temp-&gt;data</code>.</li>
  <li>point <code>head</code> to <code>head-&gt;next</code>.</li>
  <li>set <code>temp-&gt;next</code> to <code>nullptr</code>?
  
  <ul>
  <li>cause <code>temp</code> holds recursive nodes</li>
  <li>how do I extract just the <code>head</code> without those nodes in <code>next</code>?</li>
  </ul></li>
  <li><code>delete temp</code> to delete the original <code>head</code>?</li>
  <li>return the <code>data</code>.</li>
  </ol>
  
  <p>I know how to implement this using <code>unique_ptr</code>, which solves all my problems and makes me worry free. But I need to know how to do this manually.</p>
  
  <pre><code>template&lt;typename Data&gt;
  class ListStack {
  public:
      ListStack(): head{nullptr} {}
  
      ~ListStack();
  
      [[nodiscard]] bool isEmpty() const;
  
      void push(Data const &amp;data);
  
      Data pop();
  
  private:
      struct Node {
          Data data;
          Node* next;
  
          explicit Node(Data const &amp;data, Node* next=nullptr) : data{data}, next{next} {}
  
          ~Node() { delete next; }
      };
  
      Node* head;
  };
  
  template&lt;typename Data&gt;
  bool ListStack&lt;Data&gt;::isEmpty() const {
      return head == nullptr;
  }
  
  template&lt;typename Data&gt;
  void ListStack&lt;Data&gt;::push(Data const &amp;data) {
      head = new Node(data, head);
  }
  
  template&lt;typename Data&gt;
  Data ListStack&lt;Data&gt;::pop() {
      if (isEmpty()) {
          throw std::out_of_range("ListStack underflow");
      }
      Node* temp = head;
      head = head-&gt;next;
      return temp-&gt;data;
  }
  
  template&lt;typename Data&gt;
  ListStack&lt;Data&gt;::~ListStack() { delete head; }
  </code></pre>
  
  <p>Another try with last resort using recursive delete, why error <code>free(): invalid pointer</code>?</p>
  
  <pre><code>template&lt;typename Data&gt;
  Data ListStack&lt;Data&gt;::pop() {
      if (isEmpty()) {
          throw std::out_of_range("ListStack underflow");
      }
      Node* temp = new Node(head-&gt;next-&gt;data, head-&gt;next-&gt;next);
      Data data = head-&gt;data;
      delete head;
      head = temp;
      return data;
  }
  </code></pre>
  
  <p>Working example using <code>unique_ptr</code>, please tell me if there is anything wrong:</p>
  
  <pre><code>template&lt;typename Data&gt;
  Data ListStack&lt;Data&gt;::pop() {
      if (isEmpty()) {
          throw std::out_of_range("ListStack underflow");
      }
      Data data = head.get()-&gt;data;
  
      // ~Node() and ~ListStack() are not implemented, using default.
      // head and next are std::unique_ptr&lt;Node&gt;
      head = std::move(head.get()-&gt;next);
      // here the original head has no one owns it, so it gets freed automatically.
      return data;
  }
  </code></pre>