How to create chuncklist class with the above methods. A ChunkList is like a reg

ID: 3785661 • Letter: H

Question

How to create chuncklist class with the above methods.

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 Chunk List 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 0, the head and tail pointers are null. Each chunk contains a fixed size item Type[] 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 0 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. The empty collection should be implemented as null head and tail pointers. Only allocate chunks when actually needed. ChunkList should implement the following methods similar to those describe on pages 136-138: Make Empty isFull rightarrow (refers to the entire list, not an individual chunk node) GetLength rightarrow (refers to the total number of element, not the number of chunk nodes) Getltem Putltem Deleteltem ResetList GetNextltem The Putltem operation should add new elements at the end of the overall collection -i.e. new elements should always 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. We'll only look at the tail chunk. The DeleteItem operation should look through each chunk array until the target element is found. Since the ChunkList can potentially have duplicates of the same elements, DeleteItem 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. Do not use a dummy node because (a) it does not help the code much, and (b) dummy nodes are lame. Keep a single "size" variable for the whole list that stores the total number of client data elements stored in the list. Similarly, keep a separate size in each chunk to know how full it is

Explanation / Answer

Hi Buddy, Since you asked to create a class and you didn't mention which language to use, I'm using java to create the class 'ChunkList'. Don't worry if you don't know java. I've used comments for better understanding. I would suggest you to copy all the answer in a single notepad file for better readability. I've also given the completely implemented code in java.

I have few confusions regarding the question and I've made some assumptions and I've clearly stated my assumptions for your better understanding. This was not so easy to solve in 2hrs, but I tried my best to implement all operations

This is the class ChunkList. This class implements a method 'deleteItemFromChunk'. This method deletes the element from the chunk and return the position of the element in the CHUNK if the element is found or returns -1, If the element is not found

//This method Empties the chunk
void emptyChunk(){
//Resets the elements in the array to zero
for(int i=0;i<size;i++){
item[i] = 0;
}
//change the size of the CHUNK to zero
size = 0;
}

}

1. Make Empty Operation

   This operation is a bit unclear. So, I've implemented in 2 ways
   a. Make Empty The Whole CHUNK LIST by keeping the CHUNKS
   b. Make Empty The Whole CHUNK LIST by removing all the CHUNKS
   Please find the 2 methods MakeEmptyButKeepChunks and MakeEmptyAndRemoveAllChunks in the ChunkList class

2. IsFull
   I understood that I've to check whether all the elements in the CHUNK are filled completely. Please find the method isFull in ChunkList class

3. GetLength
   I understood that I've to return count of the elements in the CHUNK LIST. Since we are keeping track of all the elements while adding an element and removing elements, the variable
   SIZE returns the count of elements in the ChunkList class. Please find the getLength method in the ChunkList class

4. GetItem
   I didn't understand what this method was supposed to do. I've implemented this method to return the first CHUNK in which the element is found or this method returns null if no element is found. Please find getItem Method in the ChunkList class

5. PutItem
   Please find putItem method in the ChunkList class

6. DeleteItem
   Please find deleteItem method in the ChunkList class

7. ResetList
   I was unclear about what this method was supposed to do. So, I've implemented this method in the same way as I implemented 1.b Please find resetList method in ChunkList class

8. GetNextItem
   Question doesn't talk clearly about what this operation is supposed to do either. So, I've implemented this method to return the immediate next element in the CHUNK LIST and it returns -1, If no valid next element exists. (Either the element is not found or the Element is found at the end of the CHUNK LIST). Please find getNextItem method in the ChunkList class



   This is the complete java program


   /******************************************************************************************************************************************************************************/

package chunklist;

import java.io.IOException;
import java.util.Scanner;

