CODEWITHSUNDEEP
c++pointersmemory-leakslinked-list
Mark
Mark

Reputation: 283

C++ Memory leaks form inserting data into linked list

I'm required to use either unique_ptr or shared_ptr for my linked list, but I am still getting memory leaks. Just for this case, I'm leaving all the member data as public. Inserting the first time into the linked list does not cause any memory leaks, but as the for loop continues, each time I insert an object as the data into the linked list, the debugger shows more memory leaks. I don't know what could be causing so many memory leaks. Could it be caused by some of the shared ptrs?

    template <typename T>
    class Node
    {
    public:
       T data;
       shared_ptr<Node<T>> next;
       shared_ptr<Node<T>> prev;

    public:
       Node() { next = NULL; prev = NULL; data = 0; }
       Node(T value) { next = NULL; prev = NULL; data = value; }
       T getData() { return data; }

    };

  template <typename T>
  class DoubleLinkedList
  {
  public:
      shared_ptr<Node<T>> head;
      shared_ptr<Node<T>> tail;
  public:
      DoubleLinkedList()
     {
         head = NULL;
         tail = NULL;
         total = 100;
         for (int i = 0; i < total; i++)
         {
            Insert(objectgetsinsertedhere);
         }
     }


void Insert(T data)
{
    shared_ptr<Node<T>> rover = NULL;
    T value(data);
    if (head == NULL)
    {
        head = make_shared<Node<T>>(data);
        tail = head;
    }
    else
    {
        shared_ptr<Node<T>> nu = make_shared<Node<T>>(data);
        nu->prev = tail;
        if (head == tail)
            head->next = nu;
        tail->next = nu;
        tail = nu;
    }
}
};

EDIT: This is a portion of what the debugger shows as memory leaks.

Detected memory leaks!
Dumping objects ->
{211} normal block at 0x005CF798, 8 bytes long.
Data: <x \     > 78 98 5C 00 00 00 00 00 
{210} normal block at 0x005CF258, 8 bytes long.
Data: <\ \     > 5C 98 5C 00 00 00 00 00 
{209} normal block at 0x005CF1B0, 8 bytes long.
Data: <@ \     > 40 98 5C 00 00 00 00 00 
{205} normal block at 0x005C9830, 136 bytes long.
Data: <H               > 48 A9 0C 00 01 00 00 00 01 00 00 00 CD CD CD CD 
{191} normal block at 0x005CF3A8, 8 bytes long.
Data: <  \     > A8 DB 5C 00 00 00 00 00 
{190} normal block at 0x005CF0D0, 8 bytes long.
Data: <  \     > 8C DB 5C 00 00 00 00 00 
{189} normal block at 0x005CF060, 8 bytes long.
Data: <p \     > 70 DB 5C 00 00 00 00 00 
{185} normal block at 0x005CDB60, 136 bytes long.
Data: <H               > 48 A9 0C 00 01 00 00 00 01 00 00 00 CD CD CD CD 
Object dump complete.

Upvotes: 2

Views: 369

Answers (1)

Vaughn Cato
Vaughn Cato

Reputation: 64308

The issue is that you have an ownership cycle in your shared pointers. This makes it where the memory does not get freed automatically because there is always at least one owner, even after the linked list itself has been destroyed. One way to address this is to only use a shared pointer for the next pointer, but not the prev pointer:

template <typename T>
class Node
{ 
  public:
    T data;
    shared_ptr<Node<T>> next;
    Node<T> *prev;

  public:
    Node() { next = NULL; prev = NULL; data = 0; } 
    Node(T value) { next = NULL; prev = NULL; data = value; }
    T getData() { return data; }

};

This prevents the ownership cycle. The list owns the head, the head owns the second element, etc. When the list is destroyed, then there are no owners for the head, so the head gets destroyed, and now there are no owners for the second element, so it gets destroyed, etc.

Upvotes: 2

Related Questions