CSE 212 | Assignment

Code 04: Linked Lists

This assignment must be completed individually to ensure you are meeting all course outcomes. You should not complete this assignment within a group. If you obtain help from a tutor, the tutor should help you understand principles but should not help you answer these problems. It is an honor code violation to obtain answers for these problems from others including using the internet (i.e. sites that allow students to share their solutions).

Running and Debugging

You should not edit any files that have the comment DO NOT MODIFY THIS FILE at the top of them. Any edits you make to these files will be removed before grading.
Running all tests for this assignment: Click on Run and Debug in the sidebar, then select this week's code assignment from the drop-down at the top. Click the green Start Debugging button next to the drop-down. The integrated terminal will show the files being compiled and then the tests being run. It will print a summary of which tests passed and failed.
Running individual tests: Navigate to the test file ending in _Tests.cs in the week's code directory. Visual Studio Code will show inline buttons to Run Test for each test method, or to Run All Tests for each test class.
Debugging individual tests: Navigate to the test file ending in _Tests.cs in the week's code directory. Visual Studio Code will show inline buttons to Debug Test for each test method, or to Debug All Tests for each test class.
- If you put a breakpoint inside your code or inside the test, the only way to hit it will be by clicking Debug Test or Debug All Tests in this file.
- If you want to debug by printing output to the terminal, you must use Debug.WriteLine() to do so. Using that may require you to add using System.Diagnostics; to the top of the file. Using Console.WriteLine(), as is done in other parts of the template project, will not correctly print output to the console when a test is running. Any output generated with Debug.WriteLine() will appear in the Debug Console portion of the integrated terminal when clicking Debug Test or Debug All Tests in this file.

Instructions

As you solve the problems, remember to use the principles learned previously in the course:

Problem Solving Strategy: understand the problem, plan and design the solution, implement the solution, and evaluate the solution.
Evaluate Performance of Alternative Solutions: use big O to determine the best solution.
Understanding Code Using Reviews: analyze any code you have been given.
Finding Defects Using Tests: write tests to determine if your solution is working.
Articulating Answers for Technical Questions: imagine that you were asked one of these questions during an interview. Remember to ensure that you fully understand the problem and work through different scenarios manually. Consider how the data structure you are using will help you solve the problem. A notebook or a whiteboard can be very useful in this process.

All of the files for this assignment will be found in the course Git repository in the week04/code folder. You will commit changes to your own repository for your submission for this assignment.

Insert Tail

Implement the InsertTail function in the LinkedList class. The function should add a new node (Node) at the end of the linked list. Hint: Consider the code already written for InsertHead.

Remove Tail

Implement the RemoveTail function in the LinkedList class. The function should remove the last node. Hint: Consider the code already written for RemoveHead.

Remove

Implement the Remove function in the LinkedList class. The function will need to search for the node (starting at the head) that contains the value and then remove that one node. The function should not continue searching the list once a match has been found and the node has been deleted. Hint: You may be able to reuse the RemoveHead and RemoveTail functions.

Replace

Implement the Replace function in the LinkedList class. The function should search for all nodes that are equal to oldValue and then replace the value in those nodes with newValue. Unlike the remove function, this function should continue searching through the list to replace all values that match oldValue.

Reversed Iterator

The GetEnumerator function provides the ability to iterate forward through a LinkedList object using a foreach loop such as foreach (var item in myLinkedList). When a foreach loop starts, the GetEnumerator function will start. Each time the yield return statement runs, it will provide a new value to the foreach loop and pause the GetEnumerator function. When the foreach loop goes to the next iteration, it will continue running the GetEnumerator function again until it gets to the next yield return which will provide the next value to the foreach loop. You can use the following test code to see how the GetEnumerator function works:


foreach(var item in myLinkedList)
{
    Debug.WriteLine(item);
}

The Reverse function is used to iterate backwards. Implement the Reverse function in the LinkedList class. Hint: Pattern your solution after the GetEnumerator function that was already written for you and that was described above. To test the Reverse function, you can use the following code:


foreach(var item in myLinkedList.Reverse())
{
    Debug.WriteLine(item);
}

Grading

To receive full credit on this assignment, you must successfully complete any four of the five problems. If you complete all five problems you are eligible to receive extra credit.

Submission

When you have finished the assignment:

Make sure that all of your changes are committed to your course repository.
Push your latest changes to GitHub.
Return to I-Learn to submit a link to your GitHub repository.