Assignment #3: ADT List implemented as Linked Lists in an Array Assignment due with Brightspace at 11:50pm on Wednesday February 3 Read in the textbook chapters 1 (skip $1.3, 61.5), chapter 5 (skip $5.9) and chapter 3. The purpose of this assignment' 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 wel) 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 The following assignment is based on the Programming Problem #11 on page 245 in Data Abstraction and Problem Solving with C++: Walls and Mirrors by Frank M. Carrano, 5h Edition, Pearson Education, Inc., 2007. But it is different. 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 x's 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 Last.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. To submit as Assignment #3 a single compressed zip file a directory that contains o List.h (add YOUR code) oLList.cpp (add YOUR code) Llist_unittest.cpp (add more tests optionally: it will not be marked) Makefile (provided do not modify) test_LList.cpp (leave as is or add more code: it will not be marked but it should work with NDEBUG not defined so that we can see if your program is working) a README.txt if needed but if you did the bonus, indicate so in this README.txt a second directory with the bonus part a README.txt that explains the design of your memory management including how the constructor is to be called LList.h you can pass to the constructor of the LList an instance of a class that does the memory management: in such a case, the constructor will be different but the rest of the interface remains the same LList.cpp that implements the class List_unittest.cpp add tests and modify to show that your bonus part works the Makefile that will compile and run your code (including the extra files for the memory management: fix the Makefile accordingly) test Llist.cpp that matches your class constructor from LList.h that tests your class and dumps the common array expand the tests to illustrate that the bonus part works Other files that implement the memory management You might want to add the flag -fsanitize-address to help you with possible memory errors; you might need to add the static-libasan flag too You are recommended NOT to use the data structures of Lab II. o Assignment #3: ADT List implemented as Linked Lists in an Array Assignment due with Brightspace at 11:50pm on Wednesday February 3 Read in the textbook chapters 1 (skip $1.3, 61.5), chapter 5 (skip $5.9) and chapter 3. The purpose of this assignment' 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 wel) 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 The following assignment is based on the Programming Problem #11 on page 245 in Data Abstraction and Problem Solving with C++: Walls and Mirrors by Frank M. Carrano, 5h Edition, Pearson Education, Inc., 2007. But it is different. 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 x's 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 Last.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. To submit as Assignment #3 a single compressed zip file a directory that contains o List.h (add YOUR code) oLList.cpp (add YOUR code) Llist_unittest.cpp (add more tests optionally: it will not be marked) Makefile (provided do not modify) test_LList.cpp (leave as is or add more code: it will not be marked but it should work with NDEBUG not defined so that we can see if your program is working) a README.txt if needed but if you did the bonus, indicate so in this README.txt a second directory with the bonus part a README.txt that explains the design of your memory management including how the constructor is to be called LList.h you can pass to the constructor of the LList an instance of a class that does the memory management: in such a case, the constructor will be different but the rest of the interface remains the same LList.cpp that implements the class List_unittest.cpp add tests and modify to show that your bonus part works the Makefile that will compile and run your code (including the extra files for the memory management: fix the Makefile accordingly) test Llist.cpp that matches your class constructor from LList.h that tests your class and dumps the common array expand the tests to illustrate that the bonus part works Other files that implement the memory management You might want to add the flag -fsanitize-address to help you with possible memory errors; you might need to add the static-libasan flag too You are recommended NOT to use the data structures of Lab II. o