This class is about sorting. It is therefore convenient that you know what was discussed on the lectures:
This class includes the following implementation exercises available on Mooshak:
1. Understanding Linked Lists
(the goal of this exercise is for you to understand a basic implementation of linked lists that uses templates)
Start by downloading the following two files: singlyLinkedList.h (see it in html) and testLists.cpp (see it in html).
Compile the code. The whole SinglyLinkedList<T> class is contained in the .h file, so you just need to compile testLists.cpp (make sure they are in the same directory, so that the line #include "singlyLinkedList.h" knows where to find the file it wants to include). If you are on a shell, you could for instance run g++ -std=c++17 -o testLists testLists.cpp to obain an executable with the name testLists).
Run the code while looking at testLists.cpp on your editor to see each line and its effect. You should obtain the following output:
{}
isEmpty? 1
{1,2,3,4,5}
{10,9,8,7,6,1,2,3,4,5}
size = 10
{9,8,7,6,1,2,3,4,5}
{9,8,7,6,1,2,3,4}
isEmpty? 0
getFirst() = 9
getLast() = 4
Also have a look at each method being called in singlyLinkedList.h to understand how the linkedList is implemented. The figure above gives you an overview of how the class is organized and a similar class (although distinct) was implemented and explained in the lectures.
Notice how the implementation uses templates to be general and therefore supports any data type (not just int).
To make sure you understand how to use it, implement and test the creation of a singly linked list of char containing the 5 vowels: 'a', 'e', 'i', 'o', 'u'.
To understand how the class is providing some error messages, create an empty list and try to get the first or last element. What happens when you run the code?
The error messages might be helpful when you are developing the next methods.
2. Your first linked list method
For this exercise you will be solving the problem [AED026] Returning an element on a given position.
Desired time complexity: \(\mathcal{O}(N)\) (where N is the size of the list)
For this class you will be adding methods to an existing class, so the idea is that you add the requested method at the end of the class (but before the closing brackets). You only need to submit the singlyLinkedList.h file!
If you want to test the method on your computer, you can copy+paste tester code from the problem statement to a file on your computer, compile it and use the input given to see if the results are as expected (note how easy it is to add new inputs, if you want to make further tests).
This problems asks you to traverse the list until the desired position. Have a look at getLast(). What do you need to change to implement the get method?
- You can do the same type of cycle blueprinted in getLast() (use a cur variable to keep the current node, starting with first and always going to the next value).
- If you want to get to position pos, how many next links to you need to traverse?
- After reaching the desired node, you can simply use getValue() to return the desired value.
3. Counting values
For this exercise you will be solving the problem [AED027] Counting elements.
Desired time complexity: \(\mathcal{O}(N)\) (where N is the size of the list)
This is a similar exercise to the previous one, but now you need to count. Can you see how to use a list traversal do the the counting?
- Use the same pattern of link traversal with a cur node, but this time traverse the entire list
- Use an auxiliary variable as a counter and on each iteration check with == to see if the value stored in the node is equal (use cur->getValue()), incrementing the counter when this happens.
4. Removing a node
For this exercise you will be solving the problem [AED028] Removing an element on a given position .
Desired time complexity: \(\mathcal{O}(N)\) (where N is the size of the list)
For this exercise use as a blueprint the method removeLast(). What do you need to change?
- Just as in removeLast(), instead of going until the node, go until the previous node, so that when you need to erase you can just make the current node skip the node you want to delete (the "victim"); don't forget to delete the node after removing it (see the getLast() implementation) if you want to avoid memory leaks (which are not tested explicitly by Mooshak)
- Don't forget to decrease the length variable after removing the node
- Be careful with the case where the node to remove is the first one (as there is no previous node to the first); but in that case you can simply call removeFirst(), right?
5. Inserting a node
For this exercise you will be solving the problem [AED029] Inserting an element on a given position .
Desired time complexity: \(\mathcal{O}(N)\) (where N is the size of the list)
For this exercise use as a blueprint the method addLast(). What do you need to change?
- Because you want to insert before pos you need to stop before the position and do something similar to what is done in getLast()
- Don't forget to increment length variable after inserting the node
- Be careful with the case where you want to insert the node in the first position (as there is no previous node to the first); but in that case you can simply call addFirst(), right?
6. Training for the exam
We provide here a copy of the written exam from the previous year: Exam 25/26 ("normal" season)
(you can access using the AED 26/27 evaluation credentials - check discord or ask your practical class professors for the username and password)
To test your knowledge on Linked Lists and train for the written exam, we suggest you try to do the following exercises with pen and paper (without using a computer to code and test: your focus should be on thinking and expressing your algorithmic ideas):
Try to justify the correctness of your code.
7. Duplicating elements
For this exercise you will be solving the problem [AED030] Duplicating elements .
Desired time complexity: \(\mathcal{O}(N)\) (where N is the size of the list)
Can you do this one without any hints?
8. Removing all occurrences of a value
For this exercise you will be solving the problem [AED031] Inserting an element on a given position .
Desired time complexity: \(\mathcal{O}(N)\) (where N is the size of the list)
For this exercise Mooshak was setup with a large test to make sure your implementation is linear on the size of the list, so you cannot go back to the start of the list each time you remove a node. You should be able to remove as you are traversing the list (and take care when removing consecutive nodes)
The main idea of the challenge problems is to give you the opportunity of improving your problem solving abilities, so it does not necessarily have anything to do with the main topic of the class.
The proposed challenge here is again an adaptation of a problem used on the National Olympiads in Informatics in 2016.
Remember that these challenge exercises are harder and the main idea is to give you the opportunity of improving your problem solving abilities!
For this exercise you will be solving the problem [AED032] Squared Notebook.
Since this is a challenge, I will not give you any hints, but if you are stuck just contact @PedroRibeiro on Discord. Feel free to also contact @PedroRibeiro to discuss your accepted solution.
Happy coding! 😊