0
What are the merits and demerits of array based implementation over linked implementation?
Wiki User
∙ 11y ago
The merits of an array are that it provides the most compact storage mechanism of any data container, and enables constant-time, random access to that data.
The demerits are that insertions and extractions can be costly in terms of performance due to the need to copy/move elements within the array. For large arrays, the cost can become prohibitive. Also, arrays can only be used to store elements of the same type.
Wiki User
∙ 8y ago
Wiki User
∙ 11y agoArray-based lists are far faster to access (pro), but must be resized each time they exceed their bounds (con).
Linked-list lists are slower to access (con), but can grow to consume all available space without having to be resized (pro).
Array-based lists consume less memory per element (pro), but have to be copied/moved completely each time the list grows larger (con).
Linked-list lists consume more memory per element (con), but never need to be copied or moved during a resize (pro).
Array-based lists can exceed their bounds (con), while linked-list lists can introduce memory leaks and dangling/null pointers if there are programming bugs (con).
Array-based lists must move ALL elements after the insertion or deletion point each time an insert or deletion is required (con).
Linked-list lists only have to remove a single element and update at most two neighbors (pro).
Array-based lists must have their elements sorted in memory, requiring many additional reads and writes (con).
Linked-list implementations can sort their data without moving a single element simply by changing pointers around (pro).
Array-based lists are inherently faster to copy (pro), while linked-list lists must be copied one element at a time (con).
Overall, an array-based list is desirable if the linked-list memory overhead is undesirable (e.g. there are many elements, such as a string), and if resizing is fairly uncommon. Linked-list implementations are well suited for smaller lists that are constantly being inserted and removed at various splice points, and when iterating over the entire list is not particularly disadvantageous. Sorting a linked list of complex objects is trivially faster than an array-based list, unless the array is simply an array of pointers, in which case that advantage is largely irrelevant. Both memory structures are useful, and it is important to know when to use each.
Add your answer:
Earn +20 pts
Would there be any Memory issues or execution issues or any merits or demerits of using 1D array of size 'mn' instead of using 2D array of size mxn?
It requires the same amount of memory, so it wouldn't spare anything. Don't do it.
What are the disadvantage of array implementation of stack?
Some immediate disadvantages:You'll have dead space in the array (entries which aren't currently used for items) taking up memoryYou'll have to keep track of the free entries - after a few insertions and deletions, these free entries could be anywhere.Using an array will impose an upper limit on the size of the linked list.
What are the advantages and disadvantages of the linked implementation of a queue relative to the contiguous implementation?
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.
Array implementation of priority queue example program in c plus plus?
yes
Is it true or false that a dynamically linked list can be accessed both sequentially and randomly?
No. Linked lists require traversal, and are therefore accessed sequentially. For random access you need an array. An array of pointers to the data in your list would do, but you will incur an overhead in creating the array on top of the list.
Would there be any Memory issues or execution issues or any merits or demerits of using 1D array of size 'mn' instead of using 2D array of size mxn?
It requires the same amount of memory, so it wouldn't spare anything. Don't do it.
Can a linked list implemented using an array be accessed by giving the location?
A linked list implemented with an array defeats the purpose of using a linked list, which is to address the memory allocation problems associated with arrays.
What are the disadvantage of array implementation of stack?
Some immediate disadvantages:You'll have dead space in the array (entries which aren't currently used for items) taking up memoryYou'll have to keep track of the free entries - after a few insertions and deletions, these free entries could be anywhere.Using an array will impose an upper limit on the size of the linked list.
What are the advantages and disadvantages of the linked implementation of a queue relative to the contiguous implementation?
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.
Can you simulate linked list using arrays?
I would say no, but it really depends on your point of view. An array and a linked list can both hold the same data; the only difference is how they do so. The definition of a linked list is a sequence of connected nodes. An array is a contiguous block of memory, so you can think of an array as a linked list in which each element is spacially connected to the next.
Array implementation of priority queue example program in c plus plus?
yes
Can linked list represent in array if yes show how insertion and deletions can perform in array representation of inked list?
yes
What is the Java program for sorting an array?
Java has a very efficient built in implementation of quick sort. You can use it on any array of primitives or Comparable Objects by invoking Arrays.sort(<array>) See related link.
What is a implementation on n numbers of term in bubble sorting?
void bubblesort (int* array, int size) { if (!array size<2) return; int last_swap = size; while (last_swap>0) { int n=last_swap; for (int i=1; i<last_swap; ++i) { if (array[i]<array[i-1]) { array[i]^=array[i-1]^=array[i]^=array[i-1]; n=i; } last_swap = n; } }
Is it true or false that a dynamically linked list can be accessed both sequentially and randomly?
No. Linked lists require traversal, and are therefore accessed sequentially. For random access you need an array. An array of pointers to the data in your list would do, but you will incur an overhead in creating the array on top of the list.
What are the the two ways in representing the stack?
one-dimensional array, and doubly-linked list.
C program to implement tower of hanoi using array implementation of stack abstract datatype?
stack abstract datatype
