this whole project

Overview The purpose of this assignment is for vou to write a data structure called a Linked List, which utilizes templates (similar to Java's eenerics), in order to store any tvpe of data. in addition, the nature of a Linked List will give you some experience dealing with non-contiguous memory organization. This will also give vou more experience using pointers and memory manugement. Fointers, memory allocation. and understand how data is stored in memery will serve you well in a variety of situations, not just for an assignment tike this. Background Remember Memory? Variables, functions, pointers-everything takes up somE space in memory. Sometimes that memory is occupied for only a short duration (a temporary variable in a function), sometimes that memory is. allocated at the start of a program and hangs around for the lifetime of that program. Visualizing. memory can be difficult sometimes, but very helpful. You may see diagrams of memory like this: Or, you may see diagrams liket these: If you are trying to draw out some representation of memiory to help you solve a problem, any of these (or some alternative that makes sense to you) will be fine. COP3503 Programming Fundamentals 2 Arrays Arrays are stored in what is called contiguous memory. A contigoous memory block is one that is not interrupted by anything else (lie any other memory block). So if you created an array of 5 integers, each of those integers would be located one after the other in memory, with nothing else occupying memory between them, This is true for all arrays, of any data type. \begin{tabular}{l} int someArray[5]i \\ someArray[0] =2j \\ someArray [1]=4j \\ someArray [2]=6j \\ someArray [3]=8j \\ someArray [4]=10; \\ \hline \end{tabular} All of the data in an application is not guaranteed to be contiguous, nor does it need to be. Arrovs are typically the simplest and fastest way to store data, but they have a grand total of zero features. You allocate one contiguous block, but you can't resize it, removing elements is a pain (and siow), etc. Consider the previous array. What if you wanted to add another element to that block of memory? If the surfounding memory is occupied, you can't simply overwrite that with your new data element and expect good results. In this scenario, in order to store one more element you would have to: 1. Create another array that was large enough to store all of the old elements plus the new one 2. Copy over all of the data elements one at a time (including the new element, at the end) 3. Free up the old array-no point in having two copies of the data This process has to be repeated each time you want to add to the array (either at the end, or insert in the middle), or remove anything from the array, It can be quite costly, in ferms of performance, to delete/rebulld an entire array every time you want to make a single change. Cue the Linked Listl COP3503 Programming Fundamentais 2 Linked List. The basic concept behind a Linked tist is simple: 1. It's a container that stores its eiements in a non-contiguous fashion 2. Each element knows about the location of the element which comes after it (and possibly before, more on that lateri So instead of a contiguous array, where element 4 comes after element 3 , which comes atter element 2 , etc-you might have something like this: Each element in the Linked List (typically referred to as a "node") stores some data, plas some sort of reference (a pointer, in C++ ) to whatever node should come next. The first node knows only about itself. and the Second node. The Second node knows only about itsell, and the Third, etc. In this example the Fourth node has a null pointer as its "next" node, indicating that we've reached the end of the data. A real-world example can be helpful as well: Think about a line of people, with one person at the front of the line. That person might know about the person who is next in line, but no further than that fbeyond him or herselt, the person at the front doesn't need to know or care). The second person in line might know about the third person in line, but no further. Continuing on this way, the last person in line knows that there is no one else that follows, so that must be the end. So... What are the advantages of storing data lise this? When inserting or removing elements into an array, the entire array has to be reallocated. With a Linked tist, only a small number of elements are affected. Only elements surrounding the changed element need to be updated, and all other elements can remain unaffected. This makes the Linked List much more efficient when it comes to adding or removing elements. Now, imagine one person wants to step out of line. If this were an array, all of the data would have to be reconstructed elsewhere. In a Linked List, only three nodes are affected: 1) The person leaving, 2) the person in front of that person, and 3) the person behind that person. Imagine you are the person at the front of the line. You don't really need to know or care what happens. 10 people behind you, as that has no impact on you whatsoever. COP3503 Programming Fundamentals 2 If the 5th person in line leaves, the only parts of the line that should be impacted are the 4,5/ and 5. spaces, 1. Person 4 has a new "next" Person: whomever was behind the person behind them (Person 6 ). 2. Person 5 has to be removed from the list. 3. Person. 6 . actually does nothing in this example, a Person only cares about whomever comes after them. Since Person 5 was before Person 6 , Person 6 is unaffected. (A Linked List could be implemented with two-way information between nodes - more on that later). The same thought-process can be applied if someone stepped into line imaybe a friend was holding their placels In this case, Person 2 would change their "next" person from Person 3, to the new Person being added. New Guy would have his "next" pointer set to whomever Person 2 was previously keeping track of, Person 3. Because of the ordering process, Person 3 would remain unchanged, as would anyone else in the list (aside from being a bit irritated at the New Guy for cutting in line). So that's the concept behind a Linked List. A series of "nodes" which are connected via pointer to one another, and inserting/deleting nodes is a faster process than deleting and reconstructing the entire collection of data. Now, how to go about creating that? COP3503 Programming Fundamentals 2 Nested Classes The purpose of writing a class is to group data and functionality. The purpose of a nested class is the same - the only difference is where we declare a nested class. We declare a nested class like this: The nature of the Linked list is that each piece of information knows about the information which follows (or precedes) it. It would make sense, then, to create some nested class to group all of that. information together. LinkedListClass \{ NestedNodeClass \{ // The data you are storing I/ A pointer to the next node // A pointer to the previous node (if doubly-linked) \} /I A node pointer to the head // A node pointer to the tail /I How many nodes are there? \}; COP3503 Programming Fundamentals 2 Benefits and Drawbacks Alt data structures in programming ( C++ or otherwise) have advantages and disadvantages. There is no "one size fits all" data structure, Some are faster (in some cases), some have smaller memory footprints, and some are more fiexible in their functionality, which can make life easier for the prosrammer. Code Structure As shown above, the Linked List class itself stores very little data: Pointers to the first and last nodes. and a count. In some implementations, you might only have a pointer to the first node, and that's it. In addition to those data members, your Linked List class must conform to the following interface: /=m= Behaviors ===**/ void PrintForward() const; void PrintReverse() const; void PrintForwardRecursive (const Node* node) const; void PrintReverseRecursive (const Node* node) const; /==== Accessors =mm**/ unsigned int NodeCount() const; void FindAll(vector\& outData, const T\& value) const; const Node* Find(const T\& data) const; Node* Find(const T\& data); const Node* GetNode(unsigned int index) const; Node* GetNode(unsigned int index); Node* Head(); const Node* Head() const; Node* Tail(); const Node* Tail() const; COP3503 Programming Fundamentals 2 Function Reference COP3503 Programming Fundamentals 2. Template types and the typename keyword The compilation process for templates requires specialiation - that is, your compller essentially copiesand-pastes a version of your template, replacing all the instances of T> with the type you specified when creating an instance of the class. When dealing with templates within templates, nested template classes, etc... the compller sometimes needs a bit of assistance when figuring out a type. In order to know how to specialize, it has to know everything about the remplate class, If that template has some other template, it needs to know everything . before it knows everything-, and therein lies the problem. The typename keyword is a way of telling your compiler "Hey, what immediately follows typename is a data type. Treat it as such when you compiler everything else." For example: When defining the function "Somefunction" you might write this: template 23.21 Project 1 - Linked list Part 2 Pun your program as often as youd like, before submitting for grading Bolow. type any Beeded nput values in the firat box, then click Run program and observe the programis output in the wecond box For this part you will implement functionality to insert elements into the linked list, one of the primary advantages of this data structure (This can be achieved with arrays as well, but it is much faster with a linked list) You will implement the following: - InsertBefore( - insertafter0 - insertat0 In addition, you will implement the equality operator, to test if two lists are equal to one another. - operatora= In this last part you are going to implement vatious functions to remove nodes from the list, the other two members of the Big Three. as. Well as an alternate way of iterating through your nodes to ptint them using recursion. Youll implement the following Removal functions - RemovelHeado - Removetailo - RemoveAlO - Remove0 - Clear() Big Three - Copy Constructor - operator: Recursive Print Functions - PrintforwardRecursive0 - PrintPeverseRecursive0 Run your program as often as youd like, before submitting for grading. Below, type any needed input values in the first box, then click Run program and observe the program's. output in the second box. Enter program input (optional)