class Chunk{
// This is the maximum size of the CHUNK
final int ARRAY_SIZE = 8;

// This indicates how full our CHUNK is
int size = 0;

// This is the array that stores the data
int item[] = new int[ARRAY_SIZE];

//This node stores the next chunk
Chunk next;

//This method searches and deletes the first occurance of an element in this CHUNK and returns the index of the
//first occurance or returns -1, if the element is not found in this CHUNK
int deleteItemFromChunk(int e){
//This element stores the position of the element we are searching for
int pos = -1;
//Iterating through all the elements in the CHUNK
for(int i=0;i<size;i++){
//Condition to check the element
if(item[i]==e){
//element found at position 'pos'
pos = i;
break;
}
}
//This means element is not found in this CHUNK
if(pos==-1){
return -1;
}
//This means element is found in this CHUNK
else{
//Now element is found at position 'pos'. We have to shift the elements in the chunk
for(int i=pos;i<size;i++){
//We are moving the next element to the present position to fill in the gap formed by removing element
//at pos
item[i] = item[i+1];
}
//After that we have to reduce the size of the item array
size = size-1;
}
return pos;
}

//This method Empties the chunk
void emptyChunk(){
//Resets the elements in the array to zero
for(int i=0;i<size;i++){
item[i] = 0;
}
//change the size of the CHUNK to zero
size = 0;
}
}
public class ChunkList {

static Chunk head,tail;
static int SIZE = 0;

//This method empties CHUNK LIST but still keeps the CHUNKS
static void makeEmptyButKeepChunks(){
Chunk temp = head;
while(temp != null){
//This method empties the CHUNK and resets the array. Please go through this method
temp.emptyChunk();
temp = temp.next;
}
//Change the size of the whole CHUNK LIST to 0
SIZE = 0;
}

//This method removes all the CHUNKS
static void makeEmptyAndRemoveAllChunks(){
head = null;
tail = null;
//Change the size of whole CHUNK LIST to 0
SIZE = 0;
}

//This method returns whether all the CHUNKS in the CHUNK LIST are full or not
static boolean isFull(){
boolean full = true;
//Start with head CHUNK
Chunk temp = head;
while(temp!=null){
//Check if the CHUNK is not full
if(temp.size!=temp.ARRAY_SIZE){
full = false;
break;
}
//Move to the next CHUNK
temp = temp.next;
}
return full;
}

//This method resets the CHUNK LIST by removing all the CHUNKS
static void resetList(){
head = null;
tail = null;
//Change the size of whole CHUNK LIST to 0
SIZE = 0;
}


//this method to return the immediate next element in the CHUNK LIST and
// it returns -1, If no valid next element exists
static int getNextItem(int x){
//Start with head
Chunk temp = head;
//Iterate through all the CHUNKS in the CHUNK LIST
while(temp!=null){
//Iteraing through all the elements in the CHUNK
for(int i=0;i<temp.size;i++){
//If the elemet is found at position i
if(temp.item[i]==x){
//If element is not found at the end of the CHUNK, return the immediate next element
if(i!=temp.size-1){
return temp.item[i+1];
}
//If not , loop through all the remaining CHUNKS and return the first valid element
int ans = -1;
//Start looping from the current CHUNK
Chunk temp2 = temp.next;
//Loop through all the remaining CHUNKS
while(temp2!=null){
//Return the first element in the non empty CHUNK
if(temp2.size!=0){
return temp2.item[0];
}
//Move to the next CHUNK
temp2 = temp2.next;
}
return ans;
}
}
//Move to the next CHUNK
temp = temp.next;
}
return -1;
}

static int getLength(){
return SIZE;
}

//This method returns the first CHUNK which contains the element x or return null if the element is not found
static Chunk getItem(int x){
//Start with head
Chunk temp = head;
//Iterate through all the CHUNKS in the CHUNK LIST
while(temp!=null){
for(int i=0;i<temp.size;i++){
if(temp.item[i]==x){
return temp;
}
}
//Move to the next CHUNK
temp = temp.next;
}
return null;
}


//This method adds a new item to the tail CHUNK.
static void putItem(int x){
//The CHUNK LIST is empty.
if(head==null&&tail==null){
//Create a new head CHUNK and both head and tail point to the same CHUNK
head = new Chunk();
tail = head;
}
//If the tail CHUNK is full, create a new CHUNK and add it to the tail and make it the new tail.
if(tail.size==tail.ARRAY_SIZE){
//Creating a new CHUNK
Chunk temp = new Chunk();
//Setting the next element of the tail to the new CHUNK;
tail.next = temp;
temp.next = null;
//Making the new CHUNK as the new Tail
tail = temp;
}
//Add a new element to the tail
tail.item[tail.size] = x;
//Increase the size of the tail by one
tail.size = tail.size + 1;
//Increase the size of the whole collection by one
SIZE++;

}

//This method deletes the first occurance of element 'x' in the CHUNK LIST
static void deleteItem(int x){
//This means that the CHUNK LIST is empty
if(head==null&&tail==null){
return;
}
Chunk temp = head;
Chunk prev = null;
while(temp!=null){
//deleteItem method in the CHUNK searches and deletes the element from the CHUNK if found and returns -1
//if that element is not found
int d = temp.deleteItemFromChunk(x);
//This means that the element has been successfully deleted from the CHUNK
if(d!=-1){
//Now we have to check if this CHUNK is empty after deleting the element. If the CHUNK is empty, we have
//to remove it from the CHUNK LIST
if(temp.size==0){
//If this CHUNK is the head, remove the head and move the head to the next CHUNK
if(temp==head){
head = temp.next;
//If the new head is null, then tail should also be null
if(head==null){
tail = null;
}
}
//If this CHUNK is the tail, remove the tail and move the tail to the previous CHUNK
else if(temp==tail){
tail = prev;
}
//Set the next node of the previous CHUNK to the next element of the current CHUNK
else{
prev.next = temp.next;
}
}
//Delete the size of the whole list by one
SIZE = SIZE-1;

//Since the element has been found, break from the loop.
break;
}
//If the element is not found in the current CHUNK, move to the next CHUNK, and make the Current CHUNK as the 'prev'
prev = temp;
temp = temp.next;

}
}

public static void main(String[] args) throws IOException{
// Initially head and tail are null. That means our CHUNK LIST is empty
head = tail = null;
//You can call all the methods from here. This is the starting point of the program

//Object for reading input
Scanner obj = new Scanner(System.in);
int choice = obj.nextInt();

switch (choice){
//Make Empty. You can comment out a method based on your requirement
case 1:
makeEmptyButKeepChunks();
makeEmptyAndRemoveAllChunks();
break;
//Is Full
case 2:
System.out.println("Chunk List is Full "+isFull());
break;
//Get Length
case 3:
System.out.println("Length of the Chunk List is "+getLength());
break;
//Get Item
case 4:
System.out.println("Please enter the item");
int item = obj.nextInt();
System.out.println("Chunk is "+getItem(item));
break;
//Put item
case 5:
System.out.println("Enter the item to be put to the Chunk List");
int item2 = obj.nextInt();
putItem(item2);
break;
//Delete item
case 6:
System.out.println("Enter the item to be deleted from the Chunk List");
int item3 = obj.nextInt();
deleteItem(item3);
break;
//Reset the Chunk List
case 7:
System.out.println("Resetting the chunk list");
resetList();
break;
case 9:
break;
}
}
}

/******************************************************************************************************************************************************************************/

Navigate

How to create a program that simulates an MP3 player: Your program should begin

How to create magic square like this picture in C# windows form? I already have

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

How to create chuncklist class with the above methods. A ChunkList is like a reg

Question

Explanation / Answer

Related Questions

Navigate