Please read the instruction carefully and write the program in c++.
Chunklist Original Chunklist concept by Nick Parlante. Adapted to an assignment by Varick Erickson. 1 INTRODUCTION A Chunklist is like a regular linked list, except each node contains a little fixed size array of elements instead of just a single element. Each node also contains its own "size" int to know how full it is. The Chunklist will have the following features... The ChunkList object contains a head pointer to the first chunk, a tail pointer to the last chunk, and an int to track the logical size of the whole collection. When the size of the list is O, the head and tail pointers are null. head 16 next null next len len 8 next len values next len values values values Each chunk contains a fixed size ItemT [] array, an int to track how full the chunk is, and a next pointer. There should be a constant ARRAY_SIZE = 8 that defines the fixed size of the array of each chunk. Elements should be added to the array starting at its O index. Elements in each little array should be kept in a contiguous block starting at 0 (this will require shifting elements around in the little array at times). You may want to test ARRAY_SIZE set to smaller values, but turn it in with ARRAY_SIZE set to 8. Item T should be a separate class used in a similar manner as the examples given in class. The empty collection should be implemented as null head and tail pointers. Only allocate chunks when actually needed. Chunklist should implement the following methods: O Append(ItemT elem) o GetLength() (refers to the total number of elements, not the number of chunk nodes) o GetIndex(int i) (gets the item at index i) Contains(ItemT elem) o Print o Remove(ItemT elem) (removes first instance of elem) o IsEmpty The Append operation should add new elements at the end of the overall collection - i.e. new elements should go into the tail chunk. If the tail chunk is full, a new chunk should be added and become the new tail. We are not going to trouble ourselves shifting things around to use empty space in chunks in the middle of the list. The Remove operation should look through each chunk array until the target element is found. Since the Chunklist can potentially have duplicates of the same elements, Remove should just delete the first found instance of the element. If the chunk node is empty after removing the element, then the entire chunk should be removed from the link list. Keep a single "len" variable for the whole list that stores the total number of client data elements stored in the list. Similarly, keep a separate "len" variable in each chunk to know how full it is. Search should return true if the element if found. Otherwise it should return false. 2 TEST DRIVER You should have a test driver similar to the list drivers demonstrated in class. Much of this driver can be reused for testing your implementation of Chunklist. In particular, it should support the following commands: Append GetLength GetIndex Contains Print Remove IsEmpty IMPORTANT: Be sure to craft your input tests to ensure that your node removal works correctly. 3 QUESTIONS 1. What is the advantage of the Chunklist approach as opposed to a standard the link list implementation? 2. What would be the implications of increasing the size of ARRAY SIZE to a very large value? 3. What is the big o of: Append GetLength GetIndex Search Print Remove IsEmpty 4. Compare placing a new element into the FIRST available empty space versus placing a new element in the tail chunk. What are the advantages and disadvantages to automatically placing values at the tail node? 4 DELIVERABLES Your Chunklist class with comments for each of the methods Your test driver Input to the test driver demonstrating functionality The output file generated from the test driver Answers to the questions for part 3 Chunklist Original Chunklist concept by Nick Parlante. Adapted to an assignment by Varick Erickson. 1 INTRODUCTION A Chunklist is like a regular linked list, except each node contains a little fixed size array of elements instead of just a single element. Each node also contains its own "size" int to know how full it is. The Chunklist will have the following features... The ChunkList object contains a head pointer to the first chunk, a tail pointer to the last chunk, and an int to track the logical size of the whole collection. When the size of the list is O, the head and tail pointers are null. head 16 next null next len len 8 next len values next len values values values Each chunk contains a fixed size ItemT [] array, an int to track how full the chunk is, and a next pointer. There should be a constant ARRAY_SIZE = 8 that defines the fixed size of the array of each chunk. Elements should be added to the array starting at its O index. Elements in each little array should be kept in a contiguous block starting at 0 (this will require shifting elements around in the little array at times). You may want to test ARRAY_SIZE set to smaller values, but turn it in with ARRAY_SIZE set to 8. Item T should be a separate class used in a similar manner as the examples given in class. The empty collection should be implemented as null head and tail pointers. Only allocate chunks when actually needed. Chunklist should implement the following methods: O Append(ItemT elem) o GetLength() (refers to the total number of elements, not the number of chunk nodes) o GetIndex(int i) (gets the item at index i) Contains(ItemT elem) o Print o Remove(ItemT elem) (removes first instance of elem) o IsEmpty The Append operation should add new elements at the end of the overall collection - i.e. new elements should go into the tail chunk. If the tail chunk is full, a new chunk should be added and become the new tail. We are not going to trouble ourselves shifting things around to use empty space in chunks in the middle of the list. The Remove operation should look through each chunk array until the target element is found. Since the Chunklist can potentially have duplicates of the same elements, Remove should just delete the first found instance of the element. If the chunk node is empty after removing the element, then the entire chunk should be removed from the link list. Keep a single "len" variable for the whole list that stores the total number of client data elements stored in the list. Similarly, keep a separate "len" variable in each chunk to know how full it is. Search should return true if the element if found. Otherwise it should return false. 2 TEST DRIVER You should have a test driver similar to the list drivers demonstrated in class. Much of this driver can be reused for testing your implementation of Chunklist. In particular, it should support the following commands: Append GetLength GetIndex Contains Print Remove IsEmpty IMPORTANT: Be sure to craft your input tests to ensure that your node removal works correctly. 3 QUESTIONS 1. What is the advantage of the Chunklist approach as opposed to a standard the link list implementation? 2. What would be the implications of increasing the size of ARRAY SIZE to a very large value? 3. What is the big o of: Append GetLength GetIndex Search Print Remove IsEmpty 4. Compare placing a new element into the FIRST available empty space versus placing a new element in the tail chunk. What are the advantages and disadvantages to automatically placing values at the tail node? 4 DELIVERABLES Your Chunklist class with comments for each of the methods Your test driver Input to the test driver demonstrating functionality The output file generated from the test driver Answers to the questions for part 3
