In this lab, you'll explore collections and dynamic data structures (linked lists). Specifically, you'll develop a small console application that defines a Node class and then make use of that Node class, including Add and Delete methods.
The lab will have multiple steps, and you should try and perform the lab steps on your own, but certainly click through the how-to links to see step-by-step walkthroughs on how to complete each step.
Here are the steps:
The first step is to write the Node class. Recall that the Node must contain two parts - the DATA and the NEXT. So write a simple Node class that contains public Data and Next attributes (you can make the Data type whatever you'd like, but in my example solutions, I'll use INT).
Also, make three constructors for this Node class - one that takes no parameters, one that takes in what the Data attribute should be initialized to, and one that takes what the Data and the Next should be initialized to.
Also, override the ToString method so that the Node class knows how to render itself as a string. This method should be recursive and display the data of the node and all the rest of the list. If the rest of the list (marked as Next) is null, then you can simply display the \\ marks. Otherwise, you should recurse through the remainder of the list and have it display the entire list.
Click this how-to to see a step-by-step solution for this part of the lab.
Now that you have the basics of the Node class, let's add an AddToFront method to our program.
One could place this method into the Node class itself, but actually, we need to do some thinking here; when I want to add to the front, I really want to add to the front of a list, not a node. It's a subtle difference, but significant. In step one, we built a Node class, but here, to add to the front, we actually need a List class, and then the AddToFront would be a method of the list class.
So next, define a new class called List. Add a Node attribute to this class, but make it private (since the List is responsible for managing the nodes, and thus the head of the list should not be visible outside of the List class). Then add a method called AddToFront that takes in a variable (of whatever type your Node manages) and creates a new node at the beginning of the List's collection of Nodes. Also be sure to override the ToString method of the List class as well.
Then in Main, create a new List and invoke the AddToFront method a few times. Be sure to display the list to the screen to ensure everything is working properly.
Click this how-to to see a step-by-step solution for this part of the lab.
The final step in this lab is to implement the Delete method for the List class. In this method, we want to take in the value we want deleted from the list. We could write the Delete method in two ways, deleting only the first occurrence or deleting all occurrences of the value we want removed; we'll implement the latter and remove all instances.
This method should be recursive in nature, and scan the entire list. If a match is found between the value to delete and the data attribute of the node, then the node should be removed. This is accomplished by moving the reference to the node just beyond itself and then recursing again (but this time recursing on current since we've already moved the reference down the list by one). If a match is not found, we simply recursively call the method again, this time using the Next reference of the current node.
One problem we have, though, is that this recursive method must take in two parameters - the value to delete and the current node we're examining. But the Main algorithm doesn't have access to the current node (and in fact doesn't even know Nodes are being used to manage the list). So we need a helper method that is private that will do the recursion and then a public method that only takes in one parameter - the value to delete. This public method then can invoke the private method, adding the needed Node parameter.
Also, don't forget that the Node parameter to the recursive function must be a ref parameter so that the changes are persistent and the node is actually removed when the function is finished.
When you've finished implementing this Delete method of the List class, invoke it a few times in Main, ensuring that the method works for values that are in the list, values that aren't in the list (nothing should change), and for duplicate/replicated values in the list.
Click this how-to to see a step-by-step solution for this part of the lab.
Click her to see the finished ZIPed solution.