Purpose: To build programming skills by implementing the linked list ADT. To leam to implement an ADT according to a description. To learn to use testing effectively. To master the concept of reference. To master the concept of node-chains. To gain experience thinking about different problem cases. Degree of Difficulty: Moderate There are a few tricky bits here, but the major difficulty is the length of the assignment. Do not wait to get started! This question will take 35 hours to complete. Restrictions: This question is homework assigned to students and will be graded. This question shall not be distributed to any person except by the instructors of CMPT 145. Solutions will be made available to students registered in CMPT 145 after the due date. There is no educational or pedagogical reason for tutors or experts outside the CMPT 145 instructional team to provide solutions to this question to a student registered in the course. Students who solicit such solutions are committing an act of Academic Misconduct, according to the University of Saskatchewan Policy on Academic Misconduct. 1. On Canvas you will find two Python scripts: - LList:py - score.py Download them and add them to your project for Assignment 6 . See below for a section on how to use the test scripts. 2. It is your task to implement all the operations in the LList.py script. Currently, the operations are stubs, meaning that the functions are defined but do nothing useful yet. They return trivial values, and you'll have to modify them. 3. The Linked List operations are described in the course readings, in lecture, and below. The linked list ADT The Linked List ADT is very much like the node-based Queue ADT we studied in class. The _._init _O operation is as follows: class LLiat (object): A linked list is an object with the following attributes: size This keeps track of how many values are in the list. head This is a reference to the first node in the node chain. An empty Linked List has no node chain, which we represent with None. tail This is a reference to the last node in the chain If the list is empty, this is None. Notice that the LList attributes are protected. This helps us write test cases that would not be possible with private attributes. Also note that the node class attributes are public. This makes their use in the LList class a little easier. We no longer need to use the setters and getters from Chapter 14 , in which the attributes were private. Figure 1: A frame diagram for a typical example of a non-empty linked list. The Linked List ADT operations When you open the Li.ist.py document. you will find a complete description of all the operations you have to implement. Here is a brief list of them, with a few hints. __init__ O Creates an emply Linked Listobject. This is already completel is_emptyo Checks if the Linked List object has no data in it. Hint: Stack and Cueue have this one size0 Retums the number of data values in the Linked List object. Hint: Stack and Queue have this one. prepend(vaD Adds the data value val into the Linked List object at the front. prepend(val) Adds the data value val into the Linked List object at the front. Hint: This is similar to Stack's push ( ). append(val) Adds the data value val into the Linked List object at the end. Hint: This is similar to Queue's enqueue. get_index_of_value(val) Returns a tuple (True, idx), where idx is the index of val in the Linked List object. If val is not found. it should return (False, None). Hint: Just walk along the chain starting from the head of the chain until you find it, or reach the end of the chain. If you find it, return the count of how many steps you took in the chain. The index of the first value in the list is O, just as in normal Python lists. remove_from_frontO) Removes the first node from the node chain in the Linked List object. Retums a tuple (True, val), where val is the data value stored in the removed node. If the Linked List is empty, it should return (False, None). - For example, calling allist.remove_from_front O in Figure 1 would remove the node containing 10 from the node chain, and return the tuple (True, 10 ). Hint: This method is simitar to Queue's dequeue, except for a few details. remove_from_back0 Removes the last node from the node chain in the Linked List object. Retums a tupte (True, val), where val is the data value stored in the removed node. If the Linked List is empty, it should return (False, None). - For example, calling allist. remove_from_back () in Figure 1 would remove the node containing 18 from the node chain, and return the tuple (True, 18). retrieve_data(idx) Returns a tuple (True, val), where val is the data value stored at index idx. If the index is not valid (negative. or too targe), it should return (False, None) - For example, calling allist. retrieve_data(2) in Figure 1 would return the tuple (True, 5). The node chain is not changed. Hint: Walk along the chain, counting the nodes, and return the data stored at idx steps. Start counting at index zero, of course! set_datalidx, val) Store val into the Linked List object at the index idx. This method does not change the structure of the list, but will change the data value stored at a node. Returns True if the index is valid (and the data value set), and False otherwise. - For example, calling allist.set_data (5,24) in Figure 1 would change the data value in the sixth node from 19 to 24. The node chain is not changed. Hints: Break the problem into 3 parts, and get each part working and tested before you go on to the next part. - First, deal with trying to remove from an empty list. - Second, deal with removing the last value in a list if size is exactly 1 and no bigger. - Third, deal with the general case. Walk along the chain, counting the nodes, and store the new value as data at the node idx steps in. Start counting at index zero. of coursel Because of the similarity between the Linked List ADT and the node-based Queue and Stack ADTs, some of the operations will be similar, if not exactly the same. You may borrow from Queve and Stack (the nodebased implementations), being careful to realize that copy/paste may only be the start of your work, not the end! How to FAIL to complete this question Write all your code all at once, without any testing as you go. Then run the test scripts to find that youve got a lot of errors to fix. Good luck! How to complete this question Write one function at a time, starting with a simple node-chain version (Uike A5). Test your node-chain version, and when you are sure it works, adapt it for the linked list operation. Then run the unit test script, with a limit on the number of failures reported. Debug each operation one at a time, then when the unit test script reports no errors in the operation, move on to the next. Testing using the given test script We ve provided a test script which includes unit testing, and integration testing. It is fairly well documented, so you can open it up and have a look. The script consists of definitions of simple Python functions, all of which have the same basic task: 1. First, create a test harness for the test. This usually involves creating a LList object somehow. As were doing unit testing on the LList ADT, we sometimes create node and LList objects without using their methods. This is valid in a test script. but not in an application; we can violate the ADT Principle in testing the ADT. 2. Second, check how one other operation works in the given context. In our scripts, we use assertions. which check for something that should be true, and which alert us when that thing is not true. It's a simple test of the _._init__() operation. A list is created, and then an assertion is used to check if the size is equal to zero. Notice how the assertion replaces the familiar if-statement that we would expect to see in the testing we have done so far. An assertion like this only reports a problem if the condition is false. This particular test will pass using the script L..ist.py that we ve given you, it may fail if you tinker with the -.init _. () operation. Here's an integration test This test creates a list, adds a bunch of strings to the list, then checks is_empty (). The test script runs all the tests, and produces output to the console. It counts how many tests have been attempted, and how many are passed. At the end of the script, the script will also report the grade you will earn on this question. - The test script has a variable named verbose which is set to True by default. This will cause any error to be displayed to the console. The verbose output will show you which test cases did not pass by name. - You can reduce the amount of output by setting verbose = False, but it will not tell you the names When you run the test script on the file as given on Canvas, you should see that 17 of the tests pass before you have added any code to LList.py. That's because the function stubs coincidentally give the correct answer for those 17 test cases. You may write your own test scripts (using the simple format we've used before, or you can try your hand at using the style here). When you think you've got a working operation completed, run the test script. You will know you are done when you see something like this: Passed: 142 test out of 142 Total tests: 143 Tests passed: 143 Passed: 143 Resulting Grade: 30 out of 30 Be carefult it's fairly easy to write a loop that never terminates, and you might think the test script stopped early, when it's stuck half way through. If you don't see a final report, the script is still running. What to Hand In Hand in your LList.py program, named LList.py. It should contain only the LList class land the node class) operations, and nothing else (no test code, no extra functions). Do not submit score.py. Be sure to include your name, NSID, student number, course number and laboratory section at the top. Evaluation - Your solution to this question must be named LList.py, or you will receive a zero on this question. - 9 marks: You completed an implementation for all 9 operations. One mark per operation. The implementation is not being graded for correctness, but it should be relevant, and it should be code written with an effort to demonstrate good style and internal documentation. The mark will be deducted if there is no implementation, or if the function does not demonstrate good programming style. - 30 marks: When our scoring script runs using your implementation of LList. py. no errors are reported. Partial credit will be allocated as follows: For example, if your implementation passes 109 tests, youll get 27/30. If your implementation passes 72 tests, you'll get 20/30. Our test script is based on the test scripts distributed with the assignment, but may not be exactly the same