Vfrdtyky

New learner for data structure, recently learning Listnode. Got questions.
Define a ListNode:

struct ListNode

{

    int val;

    ListNode* next;

    ListNode(int x) : val(x), next(NULL) {}

};

void AddToTail(ListNode** head, int value)

{

    ListNode* nlist = new ListNode(value);

    if(*head == NULL)

    {

        *head = nlist;

    }

    else

    {

        ListNode* p = *head;

        while(p->next != NULL)

        {

            p = p->next;

        }

        p->next = nlist;

    }

    // No need to delete nlist, since the memory allocated by it is already organized by the ListNode.

}



int main()

{

    ListNode* L = new ListNode(5);

    AddToTail(&L, 10);

    ListNode* p = L;

    while(p->next != NULL)

    {

        p = p->next;

    }

    printf("Final value is %d.n", p->val);

    delete L;

}

Till now, everything seems ok right? I wonder what if i don't allocate the ListNode memory in heap, that means i don't use new, while i use ListNode L; then initialize it manually. The memeory of it is now in stack. The tail added to it is in heap memory. How do i delete the heap memory right now. It seems part of the ListNode memory is in stack and part of it is in heap? Am i correctly understood?

Yeah, it doesn't really matter whether L is dynamically allocated or not. That's by-the-by. In fact there's no reason here to dynamically allocate it.

What matters is the ownership and lifetime of the nodes that it manages. These are dynamically allocated, so you will need a destructor inside ListNode that unlinks and de-allocates the nodes.

There's nothing wrong with "mixing" storage duration — that's what you're doing every time you instantiate a std::vector<int>, for example. You just need to ensure that anything owning dynamically allocated data has the capability to clean up after itself.

You need some delete function like this

    void DeleteList(ListNode** head)

    {

        ListNode* p = *head;

        while(p != NULL)

        {

            ListNode *t = p->next;

            delete p;

            p = t;

        }

    }



    // and call it in main:



    printf("Final value is %d.n", p->val);

    DeleteList(&L);

But it is better to immediately define all these operations in a special class, such as List:

class List

{

private:

    ListNode  *head;

public:   

    List() : head(NULL){}

    ~List() { Clear(); }

    void AddToTail(int value);

    void Clear();      

};



void List::AddToTail(int value)

{

    ListNode* nlist = new ListNode(value);

    if(head == NULL)

    {

        head = nlist;

    }

    else

    {

        ListNode* p = head;

        while(p->next != NULL)

        {

            p = p->next;

        }

        p->next = nlist;

    }

}





void List::Clear()

{

    ListNode* p = head;

    while(p != NULL)

    {

        ListNode *t = p->next;

        delete p;

        p = t;

    }

    head = NULL;

}

and use it like this:

List lst;

lst.AddToTail(5);

lst.AddToTail(10);

lst.AddToTail(20);

lst.AddToTail(30);

lst.Clear();