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...
-
AI Shalou, a single individual, had only $14,000 of salary income in 2013, but he had a number of property transactions during the year with the following results: a. $26,000 Section 1202 gain on ABC...
-
Tannin Products Factory Overhead Cost Variance Report-Trim Department For the Month Ended July 31 Line Item Description Variable factory overhead costs: Indirect factory labor Power and light...
-
The CEO of Evans \& Sons, Inc., was considering a lease for a new administrative headquarters building. The building was old, but was very well located near the company's principal customers. The...
-
Briefly discuss Harrahs marketing information system, using Figure as a guide. Joseph, a 30-something New Yorker, recently went on a weekend trip to Atlantic City, New Jersey, where he hoped to stay...
-
The Securities and Exchange Commission (SEC) allows purchasers of __________ securities to resell the securities and not be deemed __________. Question 38 options: restricted; underwriters...
-
Telstar uses job order costing. The T-accounts below summarize its production activity for the year. 1. Compute the amount for each of the following. a. Direct materials used b. Indirect materials...
-
Jim and Cherie are at the top of the 22% tax bracket and have astate tax rate of 7% and payroll taxes of 7.65%. They spend $5,000 out-of-pocket for healthcare for their son. Jim and Cherie are...
-
Transverse waves with a speed of 59.5 m/s are to be produced on a stretched string. A 5.85 m length of string with a total mass of 0.0600 kg is used. (a) What is the required tension in the string? N...
-
An isolated conductor of arbitrary shape has a net charge of +9.00x106 C. Inside the conductor is a cavity within which is a point charge q +3.15x106 C. = What is the charge on the cavity wall?...
-
An investor web page claims thatearnings per share is the bestmeasure of a share's true price because it shows you how much of a company's profit after tax that each shareholder owns. Look up the...
-
Who are the stakeholders? What does each stakeholder want? What resources do they contribute to the organization? What claims are they likely to make on the organization?
-
A 2 0 kg object is pulled to the right with a force of 3 8 0 N at an angle of 4 5 degree above the horizontal. It is also being pulled to the left wiht a force of 3 4 0 N at an angle of 2 5 degree...
-
Currently, Fire Station 51 and Fire Station 81 operate separate EMS trucks. Station 51 has operating costs of $46600 per year. Station 81 reports operating cost of $42400 per year. Station 51...
-
In Exercises 15 through 30, find the derivative dy/dx. In some of these problems, you may need to use implicit differentiation or logarithmic differentiation. y ex + et -2x 1 + e
-
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...
-
Which of the following areas illustrates positive network externalities? a. Telephones b. Software c. The Internet d. All of the above
-
Oligopolies exist when only a(n) _________ firms control all or most of the production and sale of a product.
-
What is a Nash equilibrium?
Study smarter with the SolutionInn App