A Chunklist is like a regular linked list, except each node contains a little fixed size...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
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 0, the head and tail pointers are null. head tail size 16 next next * next next null size size e 1 size 2 size 5 values 4 values 9 values 10 values 2 2 12 7 5 4 -1 2 8 Each chunk contains a fixed size ItemType[] 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: o MakeEmpty isFull > (refers to the entire list, not an individual chunk node) Getlength > (refers to the total number of element, not the number of chunk nodes) Getltem Putltem Deleteltem o Resetlist o GetNextitem • 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 Deleteltem operation should look through each chunk array until the target element is found. Since the ChunkList can potentially have duplicates of the same elements, Deleteltem 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. 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 0, the head and tail pointers are null. head tail size 16 next next * next next null size size e 1 size 2 size 5 values 4 values 9 values 10 values 2 2 12 7 5 4 -1 2 8 Each chunk contains a fixed size ItemType[] 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: o MakeEmpty isFull > (refers to the entire list, not an individual chunk node) Getlength > (refers to the total number of element, not the number of chunk nodes) Getltem Putltem Deleteltem o Resetlist o GetNextitem • 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 Deleteltem operation should look through each chunk array until the target element is found. Since the ChunkList can potentially have duplicates of the same elements, Deleteltem 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.
Expert Answer:
Answer rating: 100% (QA)
Hi Buddy Because youre going to be able to create as a class and you didnt mention which language you want to use I am using the code to create the class of ChunkList Dont worry if you dont know what ... View the full answer
Related Book For
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
Posted Date:
Students also viewed these programming questions
-
A laser pointer is kept at a constant and fixed height above the floor, but it can move horizontally back and forth in a straight line. A mirror is placed on a platform at a fixed distance from a...
-
A linked list contains a cycle if, starting from some node p, following a sufficient number of next links brings us back to node p. p does not have to be the first node in the list. Assume that you...
-
When an object moves with constant velocity, does its average velocity during any time interval differ from its instantaneous velocity at any instant?
-
Write an HTML document to create a form that collects favorite popular songs, including the name of the song, the composer, and the performing artist or group. This document must call one PHP script...
-
Computer Corp. reinvests 60% of its earnings in the firm. The stock sells for $50, and the next dividend will be $2.50 per share. The discount rate is 15%. What is the rate of return on the company's...
-
Facts: Chelsea Chaney was a seventeen-year-old high school student in Fayette County, Georgia. At a county-wide Internet safety seminar, Curtis Cearley, the Districts technology director, presented a...
-
What are the different types of schemes associated with complex frauds?
-
As loan analyst for Utrillo Bank, you have been presented the following information. Each of these companies has requested a loan of $50,000 for 6 months with no collateral offered. Because your bank...
-
choose the closest answer find the annual total cost of inventory. if the company using their present lot size do not use the EOQ be sure to use the present lot size . unit cost$5, ordering cost...
-
For the network of Fig. 7.86, determine: a. VGSQ and IDQ b. VDS, VD, VC and VS. 12 V 22 kQ Gso 1 1.6 k FIG. 7.86
-
Sydney Ltd repaired a customers' washing machine and charged the customer $500 which the customer paid immediately. The general journal entry to record the transaction is: a.Debit Cash at bank $500;...
-
An apartment building was recently sold for $3,650,000. The County Assessor has determined that the building's value is allocated with 36% land value. What is the annual allowable tax shelter from...
-
Onyx Healthcare is a renowned primary provider of private healthcare services in Malaysia. Onyx Healthcare provides medical specialist services from their multiple hospitals throughout Malaysia. Due...
-
2: Find the equation of the plane a) Passing through the point (1,1,3) and having the normal vector = (0, 2, 3) b) Passing through the three points(1,-1,3), (0,5,1) and (-2,-3,-1). c) Passing...
-
Given the following grammar: SWAB|ABCS B|WB Ely B A B .CZ W What are the FIRST and FOLLOW sets?
-
CS161 Introduction to Computer Science II Implementation Requirements The following class relationship diagram shows the required classes and how they interact. BlackjackTableGUI Extends Application...
-
Discuss in detail what the company does to achieve each of the "effects" in the Wheel of Social Media Engagement. Be specific, use examples, and cite your sources (using APA format). elacemater
-
Write each fraction as a percent. 7 50
-
Show how to modify the topological sort algorithm so that if the graph is not acyclic, the algorithm will print out some cycle. You may not use depth-first search.
-
In the analysis of mergesort, constants have been disregarded. Prove that the number of comparisons used in the worst case by mergesort is N[log N] - 2[logN] + 1.
-
The longest increasing subsequence problem is as follows: Given numbers a1, a2, . . . , aN, find the maximum value of k such that ai1 < ai2 < < aik, and i1 < i2 < < ik. As an example, if the...
-
In a(n)________ numbering system, all numeric values are written as sequences of 0s and 1s. a. hexadecimal b. binary c. octal d. decimal
-
What is a program?
-
List the five major components of a computer system.
Study smarter with the SolutionInn App