Please I need this solved as soon as possible.

The purpose of this assignment1 is to write an ADT list to implement this ADT list as a C++ class that manipulates two singly linked lists in a growing array to do memory management The functionality and thus the interface to this C++ class LList is exactly the same as in Assignment #2. The implementation is different: for this Assignment #3 the C++ class manipulates two singly linked lists (one linked list of free nodes and one linked lists of occupied nodes) so that instead of having pointers that link to addresses in memory (like in Assignment #2), you are going to have as links indices of a dynamic array. The C++ class LList must use the interface provided in LList.h. Do not modify the given (public) interface code of the class definition (except for possibly adding to that public interface though it is unlikely that you will need to in order to finish the assignment properly). Add code to the private part of the class definition in LList.h without modifying the private struct Node, the instance variables and the constant INTIAL_CAPACITY given. Document the class as needed in the header file and the implementation file. The one notable difference in the interface of Assignment #2 is that when NDEBUG is not defined, the internal array is dumped or printed to an output stream.ugly, I know, exposing the internal implementation but you (and we!) need to see the following private data to make sure that the program is correct the contents of the private array nodes the private instance variable head, an index the private instance variable free, an index the private instance variable number of elements in the list the private instance capacity of the array

More Details on the Implementation As per LList.h, in the implementation part of the class, defined is a node as a C++ struct with two fields, item (of type short) and link (of type int which could have been unsigned int). And each node is an element of an array. The link field of the last node of either linked list is set to -1 to simulate the null pointer: use a named constant for this -1. At first the free nodes linked list has all the nodes in the array. I shall refer to this list as the free nodes linked list. The instance variable free has the index of the first available node. At first, also, the head instance variable is initialized to the named constant corresponding to -1 to indicate that the linked list is empty. After a call to cons or append, the integer instance variable head will contain the index of what was the first free nodes node which is the value of the variable free and subsequently free will be updated to indicate that it has lost one free node to head. Another way of explaining the initial: When an x is consed into the linked list pointed to by head, x is put as the item field of the first node of the free nodes linked list which eventually becomes the first node of the list pointed to by head. The variable free is updated accordingly to reflect that the node is no longer part of the free nodes list. When all the xs are to be removed from the list, each node with the item field x is taken out of the linked list pointed to by head (they are pretend deallocated and the pointers (indices!) before and after are fixed) and they are added to the free nodes linked list. Do not use the STL except for std::string (if needed). The functions may or not be recursive. Up to you. Give the static constant NOT_DEFINED an appropriate value. Put a comment why you chose that value. The value NOT_DEFINED is returned by the function first and last if there is no first element or last element in the list. You could use a dummy head node if you want. Hint which is optional: Have one last free node before growing the array. You must use one growing array that is allocated dynamically (using the operator new). Do not just use a static array. Do not use a variable length array. You can assume that there is enough heap memory. Implement the copy constructor, the destructor and the overload assignment operator (you do not need to implement neither the move constructor nor the move assignment operator). Hint: Do not forget to copy all the instance variables. Though not recommended, you can have a tail index pointer. Bonus worth up to 30% extra Once you have implemented splice and halve, you will have noticed that in a proper object-oriented manner, each instance of the class LList has its own growing array. But that design is lacking (nice way of saying, the design is bad). Design the memory management better: you will still need a growing array of nodes, you will still use indices instead of memory addresses, but you do not need an array per instance of the class LList. Have various instances of the class LList share a common array of nodes. Each instance of LList will still have an instance variable head which is an index to the growing array and a variable free which is an index of the free nodes list. You may change the LList.h slightly but keep the functionality. You must put in the README.txt in the first directory that you have implemented the bonus part, otherwise it will not be marked.