{"id":898,"date":"2013-01-04T19:09:21","date_gmt":"2013-01-04T18:09:21","guid":{"rendered":"http:\/\/denbeke.be\/blog\/?page_id=898"},"modified":"2013-01-04T19:16:49","modified_gmt":"2013-01-04T18:16:49","slug":"linked-list-memory-leak","status":"publish","type":"page","link":"https:\/\/denbeke.be\/blog\/linked-list-memory-leak\/","title":{"rendered":"Linked List (memory leak)"},"content":{"rendered":"<p><strong>C++ File<\/strong><\/p>\n<pre><code data-language=\"c\">\/*\r\nLinked List\r\n\r\nCreated: dec 22, 2012\r\nAuthor: Mathias Beke - http:\/\/denbeke.be\r\n*\/\r\n\r\n#include &lt;iostream&gt;\r\n#include \"LinkedList.h\"\r\n\r\n\/*******\r\n* Node *\r\n*******\/\r\n\r\nNode::Node() {\r\n\t\/\/Constructor\r\n\tnumber = 0;\r\n\tnext = NULL;\r\n}\r\n\r\nNode::Node(int value, Node* next_node) {\r\n\t\/\/Constructor with values\r\n\tnumber = value;\r\n\tnext = next_node;\r\n}\r\n\r\n\/**************\r\n* Linked List *\r\n**************\/\r\n\r\nLinkedList::LinkedList() {\r\n\t\/\/Constructor\r\n\thead = NULL;\r\n\tlength = 0;\r\n}\r\n\r\nvoid LinkedList::insert(int value, int index) {\r\n\t\/\/Insert element with given 'value' on position 'index'.\r\n\t\/\/The first element has index 1.\r\n\tif(index &gt; getLength()+1 || index &lt; 1) {\r\n\t\t\/\/ERROR: index out of range\r\n\t\treturn;\r\n\t}\r\n\telse if (getLength() == 0) {\r\n\t\t\/\/Insert item on first position in empty list\r\n\t\tNode *newNode;\r\n\t\tnewNode = new Node;\r\n\t\tnewNode-&gt;number = value;\r\n\t\tnewNode-&gt;next = NULL;\r\n\t\thead = newNode;\r\n\t}\r\n\telse {\r\n\t\t\/\/List not empty\r\n\r\n\t\tif (index == 1) {\r\n\t\t\t\/\/Insert item on first position of 'normal' list\r\n\t\t\tNode *newNode;\r\n\t\t\tnewNode = new Node;\r\n\t\t\tnewNode-&gt;number = value;\r\n\t\t\tnewNode-&gt;next = head;\r\n\t\t\thead = newNode;\r\n\t\t}\r\n\t\telse if (index == length+1){\r\n\t\t\t\/\/Insert item on last position\r\n\t\t\tNode *cur = head;\r\n\r\n\t\t\tfor (int i = 1; i &lt; index-1; i++) {\r\n\t\t\t\tcur = cur-&gt;next;\r\n\t\t\t}\r\n\r\n\t\t\tNode *newNode;\r\n\t\t\tnewNode = new Node;\r\n\t\t\tnewNode-&gt;number = value;\r\n\t\t\tnewNode-&gt;next = NULL;\r\n\t\t\tcur-&gt;next = newNode;\r\n\t\t}\r\n\t\telse {\r\n\t\t\t\/\/Insert item on regular position\r\n\t\t\tNode *prev = head;\r\n\t\t\tNode *cur;\r\n\r\n\t\t\tfor (int i = 1; i &lt; index-1; i++) {\r\n\t\t\t\t\/\/Move the 'previous' pointer 'index-2' steps forward\r\n\t\t\t\tprev = prev-&gt;next;\r\n\t\t\t}\r\n\r\n\t\t\tcur = prev-&gt;next; \/\/Go 1 step forward\r\n\r\n\t\t\tNode *newNode;\r\n\t\t\tnewNode = new Node;\r\n\t\t\tnewNode-&gt;number = value;\r\n\t\t\tnewNode-&gt;next = cur;\r\n\t\t\tprev-&gt;next = newNode;\r\n\r\n\t\t}\r\n\t}\r\n\r\n\tlength++; \/\/Increment length of list\r\n}\r\n\r\nvoid LinkedList::remove(int index) {\r\n\t\/\/Remove item from Linked List\r\n\tif (getLength() == 0) {\r\n\t\t\/\/ERROR: can't remove item from empty list\r\n\t\treturn;\r\n\t}\r\n\telse if(index &gt; getLength() || index &lt; 1) {\r\n\t\t\/\/ERROR: index out of range\r\n\t\treturn;\r\n\t}\r\n\telse {\r\n\t\t\/\/List not empty\r\n\r\n\t\tif (index == 1) {\r\n\t\t\t\/\/Remove first item from list\r\n\t\t\tif (getLength() == 1) {\r\n\t\t\t\t\/\/Remove first and last item from list\r\n\t\t\t\tdelete head;\r\n\t\t\t\thead = NULL;\t\r\n\t\t\t}\r\n\t\t\telse {\r\n\t\t\t\t\/\/Remove first item where length &gt; 0\r\n\t\t\t\tNode* cur;\r\n\t\t\t\tcur = head;\r\n\t\t\t\thead = head-&gt;next;\r\n\t\t\t\tdelete cur;\t\t\r\n\t\t\t}\r\n\t\t}\r\n\t\telse if (index == length){\r\n\t\t\t\/\/Remove item from last position\r\n\t\t\tNode *cur = head-&gt;next;\r\n\t\t\tNode *prev = head;\r\n\t\t\twhile ( cur-&gt;next != NULL ) {\r\n\t\t\t\tcur = cur-&gt;next;\r\n\t\t\t\tprev = prev-&gt;next;\r\n\t\t\t}\r\n\r\n\t\t\tprev-&gt;next = NULL;\r\n\t\t\tdelete cur;\r\n\t\t}\r\n\t\telse {\r\n\t\t\t\/\/Remove item from regular position\r\n\t\t\tNode *cur = head-&gt;next;\r\n\t\t\tNode *prev = head;\r\n\t\t\tfor (int i = 1; i &lt; index-1; i++) {\r\n\t\t\t\t\/\/Move the 'previous' and 'cur' pointer 'index-2' steps forward\r\n\t\t\t\tcur = cur-&gt;next;\r\n\t\t\t\tprev = prev-&gt;next;\r\n\t\t\t}\r\n\t\t\tprev-&gt;next = cur-&gt;next;\r\n\t\t\tdelete cur;\r\n\t\t}\r\n\t}\r\n\r\n\tlength--; \/\/Decrement length of list\r\n\r\n}\r\n\r\nint LinkedList::getLength() {\r\n\t\/\/Get Length of Linked List\r\n\treturn length;\r\n}\r\n\r\nbool LinkedList::isEmpty() {\r\n\t\/\/Check if Linked List is empty\r\n\treturn getLength() == 0;\r\n}\r\n\r\nint LinkedList::retrieve(int index) {\r\n\t\/\/Retrieve value on position 'index'\r\n\tNode *cur = head;\r\n\tfor (int i = 1; i &lt; index; i++) {\r\n\t\t\/\/Move index-1 steps forward\r\n\t\tcur = cur-&gt;next;\r\n\t}\r\n\treturn cur-&gt;number;\r\n}\r\n\r\nvoid LinkedList::print() {\r\n\t\/\/Print Linked List\r\n\tint counter = 1;\r\n\r\n\tfor (int i = 1; i &lt; getLength()+1; i++) {\r\n\t\tstd::cout &lt;&lt; counter &lt;&lt; \". \" &lt;&lt; retrieve(i) &lt;&lt; std::endl;\r\n\t\tcounter++;\r\n\t}\r\n}\r\n\r\nLinkedList::~LinkedList() {\r\n\t\/\/Destructor\r\n\twhile ( !isEmpty() ) {\r\n\t\tremove(1);\r\n\t}\r\n\r\n\tstd::cout &lt;&lt; \"Destruction List\" &lt;&lt; std::endl;\r\n\tprint(); \r\n}\r\n\r\nint main() {\r\n\r\n\t\/****************************\r\n\t* Test Data for Linked List *\r\n\t****************************\/\r\n\r\n\tstd::cout &lt;&lt; \"Testing Linked List\" &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; \"___________________\" &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; std::endl;\r\n\r\n\tLinkedList list;\r\n\r\n\tstd::cout &lt;&lt; \"Linked List Empty? \" &lt;&lt; list.isEmpty() &lt;&lt; std::endl;\r\n\r\n\tlist.insert(11,1);\r\n\tlist.insert(19,1);\r\n\tlist.insert(3,3);\r\n\tlist.insert(5,4);\r\n\tlist.insert(9,5);\r\n\tlist.insert(21,6);\r\n\tlist.insert(15,7);\r\n\tlist.insert(50,8);\r\n\r\n\tstd::cout &lt;&lt; std::endl;\r\n\r\n\tstd::cout &lt;&lt; \"insert(11,1)\" &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; \"insert(19,1)\" &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; \"insert(3,3)\" &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; \"insert(5,4)\" &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; \"insert(9,5)\" &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; \"insert(21,6)\" &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; \"insert(15,7)\" &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; \"insert(50,8)\" &lt;&lt; std::endl;\r\n\r\n\tstd::cout &lt;&lt; std::endl;\r\n\r\n\tstd::cout &lt;&lt; \"Item on first position: \" &lt;&lt; list.retrieve(1) &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; \"Item on second position: \" &lt;&lt; list.retrieve(2) &lt;&lt; std::endl;\r\n\r\n\tstd::cout &lt;&lt; \"Length: \" &lt;&lt; list.getLength() &lt;&lt; std::endl;\r\n\tstd::cout &lt;&lt; \"Linked List Empty? \" &lt;&lt; list.isEmpty() &lt;&lt; std::endl;\r\n\r\n\tstd::cout &lt;&lt; std::endl &lt;&lt; \"Current Linked List\" &lt;&lt; std::endl;\r\n\r\n\tlist.print();\r\n\r\n\tstd::cout &lt;&lt; std::endl &lt;&lt; \"Remove(1) \" &lt;&lt; std::endl;\r\n\tlist.remove(1);\r\n\r\n\tlist.print();\r\n\r\n\tstd::cout &lt;&lt; std::endl &lt;&lt; \"Remove(3) \" &lt;&lt; std::endl;\r\n\tlist.remove(3);\r\n\r\n\tlist.print();\r\n\r\n\tstd::cout &lt;&lt; std::endl &lt;&lt; \"Remove(2) \" &lt;&lt; std::endl;\r\n\tlist.remove(2);\r\n\r\n\tlist.print();\r\n\r\n\tstd::cout &lt;&lt; std::endl &lt;&lt; \"Remove(5) \" &lt;&lt; std::endl;\r\n\tlist.remove(4);\r\n\r\n\tlist.print();\r\n}<\/code><\/pre>\n<p><strong>Header file<\/strong><\/p>\n<pre><code data-language=\"c\">\/*\r\nLinked List\r\n\r\nCreated: dec 22, 2012\r\nAuthor: Mathias Beke - http:\/\/denbeke.be\r\n*\/\r\n\r\nclass Node {\r\n\t\/\/Class Node\r\npublic:\r\n\tint number;\r\n\tNode* next;\r\n\t\r\n\tNode();\r\n\tNode(int, Node*);\t\r\n};\r\n\r\nclass LinkedList {\r\n\t\/\/Class Linked List\r\n\tNode* head;\r\n\tint length;\r\n\t\r\npublic:\r\n\tLinkedList();\r\n\t\r\n\tvoid insert(int, int);\r\n\t\r\n\tvoid remove(int);\r\n\r\n\tint retrieve(int);\r\n\r\n\tvoid print();\r\n\t\r\n\tint getLength();\r\n\t\r\n\tbool isEmpty();\r\n\t\r\n\t~LinkedList();\r\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>C++ File \/* Linked List Created: dec 22, 2012 Author: Mathias Beke &#8211; http:\/\/denbeke.be *\/ #include &lt;iostream&gt; #include &#8220;LinkedList.h&#8221; \/******* * Node * *******\/ Node::Node() { \/\/Constructor number = 0; next = NULL; } Node::Node(int value, Node* next_node) { \/\/Constructor with values number = value; next = next_node; } \/************** * Linked List * **************\/ [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v15.6.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Linked List (memory leak) &ndash; DenBeke<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/denbeke.be\/blog\/linked-list-memory-leak\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Linked List (memory leak) &ndash; DenBeke\" \/>\n<meta property=\"og:description\" content=\"C++ File \/* Linked List Created: dec 22, 2012 Author: Mathias Beke - http:\/\/denbeke.be *\/ #include &lt;iostream&gt; #include &quot;LinkedList.h&quot; \/******* * Node * *******\/ Node::Node() { \/\/Constructor number = 0; next = NULL; } Node::Node(int value, Node* next_node) { \/\/Constructor with values number = value; next = next_node; } \/************** * Linked List * **************\/ [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/denbeke.be\/blog\/linked-list-memory-leak\/\" \/>\n<meta property=\"og:site_name\" content=\"DenBeke\" \/>\n<meta property=\"article:modified_time\" content=\"2013-01-04T18:16:49+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary\" \/>\n<meta name=\"twitter:site\" content=\"@MthsBk\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\">\n\t<meta name=\"twitter:data1\" content=\"4 minutes\">\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebSite\",\"@id\":\"https:\/\/denbeke.be\/blog\/#website\",\"url\":\"https:\/\/denbeke.be\/blog\/\",\"name\":\"DenBeke\",\"description\":\"Mathias Beke\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":\"https:\/\/denbeke.be\/blog\/?s={search_term_string}\",\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/denbeke.be\/blog\/linked-list-memory-leak\/#webpage\",\"url\":\"https:\/\/denbeke.be\/blog\/linked-list-memory-leak\/\",\"name\":\"Linked List (memory leak) &ndash; DenBeke\",\"isPartOf\":{\"@id\":\"https:\/\/denbeke.be\/blog\/#website\"},\"datePublished\":\"2013-01-04T18:09:21+00:00\",\"dateModified\":\"2013-01-04T18:16:49+00:00\",\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/denbeke.be\/blog\/linked-list-memory-leak\/\"]}]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","_links":{"self":[{"href":"https:\/\/denbeke.be\/blog\/wp-json\/wp\/v2\/pages\/898"}],"collection":[{"href":"https:\/\/denbeke.be\/blog\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/denbeke.be\/blog\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/denbeke.be\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/denbeke.be\/blog\/wp-json\/wp\/v2\/comments?post=898"}],"version-history":[{"count":4,"href":"https:\/\/denbeke.be\/blog\/wp-json\/wp\/v2\/pages\/898\/revisions"}],"predecessor-version":[{"id":904,"href":"https:\/\/denbeke.be\/blog\/wp-json\/wp\/v2\/pages\/898\/revisions\/904"}],"wp:attachment":[{"href":"https:\/\/denbeke.be\/blog\/wp-json\/wp\/v2\/media?parent=898"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}