Lab materials

• Slides: Linked list

Lab tasks

In this lab, there is one base task and two advanced tasks that build upon the base task.

Lab task: 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 of a singly linked list
• New nodes must be added to the beginning of the list only.
• A node contains a number (id) and a string (name).
  • id is auto-generated, unique, sequential integer starting from 0
  • Name is a string entered by the user during creation of the node.
  • Name is allocated dynamically, dependent on the length of the entered name.
• Implement the PrintNode() , CreateNode() , InsertNode() , FindNodeByID() , FindNodeByName()  and Unload()  functions based on their description
• Use the starter code provided as your base
• Work through the task base on the step-by-step guide. Implement the functions as specified in the guide.

Step-by-step guide

NB! Notice that the structure declaration creates 2 valid data types – struct node  and list . While both are  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.

---

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).  It needs to print all members of the node.

PrintNode()  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.  This way, whenever the contents of the node changes, the modifications for printing only need to be made once in a single place.

Don’t forget to check for NULL pointer to avoid crashing if the calling function decides to pass a NULL pointer.

Uncomment testing stage 1 and run your code!

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.

---

NB! This function is already completed for you. Pay attention to how the loop is built. You need it for traversal in the later functions.

This function is used to print the entire linked list.  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 NULL  pointer..

The function also handles a NULL  pointer passed to it instead of a valid pointer to the beginning of the list – this will happen when the linked list is empty!

The function itself does not handle printing of the nodes, but rather calls  PrintNode()  on every node to print its contents. This is why we completed that first.

Uncomment testing stage 2 and run your code!

---

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.

1. Create and allocate the node
2. Assign the ID value (sequentially incrementing value, use static )
3. Allocate memory for the name and copy it over
4. Initialize the pNext  pointer
5. Return the struct pointer

NB! There are two memory allocations in this function. Both need to be checked. If there’s an error, return a NULL pointer! Program should continue running.

Uncomment testing stage 2 and run your code! Only expected changes are different address space (going from stack to heap) and increased allocations when checking with valgrind.

---

This function adds the node pNode  to the list pointed by ppHead . Double pointer is required to change the location of the beginning of the list.

In the base version of the task, add the node to the beginning of the list (onlu 2 assignment statements!)

NB! Before adding, check that pNode  isn’t a NULL  pointer!

Uncomment testing stage 3 and run your code!  Visually you should not see any differences in the output.

---

This function is what’s also called a destructor. It removes (deallocates) all nodes from them memory. This includes all the members that were allocated dynamically as well – in our case, the name.

To free a linked list, you need to loop through the entire list. To familiarize yourself with the traversal of the list, check the   PrintList()  function.

When freeing the list, you should pay close attention to how you free the current node. After freeing the current node, we no longer have access to its  pNext  pointer. Due to this, we need to create a temporary pointer that will have a copy of the current node’s address, which adds a little bit of complexity.

You have to complete 3 steps in the loop. The most elegant way of making it is by using a  while()  loop.

1. Make a copy of the current node address (you will be freeing through this copy)
2. Move the main pointer to the next element ( pCurrent = pCurrent->pNext )
3. Free the current node and its members.

Uncomment testing stage 4.  Run through valgrind. You should see 6 allocations and 6 frees.

---

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.

Use PrintNode()  to output the result.

Uncomment testing stage 5 and check the output! Note that the error message is provided by PrintNode() function and is not specific to the search!

---

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.

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. Once that is done, present the task.

Testing

This is the final expected output of the base task

Advanced task 1: Alphabetically ordered list

In this task, we’re alter modify our list in order for it to be always sorted alphabetically by the name.

Requirements

• Update the InsertNode()  function in order for it to add the new node in an alphabetically sorted order.
  • Must handle adding to the beginning, end and middle of the list.
• Update the FindNodeByName()  function to take advantage of the list being sorted.
• If you completed advanced task 2 first, also update the approriate Remove()  functions to also take advantage of this property

Notes

• Adding to the beginning, end or middle of the list requires different handling of the pointers.
• Take note of the positioning and choose appropriate method of adding to the list

Advanced task 2: Removal of nodes

Implement the two functions to remove nodes from the list.

Requirements

• Implement RemoveNodeByName()  that removes a node from the list if it finds a matching name.
• Implement RemoveNodeByID()  that removes a node from the list if it finds the matching ID value.
• Take advantage of the ordered nature of the list (from advanced task 1)
• Ensure the integrity of the list after removing an element

Notes

• Find if the node exist in the list that you need to remove
• Removing from a singly linked list will require you to keep track of the previous node location. You cannot reuse FindNodeBy()  function (You could, if it was a doubly linked list).
• Removing from the beginning, end or middle of the list are different. Detect the position and then decide on the removal procedure!
• Don’t forget to free the memory for the node completely
• Double pointer is required to remove from the beginning of the list.

After this class, you should

Additional materials