GATE CSE 1996 | Question: 1.12

Question

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.

• A. $(ii)$ and $(iii)$ are true
• B. $(i)$ and $(ii)$ are true
• C. $(iii)$ and $(iv)$ are true
• D. $(ii)$ and $(iv)$ are true

Comments

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

---

Some programming languages use the word “List” as a synonym to “Linked List”. But theoretically these two are somewhat different.

$\color{red}{\text{Difference between List & Linked-List:}}$

List is just an Ordered Sequence of elements, Not a data structure.

In the non-technical world, We all have an intuitive understanding of what we mean by a “list”. We want to turn this intuitive understanding into a concrete data structure with implementations for its operations. The most important concept related to lists is that of position. In other words, we perceive that there is a first element in the list, a second element, and so on. So, define a list to be a finite, ordered sequence of data items known as elements. This is close to the mathematical concept of a sequence.

“Ordered” in this definition means that each element has a position in the list. So the term “ordered” in this context does not mean that the list elements are sorted by value. (Of course, we can always choose to sort the elements on the list if we want; it’s just that keeping the elements sorted is not an inherent property of being a list.)

So, List is NOT a data structure, But just a ordered sequence of elements.

Now, any list can be implemented using any data structure that we have Like Array, Linked List, Stack, Queue, Search Tree etc.

$\color{red}{\text{Basic List Operations:}}$

What basic operations do we want our lists to support?

Our common intuition about lists tells us that a list should be able to grow and shrink in size as we insert and remove elements. We should be able to insert and remove elements from anywhere in the list. We should be able to gain access to any element’s value, either to read it or to change it. We must be able to create and clear (or reinitialize) lists. It is also convenient to access the next or previous element from the “current” one.

https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/ListIntro.html

https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/ListADT.html

https://en.wikipedia.org/wiki/List_(abstract_data_type)

---

Refer to chapter 3, of "Data Structures and Algorithm Analysis" by Mark Allen Weiss.

Answer 1

(A). (i) and (iv) are false.

http://en.wikipedia.org/wiki/List_(abstract_data_type)#Operations

Comments

@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. :)

---

insertion in LL take O(1) while in array it takes O(n) and the crux is list dynamically change its size so LL is preferable

---

@mrinmoyh what say if we insert the node in the front which will cost you theta(1)?

 

Answer 2

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

Comments

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.

---

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.

Answer 3

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

Comments

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 ?

---

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

---

explain the concept of list for array and linkedlist

Answer 4

The first statement is true. Stacks are a type of data structure that follows the Last-in-first-out (LIFO) principle, where the last element added to the stack is the first one to be removed. This makes it efficient for performing first-in-first-out (FIFO) type of computations, such as undo/redo operations, backtracking, and recursive function calls.

The second statement is also true. Linked lists are a type of data structure where each element is a separate object with a reference to the next element. This allows for fast insertion and deletion of elements, which are commonly used operations in lists. Implementing lists on an array, on the other hand, requires shifting elements to make room for new elements or to fill gaps after deleting elements. This can be time-consuming and not efficient.

The third statement is also true. A circular array is an array that wraps around when it reaches the end, allowing for efficient use of space. Implementing a queue on a circular array allows for fast enqueue and dequeue operations, as well as efficient use of space. Implementing a queue on a linear array with two indices can lead to wasted space, as well as the need to shift elements when one end of the array becomes full.

The last statement is false. Queues are a type of data structure that follows the First-in-first-out (FIFO) principle, where the first element added to the queue is the first one to be removed. This makes it efficient for performing last-in-first-out (LIFO) type of computations, such as breadth-first traversals, scheduling, and load balancing tasks.