Chuncklist C++ Assignment
A ChunkList is like a regular linked list, except each nodecontains a little fixed size array of elements instead of just asingle element. Each node also contains its own “size” int to knowhow full it is. The ChunkList will have the followingfeatures…
• The ChunkList object contains a head pointer to the firstchunk, a tail pointer to the last chunk, and an int to track thelogical size of the whole collection. When the size of the list is0, the head and tail pointers are null.
Each chunk contains a fixed size ItemT [] array, an int to trackhow full the chunk is, and a next pointer. There should be aconstant ARRAY_SIZE = 8 that defines the fixed size of the array ofeach chunk. Elements should be added to the array starting at its 0index. Elements in each little array should be kept in a contiguousblock starting at 0 (this will require shifting elements around inthe little array at times). You may want to test ARRAY_SIZE set tosmaller values, but turn it in with ARRAY_SIZE set to 8.
• The empty collection should be implemented as null head andtail pointers. Only allocate chunks when actually needed.
• ChunkList should implement the following methods: oAppend(ItemT elem) o GetLength() → (refers to the total number ofelements, not the number of chunk nodes) o GetIndex(int i) → (getsthe item at index i) o Search(ItemT elem) o Print o Remove(ItemTelem) → (removes first instance of elem) o IsEmpty
• The Append operation should add new elements at the end of theoverall collection – i.e. new elements should go into the tailchunk. If the tail chunk is full, a new chunk should be added andbecome the new tail. We are not going to trouble ourselves shiftingthings around to use empty space in chunks in the middle of thelist.
• The Remove operation should look through each chunk arrayuntil the target element is found. Since the ChunkList canpotentially have duplicates of the same elements, Remove shouldjust delete the first found instance of the element. If the chunknode is empty after removing the element, then the entire chunkshould be removed from the link list. • Do not use a dummy nodebecause (a) it does not help the code much, and (b) dummy nodes arelame.
• Keep a single “len” variable for the whole list that storesthe total number of client data elements stored in the list.Similarly, keep a separate “len” variable in each chunk to know howfull it is.
• Search should return a copy of the element if found. Otherwiseit should return null.
You should have a test driver similar to the list driverdemonstrated in class. Much of this driver can be reused fortesting your implementation of ChunkList. In particular, it shouldsupport the following commands:
• Append
• GetLength
• GetIndex
• Search
• Remove
• IsEmpty I
MPORTANT: Be sure to craft your input tests to ensure that yournode removal works correctly.
Turn IN:
•Your ChunkList template class with comments for each ofthe methods
• Your test driver
• Input to the test driver demonstratingfunctionality
• The output file generated from the testdriver
head len 16 next next next len values next len values len 19 len values values Show transcribed image text head len 16 next next next len values next len values len 19 len values values
Expert Answer
Answer to Chuncklist C++ Assignment A ChunkList is like a regular linked list, except each node contains a little fixed size array…