The Gateway to Computer Science Excellence
+21 votes
2.7k views

Consider the following statements:

  1. First-in-first out types of computations are efficiently supported by STACKS.

  2. Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.

  3. Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.

  4. Last-in-first-out type of computations are efficiently supported by QUEUES.

  1. $(ii)$ and $(iii)$ are true
  2. $(i)$ and $(ii)$ are true
  3. $(iii)$ and $(iv)$ are true
  4. $(ii)$ and $(iv)$ are true
in DS by Veteran (52.2k points)
edited by | 2.7k views
+2

This might help....

0
reason of 3rd is we do not waste space in  circular array

4 Answers

+25 votes
Best answer
by Boss (19.9k points)
edited by
0

please tell me the concept behind point no. 2( array & L.L).

for list I've assumed 3 basic operation - Search, Insertion, Deletion

Array

Insertion will take O(n) time because here worst case is the insertion before the 1st element of array causing shifting of n elements. or when the existing list is full & we're going to add more element then the approach is to make an array of double size of the existing array & copy all elements in the new array then insert.

Deletion will take O(n) time because for same reason(shifting).

search will take O(n) time in worst case generally.

Linked List

Inserting an element into L.L will take O(n) time as we've to traverse all the way from head to last node.

Deletion will take O(n) time.

Search will take O(n) time.

So, where is the efficiency???

 

0
If you consider update, then array can update element at given index with O(1), whereas list can do it in O(n). So arrays are in fact faster than lists. If you add to this pointer management overhead and optimization possible with accessing successive memory locations in array, then I believe arrays are definitely faster than lists at CRUD. I too need confirmation.
0

@  I'm getting a doubt that for updating 1st we've to search the value which will be updated,then searching an element in array is O(n) & then O(1) for updating, isn't it?????

0

@Raj Singh 1 how will you know the size of list in advance? It will grow/shrink according to need right? Array is not useful in such case. Your comment is right but what is the use if basic work is not being done and going for optimization. :)

+10 votes

Answer : (A)

Corrections :

First-in-first out types of computations are efficiently supported by QUEUES.

Last-in-first-out type of computations are efficiently supported by STACKS

by Junior (911 points)
0

First-in-first out types of computations are efficiently supported by STACKS.

https://gateoverflow.in/734/gate2001-2-16 

it is given stacks and not a single stack.

+7
Hello shefali

statement is not false cause of stack/stacks , it's false because of word 'efficiently'.Stack efficiently support LIFO type of computations not FIFO.
+6 votes
A) Wrong stack is used for implementation of LIFO order

B) true provided list is dynamic in nature, for static list both will have same performance

C) can be true if we implementation circular queue using 2 pointer, else no advantage

D) false, queue is used to support FIFO
by Boss (18.3k points)
+2
Hello Tesla

i'm doubtful about your explanation for option B.

To implement static lists we prefer Array data structure and to implement Dynamic lists we prefer link list data structure.I think the reason, we prefer link list for implementing lists is because most of the general operations like inserting , deletion link list is far more efficient than array data structure.
0
about option C , i'm not getting your explanation and We prefer Circular Queue because in that way we avoid the chances of wasting space.
0
Insertion in array worst case O(n)

Deletion in array worst case 0(n)

Search in array O(log)

If we keep insertion O(1) then deletion will be O(n) and searching will be O(n)
0
Linear array with 2 pointers= circular queue
0
in worst case link list will also take $O(n)$ time for insertion and deletion but overall for these operation link list is far better than array.So that's why i think we prefer link list to implement lists.
0
Dude I just posted worst case complexity linked list is slightly better than array then why not
0
Would you prefer to do insertion , deletion and others related operations like merging using array over link list ?

My point is most of the time link list are more efficient than array for general operations.If we have pointer for last node , then we can do insertion/deletion in constant time.

Dynamic nature of link lists make it more efficient for basic operations.
0
There is no algorithm in single linked list that can do both insertion and deletion in constat time, either insertion can be in constant or deletion can be constant

Total cost of LInked list O( 1+ n +. n) = O(2N +1)

Total cost of Array O(n + n + logn) = O(2N + logn)

 

Even in terms of cost and dynamic nature linkd list beats array
0
He didn't mention anywhere that link list is single link list.

total cost for which operation?

Tesla can you tell me again , why do you think option 2 is correct ?i thought you were categorizing it on the bases of Nature of lists (dynamic/static) and when list nature is static , of course link list are of no use and this make that statement false. But as i'm able to see , lists are just collection of data , when we implement them as array or link list , then we define their nature like dynamic /static.so in that way you reason in your answer is not making any sense? am i missing something ?
0
If nature of list is dynamic then no doubts Linked list is better.

Question does not say anything about nature of lined list so there is no harm in assuming it to be single linked list

On my previous comment I showed that single linked is better then array even for static list

 

So when we perfer array when we need random access to data, and when search queries are more then insertion and deletion
0
explain the concept of list for array and linkedlist
0 votes
Can anybody pls explain ii) point.

Thank-you
by (233 points)
edited by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,500 answers
195,541 comments
100,994 users