0
What are the advantages and disadvantages of the linked implementation of a queue relative to the contiguous implementation?
Wiki User
∙ 10y ago
Contiguous implementation (e.g., using an array), has a major disadvantage in that you have to allocate enough space in the array to hold all the elements in the queue. When there is insufficient space, you have to re-allocate, which may occasionally require the entire array be copied to new memory. In addition, with each extraction, you are left with unused memory at the start of the array. Thus before any re-allocation, you must first check if there are unused elements and then shunt all elements forward, thus creating space at the end of the array.
If we ignore the shunting and re-allocations necessary with an array, insertions and extractions will occur in constant time for both contiguous and linked implementations. However, once you take shunting and re-allocation into account, we find that contiguous implementations occasionally falter during an insertion.
Contiguous implementations also require more memory than linked implementations. Although a linked node is larger than an array element by one pointer (32 bits on a 32-bit system), contiguous implementations must allocate far more memory than is actually required in order to minimise the number of re-allocations. Thus an array must always have unused elements. Moreover, when all elements are extracted from the queue, the current allocation remains in memory. With linked implementations, the only memory allocated is the memory actually in use at any given moment, with the minimum memory requirement being just one pointer, to the tail node.
An optimal queue implementation will use a circular linked list, where only the tail node need be maintained by the list object. The tail's next node always points to the head node, so there is no need to maintain this separately.
The only real disadvantage of a linked implementation is the need to allocate and deallocate memory for each insertion and extraction respectively. However, this is a constant time operation. With contiguous implementation, only extraction is guaranteed to be a constant time operation. Most of the time, insertions will be constant time, but will occasionally take variable time due to the need to shunt or re-allocate.
Wiki User
∙ 10y ago
Add your answer:
Earn +20 pts
What are the advantages and disadvantages of the rise and fall method in surveying?
1, describe the methode of reducing the levels and thier relative advantages and disadvantages 2, writetypes of levelling instruments and methodes of leveling
Advantages and disadvantages of using employee referral campaign recruitment?
· Employee referrals:o Advantages: choosing a person that you know well (character, qualifications etc), save cost & time vs advertisement.o Disadvantages: if person is not suitable (qualifications, experience, character etc) but is merely a friend/relative (nepotism) of the current employee. Favoritisms, potential request for unreasonable favor in return.
What is contiguous memory in c plus plus?
Contiguous memory refers to a single block of consecutive memory addresses. All data types larger than a char require contiguous memory addresses. For any given data type T, sizeof (T) tells us how many bytes of contiguous memory will be allocated to an object of that type: std::cout << "sizeof (char) == " << sizeof (char) << std::endl; std::cout << "sizeof (int) == " << sizeof (int) << std::endl; std::cout << "sizeof (double) == " << sizeof (double) << std::endl; struct X {/* ... */}; std::cout << "sizeof (X) == " << sizeof (X) << std::endl; When we speak of contiguous memory, we don't usually refer to the number of bytes allocated to a given type; it can be taken as read that those bytes will be allocated contiguously such that the low-order byte refers to the whole object, regardless of its length. Typically we use the term contiguous memory when referring to an array of objects. All objects in an array (the array elements) are exactly the same length (in bytes) and because they are allocated contiguously it is trivial to calculate the offset address of any one element relative to any other element in the same array. This is precisely how the array suffix operator works using only a zero-based index; the operator is nothing more than a convenient method of implementing pointer arithmetic. The upshot is that all arrays permit constant-time random access to any element in the array. Arrays are dense data structures. That is, there is no additional memory required to maintain the structure. The only information we need to keep track of is the start address and the number of elements. However, the downside of contiguous memory allocations is that whenever we wish to increase the amount of memory allocated we often have to move the entire allocation to new memory. The larger the allocation the more costly this becomes. Moreover, inserting new data means we must move elements to make room. This is why variable-length arrays typically reserve additional memory for moderate expansion while new elements are always pushed onto the end of the array rather than inserted in the middle. Linked-lists are non-contiguous data structures which make use of additional memory to maintain links between the elements. As such, the elements need not move once allocated. If we want to change the element sequence or insert a new element into the sequence we simply update the affected links; the elements themselves remain wherever they were originally allocated. Some data structures make use of both contiguous and non-contiguous allocations. A deque (a double-ended queue, pronounced deck) is a typical example because it is usually implemented as a linked-list of separate arrays. Each array is contiguous but the list of arrays is not necessarily contiguous.
What is meant by relative size when choosing a font size?
Relative size is an option in the style tab. It means that the size should be relative or correspond to the others.
Why is relative velocity AFTER equal to Vf2 minus Vf1 but relative velocity BEFORE equal to V1 minus V2 in the coefficient of restitution formula?
relative velocity is defined as the time rate of change of one object with respect to another object.the relative velocity depends upon the observer i.e.if the velocities of two objects are same then the relative velocity also seems to be equal.
What are the advantages and disadvantages of the rise and fall method in surveying?
1, describe the methode of reducing the levels and thier relative advantages and disadvantages 2, writetypes of levelling instruments and methodes of leveling
What are the relative advantages and disadvantages of formal and informal communication networks?
disadvantage formal communicative network
What is seattle relative location?
It is in the northwest corner of the contiguous United States.
What is Seattle Washington's relative location?
It is in the northwest corner of the contiguous United States.
What are som advantages and disadvantages of a mercator projection and of an equal area projection?
advantages: correctly shows the relative sizes of Earth's landmasses disadvantages: has distortion shows the landmasses near the edges stretched and curved
What are the dis advantages of Coral reefs?
There are no disadvantages to coral reef because, animals live with and if there was problem they would just have to die cause its everywhere
The advantages and disadvantages of Relative Dating Methods?
Relative dating methods provide a chronological framework by determining the relative order of artifacts or events, making it useful for understanding the sequence of geological and archaeological events. However, they do not provide specific ages and rely on the principle of superposition, which may not always accurately reflect the true chronological order. Furthermore, relative dating methods are unable to provide precise dates, making it challenging to compare events across different regions.
What are the relative advantages and disadvantages of the gravity dams over earth dams?
Advantage of a gravity dam is that every section will be stable and reliable. An Earth dam can overflow and collapse because of erosion.
How do you use contiguous in a sentence?
The contiguous United States does not include Alaska and Hawaii. Contiguous means adjacent; touching; right next to; consecutive; sequential; or close together, but not touching. Contiguous events are adjacent in time. Contiguous memory locations are right next to each other in address space, as in (3), (4), (5). In computer terminology, contiguous is sometimes distinguished from consecutive or continuous, because 'continuous' or 'consecutive' could apply in absolute addressing, but possibly may not apply in virtual space or relative [indirect] addressing.
What are the relative advantages and disadvantages of internal CD burner and external CD burner?
An external drive will be a little slower because of the speed differences between SATA (internal) and USB (external). The obvious advantage to an external is changeability, ease of access, etc.
What are the major advantages and disadvantages of using petrol in internal combustion engines?
Some of the major advantages of using petrol in an internal combustion engine include: ease of availability of petrol, non-corrosive nature of regular petrol, relative safety of liquefied petrol. Some of the disadvantages of petrol include: enviromental damage of unburned petrol and unrestrained Hydrocarbon emissions, steadily increasing price, petrol is relatively inefficient and production of CO2 even with perfect combustion.
The advantages of the scientific method in psychology?
its clarity and precision. its relative intolerance of error
