{"id":8463,"date":"2023-04-16T15:58:50","date_gmt":"2023-04-16T13:58:50","guid":{"rendered":"https:\/\/blue.pri.ee\/ttu\/?p=8463"},"modified":"2026-01-29T11:38:32","modified_gmt":"2026-01-29T09:38:32","slug":"pr2en12-linked-list","status":"publish","type":"post","link":"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/","title":{"rendered":"PR2EN12: Linked list"},"content":{"rendered":"<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Lab_materials\" >Lab materials<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Lab_tasks\" >Lab tasks<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Lab_task_W12-1_Linked_list\" >Lab task [W12-1]: Linked list<\/a><ul class='ez-toc-list-level-5' ><li class='ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Requirements\" >Requirements<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Step-by-step_guide\" >Step-by-step guide<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Testing\" >Testing<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Extra_task_1_W12-2_Alphabetically_ordered_list\" >Extra task 1 [W12-2]: Alphabetically ordered list<\/a><ul class='ez-toc-list-level-5' ><li class='ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Requirements-2\" >Requirements<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Notes\" >Notes<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Extra_task_2_W12-3_Removal_of_nodes\" >Extra task 2 [W12-3]: Removal of nodes<\/a><ul class='ez-toc-list-level-5' ><li class='ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Requirements-3\" >Requirements<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-5'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Notes-2\" >Notes<\/a><\/li><\/ul><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#After_this_class_you_should\" >After this class, you should<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/#Additional_materials\" >Additional materials<\/a><\/li><\/ul><\/nav><\/div>\n<h3><span class=\"ez-toc-section\" id=\"Lab_materials\"><\/span>Lab materials<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Slides: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/slaidid-en\/2025\/12_Linked_List.pdf\"><strong>Linked\u00a0list<\/strong><\/a><\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Lab_tasks\"><\/span>Lab tasks<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>In this lab, there is one base task and two estra tasks that build upon the base task.<\/p>\n<h4><span class=\"ez-toc-section\" id=\"Lab_task_W12-1_Linked_list\"><\/span><span style=\"font-size: 20px; font-weight: bold;\">Lab task [W12-1]: Linked list<\/span><span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>In the base task, we are going to implement a linked list.<\/p>\n<p><strong>Download the starter code: <a href=\"https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/aluskoodid\/12_ll_basecode.zip\">https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/aluskoodid\/12_ll_basecode.zip<\/a><\/strong><\/p>\n<h5><span class=\"ez-toc-section\" id=\"Requirements\"><\/span>Requirements<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>Create a menu program that allows for manipulation of a singly linked list<\/li>\n<li>New nodes must be added to the beginning of the list only.<\/li>\n<li>A node contains a number (id) and a string (name).\n<ul>\n<li>id is auto-generated, unique, sequential integer starting from 0<\/li>\n<li>Name is a string entered by the user during creation of the node.<\/li>\n<li>Name is allocated dynamically, dependent on the length of the entered name.<\/li>\n<\/ul>\n<\/li>\n<li>Implement the <span class=\"lang:c highlight:0 decode:true crayon-inline\">PrintNode()<\/span> , <span class=\"lang:c highlight:0 decode:true crayon-inline \">CreateNode()<\/span> , <span class=\"lang:c highlight:0 decode:true crayon-inline \">InsertNode()<\/span> , <span class=\"lang:c highlight:0 decode:true crayon-inline \">FindNodeByID()<\/span> , <span class=\"lang:c highlight:0 decode:true crayon-inline \">FindNodeByName()<\/span>\u00a0 and <span class=\"lang:c highlight:0 decode:true crayon-inline \">Unload()<\/span>\u00a0 functions based on their description<\/li>\n<li>Use the starter code provided as your base<\/li>\n<li>Work through the task base on the step-by-step guide. Implement the functions as specified in the guide.<\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Step-by-step_guide\"><\/span>Step-by-step guide<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>NB! Notice that the structure declaration creates 2 valid data types &#8211; <span class=\"lang:c highlight:0 decode:true crayon-inline\">struct Node<\/span>\u00a0 and <span class=\"lang:c highlight:0 decode:true crayon-inline\">List<\/span> . While both are\u00a0 the same thing by definition (they are aliases from typedef), one is used in the context for referring to a single member and the other is referring to the entire list.<\/p>\n<hr \/>\n<pre class=\"toolbar:2 nums:false lang:c decode:true\">void PrintNode(List *pNode);<\/pre>\n<p>We will start by creating a function that prints out the contents of a single node. Add this function to the code file (prototype already exists in the header).\u00a0 It needs to print all members of the node.<\/p>\n<p><span class=\"lang:c highlight:0 decode:true crayon-inline\">PrintNode()<\/span>\u00a0 function should be used whenever you need to print the contents of a node. This includes Find family of functions that you will create later.\u00a0 This way, whenever the contents of the node changes, the modifications for printing only need to be made once in a single place.<\/p>\n<p>Don&#8217;t forget to check for NULL pointer to avoid crashing if the calling function decides to pass a NULL pointer.<\/p>\n<p><strong>Uncomment testing stage 1 and run your code!<\/strong><\/p>\n<p>NB! The testing strings are in UTF-8, which is fine for our Linux machines, however they could disagree with some Windows environments. Alter the strings if necessary.<\/p>\n<div class=\"su-spoiler su-spoiler-style-fancy su-spoiler-icon-chevron su-spoiler-closed\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-spoiler-title\" tabindex=\"0\" role=\"button\"><span class=\"su-spoiler-icon\"><\/span>Click me to see the expected output<\/div><div class=\"su-spoiler-content su-u-clearfix su-u-trim\">\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/ttu\/prog2\/wk11_linked_list$ .\/ll_basecode\r\nID: 2\r\nName: Maamees Jaanes\r\npNext: (nil)\r\n\r\nError! Node not found!\r\n<\/pre>\n<\/div><\/div>\n<hr \/>\n<p><em>NB! This function is already completed for you. <strong>Pay attention to how the loop is built. You need it for traversal in the later functions.<\/strong><\/em><\/p>\n<pre class=\"toolbar:2 nums:false lang:c decode:true\">void PrintList(List *pHead);<\/pre>\n<p>This function is used to print the entire linked list.\u00a0 It gets passed the pointer to the beginning of the list and it will traverse the list until it reaches the end of the list, indicated by a <span class=\"lang:c highlight:0 decode:true crayon-inline \">NULL<\/span>\u00a0 pointer..<\/p>\n<p>The function also handles a <span class=\"lang:c highlight:0 decode:true crayon-inline \">NULL<\/span>\u00a0 pointer passed to it instead of a valid pointer to the beginning of the list &#8211; this will happen when the linked list is empty!<\/p>\n<p>The function itself does not handle printing of the nodes, but rather calls\u00a0 <span class=\"lang:c highlight:0 decode:true crayon-inline\">PrintNode()<\/span>\u00a0 on every node to print its contents. This is why we completed that first.<\/p>\n<p><strong>Uncomment testing stage 2 and run your code!<\/strong><\/p>\n<div class=\"su-spoiler su-spoiler-style-fancy su-spoiler-icon-chevron su-spoiler-closed\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-spoiler-title\" tabindex=\"0\" role=\"button\"><span class=\"su-spoiler-icon\"><\/span>Click me to see the expected output<\/div><div class=\"su-spoiler-content su-u-clearfix su-u-trim\">\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/ttu\/prog2\/wk11_linked_list$ .\/ll_basecode\r\nID: 0\r\nName: Kivipallur J\u00fcrto Nii-Dommzonn\r\npNext: 0x7ffe9d745100\r\n\r\nID: 1\r\nName: Linnud T\u00f5nisted\r\npNext: 0x7ffe9d7450e0\r\n\r\nID: 2\r\nName: Maamees Jaanes\r\npNext: (nil)<\/pre>\n<\/div><\/div>\n<hr \/>\n<pre class=\"toolbar:2 nums:false lang:c decode:true\">struct Node *CreateNode(char *name);<\/pre>\n<p>This function is used to create a new node and initialize its values. It returns the newly created node. Values for the node are passed as parameters.<\/p>\n<ol>\n<li>Create and allocate the node<\/li>\n<li>Assign the ID value (sequentially incrementing value, use <span class=\"lang:c highlight:0 decode:true crayon-inline \">static<\/span>\u00a0)<\/li>\n<li>Allocate memory for the name and copy it over<\/li>\n<li>Initialize the <span class=\"lang:c highlight:0 decode:true crayon-inline \">pNext<\/span>\u00a0 pointer<\/li>\n<li>Return the struct pointer<\/li>\n<\/ol>\n<p>NB! There are two memory allocations in this function. Both need to be checked. If there&#8217;s an error, return a NULL pointer! Program should continue running.<\/p>\n<p><strong>Uncomment testing stage 2 <\/strong><strong>and run your code!\u00a0<\/strong>Only expected changes are different address space (going from stack to heap) and increased allocations when checking with valgrind.<\/p>\n<div class=\"su-spoiler su-spoiler-style-fancy su-spoiler-icon-chevron su-spoiler-closed\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-spoiler-title\" tabindex=\"0\" role=\"button\"><span class=\"su-spoiler-icon\"><\/span>Click me to see the expected output<\/div><div class=\"su-spoiler-content su-u-clearfix su-u-trim\">\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/ttu\/prog2\/wk11_linked_list$ .\/ll_basecode\r\nID: 0\r\nName: Kivipallur J\u00fcrto Nii-Dommzonn\r\npNext: 0x55b81e0f92f0\r\n\r\nID: 1\r\nName: Linnud T\u00f5nisted\r\npNext: 0x55b81e0f9330\r\n\r\nID: 2\r\nName: Maamees Jaanes\r\npNext: (nil)<\/pre>\n<\/div><\/div>\n<hr \/>\n<pre class=\"toolbar:2 nums:false lang:c decode:true\">void InsertNode(List **ppHead, struct Node *pNode);<\/pre>\n<p>This function adds the node <span class=\"lang:c highlight:0 decode:true crayon-inline \">pNode<\/span>\u00a0 to the list pointed by <span class=\"lang:c highlight:0 decode:true crayon-inline\">ppHead<\/span> . Double pointer is required to change the location of the beginning of the list.<\/p>\n<p>In the base version of the task, add the node to the beginning of the list (only 2 assignment statements!)<\/p>\n<p>NB! Before adding, check that <span class=\"lang:c highlight:0 decode:true crayon-inline\">pNode<\/span>\u00a0 isn&#8217;t a <span class=\"lang:c highlight:0 decode:true crayon-inline \">NULL<\/span>\u00a0 pointer!<\/p>\n<p><strong>Uncomment testing stage 3 and run your code!\u00a0\u00a0<\/strong>Visually you should not see any differences in the output.<\/p>\n<div class=\"su-spoiler su-spoiler-style-fancy su-spoiler-icon-chevron su-spoiler-closed\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-spoiler-title\" tabindex=\"0\" role=\"button\"><span class=\"su-spoiler-icon\"><\/span>Click me to see the expected output<\/div><div class=\"su-spoiler-content su-u-clearfix su-u-trim\">\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/ttu\/prog2\/wk11_linked_list$ .\/ll_basecode\r\nID: 0\r\nName: Kivipallur J\u00fcrto Nii-Dommzonn\r\npNext: 0x55b81e0f92f0\r\n\r\nID: 1\r\nName: Linnud T\u00f5nisted\r\npNext: 0x55b81e0f9330\r\n\r\nID: 2\r\nName: Maamees Jaanes\r\npNext: (nil)<\/pre>\n<\/div><\/div>\n<hr \/>\n<pre class=\"toolbar:2 nums:false lang:c decode:true\">void Unload(list *pHead);<\/pre>\n<p data-select-like-a-boss=\"1\">This function is what&#8217;s also called a destructor. It removes (deallocates) all nodes from them memory. This includes all the members that were allocated dynamically as well &#8211; in our case, the name.<\/p>\n<p data-select-like-a-boss=\"1\">To free a linked list, you need to loop through the entire list. To familiarize yourself with the traversal of the list, check the\u00a0\u00a0<span class=\"lang:c highlight:0 decode:true crayon-inline \">PrintList()<\/span>\u00a0 function.<\/p>\n<p data-select-like-a-boss=\"1\">When freeing the list, you should pay <strong>close attention<\/strong> to how you free the current node. After freeing the current node, we no longer have access to its\u00a0 <span class=\"lang:c highlight:0 decode:true crayon-inline\">pNext<\/span>\u00a0 pointer. Due to this, we need to create a temporary pointer that will have a copy of the current node&#8217;s address, which adds a little bit of complexity.<\/p>\n<p data-select-like-a-boss=\"1\">You have to complete 3 steps in the loop. The most elegant way of making it is by using a\u00a0 <span class=\"lang:c highlight:0 decode:true crayon-inline \">while()<\/span>\u00a0 loop.<\/p>\n<ol>\n<li data-select-like-a-boss=\"1\">Make a copy of the current node address (you will be freeing through this copy)<\/li>\n<li data-select-like-a-boss=\"1\">Move the main pointer to the next element (<span class=\"lang:c highlight:0 decode:true crayon-inline \">pCurrent = pCurrent-&gt;pNext<\/span>\u00a0)<\/li>\n<li data-select-like-a-boss=\"1\">Free the current node and its members.<\/li>\n<\/ol>\n<p><strong>Uncomment testing stage 4.\u00a0 Run through valgrind. <\/strong>You should see 6 allocations and 6 frees.<\/p>\n<div class=\"su-spoiler su-spoiler-style-fancy su-spoiler-icon-chevron su-spoiler-closed\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-spoiler-title\" tabindex=\"0\" role=\"button\"><span class=\"su-spoiler-icon\"><\/span>Click me to see the expected output<\/div><div class=\"su-spoiler-content su-u-clearfix su-u-trim\">\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/ttu\/prog2\/wk11_linked_list$ .\/ll_basecode\r\n==17208== Memcheck, a memory error detector\r\n==17208== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.\r\n==17208== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info\r\n==17208== Command: .\/ll_basecode\r\n==17208==\r\n==17208==\r\n==17208== HEAP SUMMARY:\r\n==17208==     in use at exit: 0 bytes in 0 blocks\r\n==17208==   total heap usage: 6 allocs, 6 frees, 135 bytes allocated\r\n==17208==\r\n==17208== All heap blocks were freed -- no leaks are possible\r\n==17208==\r\n==17208== For lists of detected and suppressed errors, rerun with: -s\r\n==17208== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)<\/pre>\n<\/div><\/div>\n<hr \/>\n<pre class=\"toolbar:2 nums:false lang:c decode:true\">struct Node *FindNodeByName(List *pHead, char *name);<\/pre>\n<pre class=\"toolbar:2 nums:false lang:c decode:true\">struct Node *FindNodeByID(List *pHead, int id);<\/pre>\n<p>In this part, we will create search functions to either search by ID or by name. The functions return the pointer to the node if a match is found or a NULL-pointer when the element was not found.<\/p>\n<p>Use <span class=\"lang:c highlight:0 decode:true crayon-inline \">PrintNode()<\/span>\u00a0 to output the result.<\/p>\n<p><strong>Uncomment testing stage 5 and check the output!\u00a0<\/strong>Note that the error message is provided by PrintNode() function and is not specific to the search!<\/p>\n<div class=\"su-spoiler su-spoiler-style-fancy su-spoiler-icon-chevron su-spoiler-closed\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-spoiler-title\" tabindex=\"0\" role=\"button\"><span class=\"su-spoiler-icon\"><\/span>Click me to see the expected output<\/div><div class=\"su-spoiler-content su-u-clearfix su-u-trim\">\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true\">risto@risto-tux:~\/Nextcloud\/ttu\/prog2\/wk11_linked_list$ .\/ll_basecode\r\nID: 1\r\nName: Linnud T\u00f5nisted\r\npNext: 0x5627e3069330\r\n\r\nError! Node not passed!\r\n\r\nID: 2\r\nName: Maamees Jaanes\r\npNext: (nil)\r\n\r\nError! Node not passed!<\/pre>\n<\/div><\/div>\n<hr \/>\n<p>Congratulations! All base functionality is now finished! Now create the additional functions, prompts etc so that the program could be used through the menu as a command line utility. You can delete the testing code from main.<\/p>\n<p>This means prompting the user for name when inserting a node or asking for search keywords, as well as checking the returns for functions as necessary. <strong>Once that is done, present the task.<\/strong><\/p>\n<h5><span class=\"ez-toc-section\" id=\"Testing\"><\/span>Testing<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<p>This is the final expected output of the base task<\/p>\n<div class=\"su-spoiler su-spoiler-style-fancy su-spoiler-icon-chevron su-spoiler-closed\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-spoiler-title\" tabindex=\"0\" role=\"button\"><span class=\"su-spoiler-icon\"><\/span>Click me to see the expected output<\/div><div class=\"su-spoiler-content su-u-clearfix su-u-trim\">\n<pre class=\"theme:cisco-router toolbar:2 nums:false lang:c highlight:0 decode:true \">risto@risto-tux:~\/Nextcloud\/ttu\/prog2\/wk11_linked_list$ .\/ll_basecode\r\nde\r\n==17678== Memcheck, a memory error detector\r\n==17678== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.\r\n==17678== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info\r\n==17678== Command: .\/ll_basecode\r\n==17678==\r\n\r\nMake your selection. Press the corresponding number and the enter key\r\n1 - Print list\r\n2 - Insert a node\r\n3 - Find a node by ID\r\n4 - Find a node by name\r\n5 - Erase a node by ID\r\n6 - Erase a node by name\r\n0 - Exit\r\n&gt; 1\r\n\r\nList empty\r\n\r\nMake your selection. Press the corresponding number and the enter key\r\n1 - Print list\r\n2 - Insert a node\r\n3 - Find a node by ID\r\n4 - Find a node by name\r\n5 - Erase a node by ID\r\n6 - Erase a node by name\r\n0 - Exit\r\n&gt; 2\r\n\r\nEnter a name:\r\nKivipallur J\u00fcrto Nii-Dommzonn\r\n\r\nMake your selection. Press the corresponding number and the enter key\r\n1 - Print list\r\n2 - Insert a node\r\n3 - Find a node by ID\r\n4 - Find a node by name\r\n5 - Erase a node by ID\r\n6 - Erase a node by name\r\n0 - Exit\r\n&gt; 2\r\n\r\nEnter a name:\r\nLinnud T\u00f5nisted\r\n\r\nMake your selection. Press the corresponding number and the enter key\r\n1 - Print list\r\n2 - Insert a node\r\n3 - Find a node by ID\r\n4 - Find a node by name\r\n5 - Erase a node by ID\r\n6 - Erase a node by name\r\n0 - Exit\r\n&gt; 2\r\n\r\nEnter a name:\r\nMaamees Jaanes\r\n\r\nMake your selection. Press the corresponding number and the enter key\r\n1 - Print list\r\n2 - Insert a node\r\n3 - Find a node by ID\r\n4 - Find a node by name\r\n5 - Erase a node by ID\r\n6 - Erase a node by name\r\n0 - Exit\r\n&gt; 1\r\n\r\nID: 2\r\nName: Maamees Jaanes\r\npNext: 0x4a80980\r\n\r\nID: 1\r\nName: Linnud T\u00f5nisted\r\npNext: 0x4a808c0\r\n\r\nID: 0\r\nName: Kivipallur J\u00fcrto Nii-Dommzonn\r\npNext: (nil)\r\n\r\n\r\nMake your selection. Press the corresponding number and the enter key\r\n1 - Print list\r\n2 - Insert a node\r\n3 - Find a node by ID\r\n4 - Find a node by name\r\n5 - Erase a node by ID\r\n6 - Erase a node by name\r\n0 - Exit\r\n&gt; 3\r\n\r\nEnter ID:\r\n66\r\nEntered ID is not in the list!\r\n\r\n\r\nMake your selection. Press the corresponding number and the enter key\r\n1 - Print list\r\n2 - Insert a node\r\n3 - Find a node by ID\r\n4 - Find a node by name\r\n5 - Erase a node by ID\r\n6 - Erase a node by name\r\n0 - Exit\r\n&gt; 3\r\n\r\nEnter ID:\r\n0\r\nID: 0\r\nName: Kivipallur J\u00fcrto Nii-Dommzonn\r\npNext: (nil)\r\n\r\n\r\nMake your selection. Press the corresponding number and the enter key\r\n1 - Print list\r\n2 - Insert a node\r\n3 - Find a node by ID\r\n4 - Find a node by name\r\n5 - Erase a node by ID\r\n6 - Erase a node by name\r\n0 - Exit\r\n&gt; 4\r\n\r\nEnter a name:\r\nmi\u00e4u!\r\nEntered name is not in the list!\r\n\r\n\r\nMake your selection. Press the corresponding number and the enter key\r\n1 - Print list\r\n2 - Insert a node\r\n3 - Find a node by ID\r\n4 - Find a node by name\r\n5 - Erase a node by ID\r\n6 - Erase a node by name\r\n0 - Exit\r\n&gt; 4\r\n\r\nEnter a name:\r\nKivipallur J\u00fcrto Nii-Dommzonn\r\nID: 0\r\nName: Kivipallur J\u00fcrto Nii-Dommzonn\r\npNext: (nil)\r\n\r\n\r\nMake your selection. Press the corresponding number and the enter key\r\n1 - Print list\r\n2 - Insert a node\r\n3 - Find a node by ID\r\n4 - Find a node by name\r\n5 - Erase a node by ID\r\n6 - Erase a node by name\r\n0 - Exit\r\n&gt; 0\r\n\r\n==17678==\r\n==17678== HEAP SUMMARY:\r\n==17678==     in use at exit: 0 bytes in 0 blocks\r\n==17678==   total heap usage: 8 allocs, 8 frees, 2,183 bytes allocated\r\n==17678==\r\n==17678== All heap blocks were freed -- no leaks are possible\r\n==17678==\r\n==17678== For lists of detected and suppressed errors, rerun with: -s\r\n==17678== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)<\/pre>\n<\/div><\/div>\n<h4><span class=\"ez-toc-section\" id=\"Extra_task_1_W12-2_Alphabetically_ordered_list\"><\/span>Extra task 1 [W12-2]: Alphabetically ordered list<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>In this task, we&#8217;re alter modify our list in order for it to be always sorted alphabetically by the name.<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Requirements-2\"><\/span>Requirements<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>Update the <span class=\"lang:c highlight:0 decode:true crayon-inline \">InsertNode()<\/span>\u00a0 function in order for it to add the new node in an alphabetically sorted order.\n<ul>\n<li>Must handle adding to the beginning, end and middle of the list.<\/li>\n<\/ul>\n<\/li>\n<li>Update the <span class=\"lang:c highlight:0 decode:true crayon-inline\">FindNodeByName()<\/span>\u00a0 function to take advantage of the list being sorted.<\/li>\n<li>If you completed extra task 2 first, also update the appropriate <span class=\"lang:c highlight:0 decode:true crayon-inline\">Remove()<\/span>\u00a0 functions to also take advantage of this property<\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Notes\"><\/span>Notes<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>Adding to the beginning, end or middle of the list requires different handling of the pointers.<\/li>\n<li>Take note of the positioning and choose appropriate method of adding to the list<\/li>\n<\/ul>\n<h4><span class=\"ez-toc-section\" id=\"Extra_task_2_W12-3_Removal_of_nodes\"><\/span>Extra task 2 [W12-3]: Removal of nodes<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>Implement the two functions to remove nodes from the list.<\/p>\n<h5><span class=\"ez-toc-section\" id=\"Requirements-3\"><\/span>Requirements<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>Implement <span class=\"lang:c highlight:0 decode:true crayon-inline \">RemoveNodeByName()<\/span>\u00a0 that removes a node from the list if it finds a matching name.<\/li>\n<li>Implement <span class=\"lang:c highlight:0 decode:true crayon-inline \">RemoveNodeByID()<\/span>\u00a0 that removes a node from the list if it finds the matching ID value.<\/li>\n<li>Take advantage of the ordered nature of the list (from extra task 1)<\/li>\n<li>Ensure the integrity of the list after removing an element<\/li>\n<\/ul>\n<h5><span class=\"ez-toc-section\" id=\"Notes-2\"><\/span>Notes<span class=\"ez-toc-section-end\"><\/span><\/h5>\n<ul>\n<li>Find if the node exist in the list that you need to remove<\/li>\n<li>Removing from a singly linked list will require you to keep track of the previous node location. You cannot reuse <span class=\"lang:c highlight:0 decode:true crayon-inline \">FindNodeBy()<\/span>\u00a0 function (<em>You could, if it was a doubly linked list).<\/em><\/li>\n<li>Removing from the beginning, end or middle of the list are different. Detect the position and then decide on the removal procedure!<\/li>\n<li>Don&#8217;t forget to free the memory for the node completely<\/li>\n<li>Double pointer is required to remove from the beginning of the list.<\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"After_this_class_you_should\"><\/span>After this class, you should<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>Know the properties of singly and doubly linked lists<\/li>\n<li>Know how the end of a linked list is indicated<\/li>\n<li>Understand the advantages and disadvantages of linked lists<\/li>\n<li>Know the complexity of various operations on a linked list and how it compares to arrays<\/li>\n<li>Be able to create, traverse, and free a linked list<\/li>\n<li>Be able to add elements to the beginning, end, and middle of a linked list<\/li>\n<li>Know how variables declared with the <span class=\"lang:c highlight:0 decode:true crayon-inline \">static<\/span>\u00a0 keyword in functions work and in which memory area they are located<\/li>\n<\/ul>\n<h3><span class=\"ez-toc-section\" id=\"Additional_materials\"><\/span>Additional materials<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<ul>\n<li>What is a Linked list? Types of Linked List with Code Examples<br \/>\n<strong><a href=\"https:\/\/www.freecodecamp.org\/news\/what-is-a-linked-list-types-and-examples\/\">https:\/\/www.freecodecamp.org\/news\/what-is-a-linked-list-types-and-examples\/<\/a><\/strong><\/li>\n<li>Insertion in Linked List<br \/>\n<strong><a href=\"https:\/\/www.geeksforgeeks.org\/insertion-in-linked-list\/\">https:\/\/www.geeksforgeeks.org\/insertion-in-linked-list\/<\/a><\/strong><\/li>\n<li>Wikipedia: Linked list<br \/>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Linked_list\"><strong>https:\/\/en.wikipedia.org\/wiki\/Linked_list<\/strong><\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Lab materials Slides: Linked\u00a0list Lab tasks In this lab, there is one base task and two estra tasks that build upon the base task. Lab task [W12-1]: Linked list In the base task, we are going to implement a linked list. Download the starter code: https:\/\/blue.pri.ee\/ttu\/files\/iax0584\/aluskoodid\/12_ll_basecode.zip Requirements Create a menu program that allows for manipulation &hellip; <a href=\"https:\/\/blue.pri.ee\/ttu\/labs\/pr2en12-linked-list\/\" class=\"more-link\">Loe edasi <span class=\"screen-reader-text\">PR2EN12: Linked list<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[75,105],"tags":[],"class_list":["post-8463","post","type-post","status-publish","format-standard","hentry","category-labs","category-pr2_en"],"_links":{"self":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8463","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/comments?post=8463"}],"version-history":[{"count":11,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8463\/revisions"}],"predecessor-version":[{"id":11181,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/posts\/8463\/revisions\/11181"}],"wp:attachment":[{"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/media?parent=8463"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/categories?post=8463"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blue.pri.ee\/ttu\/wp-json\/wp\/v2\/tags?post=8463"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}