Why no "delete" after "new" in linked list insert node

Question

I have been trying to understand memory allocation in C++ by reading some texts and looking stuff up. I have seen often that one should always call "delete" after "new". However, I also see code like this:

void LinkedList::add(int data){
    Node* node = new Node();
    node->data = data;
    node->next = this->head;
    this->head = node;
    this->length++;
}

In structures like linked lists or stacks.

I have seen some great explanations on SO like:

Why should C++ programmers minimize use of 'new'? When to use "new" and when not to, in C++?

However I am still confused why one would not call "delete" here for a new Node.

Edit: Let me clarify my question. I understand why not to immediately call delete in the same method. However, in the same code I do not see a matching delete statement for add. I assume that everything is deleted once the program ends, but I am confused that there is no apparent matching delete statement (ie: count all the news in the code, count all the deletes in the code, they do not match).

Edit: Here is the source that I am looking at: https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/

The code for their linked list:

// A complete working C++ program to demonstrate
//  all insertion methods on Linked List
#include <bits/stdc++.h>
using namespace std;
 
// A linked list node
class Node
{
    public:
    int data;
    Node *next;
};
 
/* Given a reference (pointer to pointer)
to the head of a list and an int, inserts
a new node on the front of the list. */
void push(Node** head_ref, int new_data)
{
    /* 1. allocate node */
    Node* new_node = new Node();
 
    /* 2. put in the data */
    new_node->data = new_data;
 
    /* 3. Make next of new node as head */
    new_node->next = (*head_ref);
 
    /* 4. move the head to point to the new node */
    (*head_ref) = new_node;
}
 
/* Given a node prev_node, insert a new node after the given
prev_node */
void insertAfter(Node* prev_node, int new_data)
{
    /*1. check if the given prev_node is NULL */
    if (prev_node == NULL)
    {
        cout<<"the given previous node cannot be NULL";
        return;
    }
 
    /* 2. allocate new node */
    Node* new_node = new Node();
 
    /* 3. put in the data */
    new_node->data = new_data;
 
    /* 4. Make next of new node as next of prev_node */
    new_node->next = prev_node->next;
 
    /* 5. move the next of prev_node as new_node */
    prev_node->next = new_node;
}
 
/* Given a reference (pointer to pointer) to the head
of a list and an int, appends a new node at the end */
void append(Node** head_ref, int new_data)
{
    /* 1. allocate node */
    Node* new_node = new Node();
 
    Node *last = *head_ref; /* used in step 5*/
 
    /* 2. put in the data */
    new_node->data = new_data;
 
    /* 3. This new node is going to be
    the last node, so make next of
    it as NULL*/
    new_node->next = NULL;
 
    /* 4. If the Linked List is empty,
    then make the new node as head */
    if (*head_ref == NULL)
    {
        *head_ref = new_node;
        return;
    }
 
    /* 5. Else traverse till the last node */
    while (last->next != NULL)
        last = last->next;
 
    /* 6. Change the next of last node */
    last->next = new_node;
    return;
}
 
// This function prints contents of
// linked list starting from head
void printList(Node *node)
{
    while (node != NULL)
    {
        cout<<" "<<node->data;
        node = node->next;
    }
}
 
/* Driver code*/
int main()
{
    /* Start with the empty list */
    Node* head = NULL;
     
    // Insert 6. So linked list becomes 6->NULL
    append(&head, 6);
     
    // Insert 7 at the beginning.
    // So linked list becomes 7->6->NULL
    push(&head, 7);
     
    // Insert 1 at the beginning.
    // So linked list becomes 1->7->6->NULL
    push(&head, 1);
     
    // Insert 4 at the end. So
    // linked list becomes 1->7->6->4->NULL
    append(&head, 4);
     
    // Insert 8, after 7. So linked
    // list becomes 1->7->8->6->4->NULL
    insertAfter(head->next, 8);
     
    cout<<"Created Linked list is: ";
    printList(head);
     
    return 0;
}
 
 
// This code is contributed by rathbhupendra

Answer 1

The code you cited should delete the nodes at some point. Indeed, that code shows off tons of bad C++ practices. It doesn't delete the nodes because it's bad code.

Oh and BTW: ignore anything on the site you linked to. If there is something useful on that site, it's only by accident.

Answer 2

Generally new does a couple of things. It allocates memory for an object, on the heap (where dynamic memory resides), and initialises an object at the address.

When you have variables in your function like this:

void example(){
    int a;
    char b;
}

They reside on the stack, and when the function returns, those variables no longer exist. With new you can get memory outside the stack (on the heap). The good thing is that this persists throughout function calls. The bad thing that it persists across function calls. It's good because sometimes array lengths are not known and therefore they can not be allocated on the stack, or you need a large buffer which would not fit on the stack. It's bad because if you forget about it, then it won't go away. It will just sit there taking up memory. delete, basically destructs the object at the address, and then returns the memory to the OS. That's why people say that delete should be called after new.

Luckily in modern c++ you (generally) don't need to use raw pointers and not need to worry about this. std::shared_ptr<T> created by std::make_shared<T,Args...>, and std::unique_ptr<T> created by std::make_unique<T,Args...>. These are wrappers for pointers. std::shared_ptr<T> is just T*, but when everybody loses the pointer to the object, the memory is returned. std::unique_ptr<T> is the same, but only one reference exists.

A std::unique_ptr<T> LinkedList from cppreference:

#include <memory>
struct List {
  struct Node {
    int data;
    std::unique_ptr<Node> next;
    Node(int data) : data{data}, next{nullptr} {}
  };
  List() : head{nullptr} {};
  // N.B. iterative destructor to avoid stack overflow on long lists
  ~List() { while(head) head = std::move(head->next); }
  // copy/move and other APIs skipped for simplicity
  void push(int data) {
    auto temp = std::make_unique<Node>(data);
    if(head) temp->next = std::move(head);
    head = std::move(temp);
  }
private:
  std::unique_ptr<Node> head;
};

As to an other reason the use of new should be minimised: Apart from the above issue of potential memory leak, is that it is very expensive (std::make_shared/std::make_unique still has this issue though), as the program needs to ask the kernel to grant it some memory, meaning an expensive system call must be made.