title: Valgrind reporting memory leaks in many places that change between runs
body: <p>I am creating a linked list but I keep getting memory leaks. Sometimes it says the problem is in the at() function and sometimes in the remove() function, but it all looks pretty tight to me. What is causing memory leaks?</p>
  
  <p>Here is my code for the linked list:</p>
  
  <pre><code>void LinkedList::insertHead(int value)
  {
      if (value &lt; 0) {
          return;
      }
      iterator pos(this, head);
      for (int i = 0; i &lt; num_items; i++) {
          if (pos.current-&gt;data == value)
              return;
          else
              pos++;
      }
      head = new Node(value, NULL, head);
      if (head-&gt;next != NULL)
          head-&gt;next-&gt;prev = head;
      if (tail == NULL)
          tail = head;
      num_items++;
  }
  
  void LinkedList::insertTail(int value)
  {
      if (value &lt; 0) {
          return;
      }
      iterator pos(this, head);
      for (int i = 0; i &lt; num_items; i++) {
          if (pos.current-&gt;data == value)
              return;
          else
              pos++;
      }
      if (tail != NULL) {
          tail-&gt;next = new Node(value, tail, NULL);
          tail = tail-&gt;next;
          num_items++;
      } else
          insertHead(value);
  }
  
  void LinkedList::insertAfter(int value, int insertionNode)
  {
      if (value &lt; 0) {
          return;
      }
      iterator pos(this, head);
      for (int i = 0; i &lt; num_items; i++) {
          if (pos.current-&gt;data == value)
              return;
          else
              pos++;
      }
      pos = iterator(this, head);
      for (int i = 0; i &lt; num_items; i++) {
          if (pos.current-&gt;data == insertionNode)
              break;
          else
              pos++;
      }
      if (pos.current == NULL || pos.current-&gt;data != insertionNode) {
          return;
      } /*else if(pos.current==NULL)
          insertTail(value);*/
      else {
          Node *new_node = new Node(value, pos.current, pos.current-&gt;next);
          if (pos.current-&gt;next != NULL)
              pos.current-&gt;next-&gt;prev = new_node;
          pos.current-&gt;next = new_node;
          num_items++;
      }
  
  }
  
  void LinkedList::remove(int value)
  {
      if (value &lt; 0) {
          return;
      }
      iterator pos(this, head);
      for (int i = 0; i &lt; num_items; i++) {
          if (pos.current-&gt;data == value)
              break;
          else
              pos++;
      }
      if (pos.current-&gt;data != value) {
          return;
      }
      if (pos.current == head) {
          Node *removed_node = head;
          head = head-&gt;next;
          delete removed_node;
          if (head != NULL)
              head-&gt;prev = NULL;
          else
              tail = NULL;
          num_items--;
      } else if (pos.current == tail) {
          Node *removed_node = tail;
          tail = tail-&gt;prev;
          delete removed_node;
          if (tail != NULL)
              tail-&gt;next = NULL;
          else
              head = NULL;
          num_items--;
      } else {
          Node *removed_node = pos.current;
          removed_node-&gt;prev-&gt;next = removed_node-&gt;next;
          removed_node-&gt;next-&gt;prev = removed_node-&gt;prev;
          delete removed_node;
          num_items--;
      }
  }
  
  void LinkedList::clear()
  {
      if (num_items == 0)
          return;
      if (head != NULL)
          remove(head-&gt;data);
      num_items = 0;
  }
  
  int LinkedList::at(int index)
  {
      if (index &lt; 0 || index &gt;= num_items)
          return -1;
      iterator pos(this, head);
      for (int i = 0; i &lt; index; i++)
          pos++;
      return pos.current-&gt;data;
  }
  
  int LinkedList::size()
  {
      return num_items;
  }
  </code></pre>
  
  <p>Here is code for the iterator:</p>
  
  <pre><code>class iterator {
      friend class LinkedList;
  private:
      LinkedList * parent;
      Node *current;
      iterator(LinkedList * my_parent, Node * position):parent(my_parent),
          current(position) {
      }
  public:
      int &amp;operator*() const {
          if (current == NULL)
              throw "Attempt to dereference end()";
          return current-&gt;data;
      }
  
      int *operator-&gt;() const {
          if (current == NULL)
              throw "attempt to dereference end()";
          return &amp;(current-&gt;data);
      }
  
      iterator &amp; operator++() {
          if (current == NULL)
              throw "Attempt to advance past end()";
          current = current-&gt;next;
          return *this;
      }
  
      iterator &amp; operator--() {
          if (current == parent-&gt;head)
              throw "Attempt to move before begin()";
          if (current == NULL)
              current = parent-&gt;tail;
          else
              current = current-&gt;prev;
          return *this;
      }
  
      iterator operator++(int) {
          iterator return_value = *this;
          ++(*this);
          return return_value;
      }
  
      iterator operator--(int) {
          iterator return_value = *this;
          --(*this);
          return return_value;
      }
  
      bool operator==(const iterator &amp; other) {
          return current == other.current;
      }
  
      bool operator!=(const iterator &amp; other) {
          return !operator==(other);
      }
  };
  </code></pre>
  
  <p>output as requested:</p>
  
  <pre><code>==18072== Invalid read of size 4
  ==18072==    at 0x402556: LinkedList::remove(int) (LinkedList.cpp:115)
  ==18072==    by 0x405946: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
  ==18072== 
  segmentation fault
  This segmentation fault was most likely caused by insertHead(), insertTail(), insertAfter(), or remove()
  ==18072== 
  ==18072== HEAP SUMMARY:
  ==18072==     in use at exit: 4,074 bytes in 118 blocks
  ==18072==   total heap usage: 981 allocs, 863 frees, 158,945 bytes allocated
  ==18072== 
  ==18072== 16 bytes in 1 blocks are still reachable in loss record 1 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x405888: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 32 bytes in 1 blocks are still reachable in loss record 2 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4020B2: Factory::getLinkedList() (Factory.cpp:21)
  ==18072==    by 0x40587B: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 32 bytes in 2 blocks are still reachable in loss record 3 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x407AC5: TADuck::insertHead(int) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x405D91: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 48 bytes in 2 blocks are still reachable in loss record 4 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
  ==18072==    by 0x405D84: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 48 bytes in 2 blocks are indirectly lost in loss record 5 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x40247A: LinkedList::insertAfter(int, int) (LinkedList.cpp:88)
  ==18072==    by 0x405137: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 192 bytes in 8 blocks are indirectly lost in loss record 6 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x402308: LinkedList::insertTail(int) (LinkedList.cpp:47)
  ==18072==    by 0x404D9F: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 216 bytes in 9 blocks are indirectly lost in loss record 7 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
  ==18072==    by 0x404341: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 216 bytes in 9 blocks are indirectly lost in loss record 8 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
  ==18072==    by 0x404BAD: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 240 bytes in 10 blocks are indirectly lost in loss record 9 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x402308: LinkedList::insertTail(int) (LinkedList.cpp:47)
  ==18072==    by 0x4046B1: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 240 bytes in 10 blocks are indirectly lost in loss record 10 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x40247A: LinkedList::insertAfter(int, int) (LinkedList.cpp:88)
  ==18072==    by 0x404897: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 256 bytes in 1 blocks are still reachable in loss record 11 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4074AD: std::vector&lt;int, std::allocator&lt;int&gt; &gt;::_M_insert_aux(__gnu_cxx::__normal_iterator&lt;int*, std::vector&lt;int, std::allocator&lt;int&gt; &gt; &gt;, int const&amp;) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x402B7C: fillMasterList(std::vector&lt;int, std::allocator&lt;int&gt; &gt;&amp;, int) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x404B82: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 432 bytes in 18 blocks are indirectly lost in loss record 12 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
  ==18072==    by 0x402BFD: initList(LinkedListInterface*, LinkedListInterface*) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x403F78: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 456 bytes in 19 blocks are indirectly lost in loss record 13 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
  ==18072==    by 0x4039E9: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 480 bytes in 20 blocks are indirectly lost in loss record 14 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
  ==18072==    by 0x402BFD: initList(LinkedListInterface*, LinkedListInterface*) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x4040DF: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 480 (24 direct, 456 indirect) bytes in 1 blocks are definitely lost in loss record 15 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
  ==18072==    by 0x4039E9: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 480 (24 direct, 456 indirect) bytes in 1 blocks are definitely lost in loss record 16 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
  ==18072==    by 0x402374: LinkedList::insertTail(int) (LinkedList.cpp:52)
  ==18072==    by 0x404D9F: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 537 bytes in 1 blocks are possibly lost in loss record 17 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x38C88B9F48: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator&lt;char&gt; const&amp;) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x38C88BAB1A: std::string::_Rep::_M_clone(std::allocator&lt;char&gt; const&amp;, unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x38C88BABB3: std::string::reserve(unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x38C8898F75: std::basic_stringbuf&lt;char, std::char_traits&lt;char&gt;, std::allocator&lt;char&gt; &gt;::overflow(int) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x38C889D195: std::basic_streambuf&lt;char, std::char_traits&lt;char&gt; &gt;::xsputn(char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x38C88949A4: std::basic_ostream&lt;char, std::char_traits&lt;char&gt; &gt;&amp; std::__ostream_insert&lt;char, std::char_traits&lt;char&gt; &gt;(std::basic_ostream&lt;char, std::char_traits&lt;char&gt; &gt;&amp;, char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x4036B6: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 537 bytes in 1 blocks are possibly lost in loss record 18 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x38C88B9F48: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator&lt;char&gt; const&amp;) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x38C88BAB1A: std::string::_Rep::_M_clone(std::allocator&lt;char&gt; const&amp;, unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x38C88BABB3: std::string::reserve(unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x38C8898F75: std::basic_stringbuf&lt;char, std::char_traits&lt;char&gt;, std::allocator&lt;char&gt; &gt;::overflow(int) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x38C889D195: std::basic_streambuf&lt;char, std::char_traits&lt;char&gt; &gt;::xsputn(char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x38C88949A4: std::basic_ostream&lt;char, std::char_traits&lt;char&gt; &gt;&amp; std::__ostream_insert&lt;char, std::char_traits&lt;char&gt; &gt;(std::basic_ostream&lt;char, std::char_traits&lt;char&gt; &gt;&amp;, char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
  ==18072==    by 0x403A7C: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 720 (24 direct, 696 indirect) bytes in 1 blocks are definitely lost in loss record 19 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
  ==18072==    by 0x404341: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== 936 (24 direct, 912 indirect) bytes in 1 blocks are definitely lost in loss record 20 of 20
  ==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
  ==18072==    by 0x402BFD: initList(LinkedListInterface*, LinkedListInterface*) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x403F78: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
  ==18072== 
  ==18072== LEAK SUMMARY:
  ==18072==    definitely lost: 96 bytes in 4 blocks
  ==18072==    indirectly lost: 2,520 bytes in 105 blocks
  ==18072==      possibly lost: 1,074 bytes in 2 blocks
  ==18072==    still reachable: 384 bytes in 7 blocks
  ==18072==         suppressed: 0 bytes in 0 blocks
  ==18072== 
  ==18072== For counts of detected and suppressed errors, rerun with: -v
  ==18072== ERROR SUMMARY: 7 errors from 7 contexts (suppressed: 2 from 2)
  </code></pre>