In this lab, you will complete 4 methods in the SLList class with sentinel node. This class is a generalized version of the singly linked list class discussed in the class meetings using templates.
Follow the instructions from Lab 1 to open the lab folder in VSCode.
The new files in this lab are
SLList.h: the definition of the Node and SLList classThe remaining files/directories are similar to those in Lab 1.
You are expected to modify SLList.h to add your code for the 4 methods (search in the file for TODO) and upload it to the autograding system.
You should give your own implementation of the SLList(const SLList &other) method.
The copy constructor should deep-copy the other list to create a list that is identical to other.
🍰 Tips: Similar to the first problem in Extra IntList Practice.
The get(i) method in SLList.h returns the i-th item in the list. For example, given a list L=[5,10,15]. Calling get(0) on L should return 5, while get(1) and get(2) should return 10 and 15, respectively. You can assume the item always exists.
🧁 Tips: Traverse through the list, stop the traversal when the i-th node is hit, and return the item, in an iterative way; or do it recursively (like in IntList).
Method removeFirst and removeLast are used to remove and return the first and last elements in a list. For example, given a list L=[1,2,3,4], L.removeFirst() deletes and returns the first item 1 in L. The resulting L is now [2,3,4]. Calling L.removeLast() deletes and returns the last item 4 in L and L now becomes [2,3]. You may assume the first/last item always exists.
🍩 Tips: For removeFirst, the first node is pointed to by sentinel->next, and after deletion sentinel->next should be updated to the new first node; for removeLast, you can refer to addLast(x): traverse through the list to find the node in front of last node, and after deletion the next of this node should be set to nullptr.
A sample doctest test case is given in main.cpp. We will discuss how to write doctest tests later in class. But you can first have a look and try to modify or create your own tests.
To test your code using main.cpp, follow the instructions from Lab 1.
When you run the test case in main.cpp, you will see the pass/fail output by doctest. You should also see a report generated by AddressSanitier if there are memory errors, similar to the following:
==2852==ERROR: LeakSanitizer: detected memory leaks
Direct leak of 32 byte(s) in 2 object(s) allocated from:
#0 0x7f432f452448 in operator new(unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.4+0xe0448)
#1 0x55d500a532d3 in ds::SLList<int>::addFirst(int) /workspaces/lab2/SLList.h:51
#2 0x55d500a44170 in DOCTEST_ANON_FUNC_5 /workspaces/lab2/main.cpp:16
#3 0x55d500a3e824 in doctest::Context::run() /usr/include/doctest.h:6727
#4 0x55d500a404de in main /usr/include/doctest.h:6805
#5 0x7f432e663bf6 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6)
SUMMARY: AddressSanitizer: 32 byte(s) leaked in 2 allocation(s).
A correct implementation should pass all test cases and assertions and have no memory error, as shown below:
[doctest] doctest version is "2.4.8"
[doctest] run with "--help" for options
===============================================================================
[doctest] test cases: 1 | 1 passed | 0 failed | 0 skipped
[doctest] assertions: 11 | 11 passed | 0 failed |
[doctest] Status: SUCCESS!
After testing the program locally, you should submit SLList.h to the autograding system.
There will be 10 test cases in total to evaluate your implementation. For each passing test case, you will get 3 points if there is no memory error and 2 points if there are memory errors.
You may refer to the instructions from Lab 1 for more instructions.