[c/c++] For who think they don't need to use dynamic allocation (malloc, calloc) for data structures

Look at the following code to add a node to a queue


void Queue1::add(int p_data)
{
Node newNode;
newNode.data = p_data;
newNode.next = 0;

// if tail exists
if(tail)
{
tail->next = &newNode;
tail = tail->next;
}
// otherwise
else
{
head = &newNode;
tail = &newNode;
}
}

This will not work as the 'newNode' created is only sitting on the stack not on the heap, therefore, every time this method is called, head and tail will be pointing at some junk from the get go.

We want the head to stay where it is and move the tail, hence need to put every Node created onto the heap.


void Queue1::add(int p_data)
{
Node* newNodePtr = (Node*) calloc(1, sizeof(Node));
newNodePtr->data = p_data;
newNodePtr->next = 0;

// if tail exists
if(tail)
{
tail->next = newNodePtr;
tail = tail->next;
}
// otherwise
else
{
head = newNodePtr;
tail = newNodePtr;
}
}

The full version of the main code file:

#include "Queue1.h"


Queue1::Queue1(void)
{
    head = 0;
    tail = 0; 
}


Queue1::~Queue1(void)
{
}


void Queue1::add(int p_data)
{
    Node* newNodePtr = (Node*) calloc(1, sizeof(Node)); 
    newNodePtr->data = p_data;
    newNodePtr->next = 0; 

    // if tail exists
    if(tail)
    {        
        tail->next = newNodePtr;
        tail = tail->next;
    }
    // otherwise
    else
    {
        head = newNodePtr;
        tail = newNodePtr;
    }
}

int Queue1::remove()
{
    int data = -1;
    if (head)
    {
        data = head->data;
        if (head == tail)
            tail = tail->next; 
        Node* temp = head;
        head = head->next;

        // so how to free the previous header occupied block?
        free(temp);
    }
    return data; 
}

int main(int argc, char* argv[]) 
{
    Queue1 q1; 
    q1.add(1); 
    q1.add(2);

    q1.remove();
    q1.remove(); 
}