Question

queues can be modeled as arrays or linked lists. describe the advantages and disadvantages of doing this. Focus on the operations permitted, time and space restrictions etc. Draw diagrams if necessary.

Answer 1

If the queue is implemented using array, the the time taken to enqueue an element is O(1) which is advantage. Also, the space taken is O(n) where n is the initial size of the array. Also, each time the array is completely filled, then we need to create an array of double the size and copy all the elements into the new array. So, the space is left extra and the time taken to copy the array is also O(n) which is a disadvantage. Also, the time taken to dequeue also takes O(1).

If queue is implemented using linked list, the the enqueue and dequeue take O(1) time as we have the front and tail pointer. So, we just need to adjust the pointers to insert a new element and remove an element. Also, there is no need to create a new list of double the size and copy the elements as the size of a list is infinite. Also, unlike array, no extra memory is used like in array a big part of the array is empty. That is not the case in linked list.