Linked list lab task

[Download the basecode]

[slides]

Structure to be used:

A node contains the person’s name, ID code assigned to that person and the pointer to the next structure of the same type

For the root (starting point of the list) you can use this declaration

Lab task: Implement the following functions

NB! The following prototypes are recommended. If needed, they can be altered (e.g. you can write CreateNode() and InsertNode() functions as one single function or when picking the simpler task, use single pointer instead of the double pointer.

It’s recommended to implement the functions in the same order as they are in the documentation.


 

This function has been done for you. However since it depends on the function PrintNode(), which is not yet implemented, it’s commented out.

Function prints out all of the elements in the linked list. It’s recommended to use PrintNode() function for each element since it’s guarantees a more modular approach (e.g. then changing the layout of the structure, only this function needs to be changed).

A pointer to the first element of the list is passed to the function. It’s important to check if the pHead isn’t a NULL-pointer. By doing this you’ll avoid trying to print when there are no elements in the list (empty list)


 

A pointer to a single node of the list is passed as an argument. It’s recommended to use this function within the functions InsertNode(), FindNode(), PrintList() and RemoveNode(). This will save you time and will keep the program less prone to errors and legacy implementations when changing the structure.

It’s recommended to check if the passed node isn’t a NULL pointer to avoid crashes due to faulty implementation of the calling function.


 

 

Function creates a new node. The return value is the pointer to the newly created node. During the creation of the node, input from the user will be asked for and memory will be allocated to store that allocation. This should also include fault checks.

If this fails, a NULL pointer will be returned. Program should keep on running.


 

 

Function adds a node to the list. First of all, it calls CreateNode() to create the new node and then assigns the returned node to the list at a suitable place (set up the pointers). The position of the new node is determined by the difficulty you selected!

Before starting to look for the position, remember to check for NULL-pointer from CreateNode(). If it’s NULL, don’t exit the program  – continue with what you have.

When using the easier variant of the task, you can use the following prototype:

To save time, you can write InsertNode and CreateNode() as one, however this will make the code less modular.


 

 

Search functions to either search by ID or by key. The functions return the pointer to the node found or a NULL-pointer when the element was not found.

Recommendation: use PrintNode() to output the result.

Advanced:

Implement the following functions:

void removeNodeByKey(list **pHead, char *key);

Removes a node from the list that has the matching name. When removing the node, all of the members of that struct will be freed first, followed by the node itself.

You must ensure the integrity of the list when removing a node – when removing a middle node, you must tie the previous node together with the one following the removed node.  Removing the first and last nodes are also considered special cases.

Same as the last one, however searching is done using the ID number

 

Function removes all of the nodes and their content from the memory.

 

Simpler variant (1.5p)

For the simpler variant, the list is created unsorted.

Function InsertNode() will add nodes only to the beginning of the list. You can use the simpler prototype for the function and have less corner cases to check for.

 

Harder variant (2.5p)

In the harder variant, the list will always be sorted alphabetically.

The function InsertNode() will look for the right spot in the list to add the new node so it would be in alphabetical order. Adding the node will have to take into account if the element is added as the first, middle or last element of the list and assign the pointers accordingly.

Functions InsertNode(), RemoveNode() and FindNode() should also take into account that the list is sorted in the alphabetical order.