Recent questions tagged linked-list / GATE Overflow for GATE CSE

1 votes

0 answers

121

Circular Link List Insertion and Deletion
Suppose a circular queue of capacity (n - 1) elements is implemented with an array of n elements. Now, in this queue what will be condition for FULL and EMPTY? Full:(REAR+1)%n== FRONT (or) (FRONT+1)%n==REAR (or) FRONT==REAR Empty: ... So, in case of Full, Rear point array that must be array index more than Front Am I right? Then what equation will valid?

Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements.Now, in this queue what will be condition for FULL and EMPTY?Full:(REAR...

srestha

1.4k views

srestha asked Nov 20, 2018

1 votes

2 answers

122

Karumanchi
There is a singly linked list. We have a pointer to a particular node(it is not tail node). what is the time and space complexity required to delete this node? my approach is... As there is no previous pointer so we traverse the list from the starting to just ... complexity as O(n) and space complexity O(1). but in the book the time complexity is mentioned O(1) where am I going wrong?

There is a singly linked list. We have a pointer to a particular node(it is not tail node). what is the time and space complexity required to delete this node?my approach...

aditi19

899 views

aditi19 asked Nov 20, 2018

0 votes

1 answer

123

Reversing Singly Linked List
To reverse a Singly Linked List is the below is correct code? (or) need to change Struct node *reverse(struct node *start) { Struct node *prev,*ptr,*next; prev=NULL; ptr=start; while(ptr!=NULL) { next=ptr->link; ptr->link=prev; prev=ptr; ptr=next; } start=prev; return start; Plz tell me, is here all link updating correctly?

To reverse a Singly Linked List is the below is correct code? (or) need to change Struct node *reverse(struct node *start) { Struct node *prev,*ptr,*next; prev=NULL; ptr=...

srestha

1.1k views

srestha asked Nov 19, 2018

1 votes

0 answers

124

Linked list Quiz
Consider an unrolled linked list with $n$ elements.This list stores multiple elements in each node. What is the worst case time complexity to find the $k^{th}$ element if the number of nodes and the number of elements in each node are equal? $A)O(n)$ $B)O(\sqrt n)$ $C)O(nlogn)$ $D)O(n^{2})$

Consider an unrolled linked list with $n$ elements.This list stores multiple elements in each node.What is the worst case time complexity to find the $k^{th}$ element if ...

Lakshman Bhaiya

960 views

Lakshman Bhaiya asked Nov 18, 2018

1 votes

0 answers

125

Intersection among elements of Linked List
Given two unsorted singly-linked lists each with n distinct elements. There exists an efficient intersection algorithm, that computes and returns a new list with common elements between the input lists. How much time does the intersection algorithm requires in worst case, if it is allowed to use constant extra space only?

Given two unsorted singly-linked lists each with n distinct elements. There exists an efficient intersection algorithm, that computes and returns a new list with common e...

srestha

2.4k views

srestha asked Nov 4, 2018

0 votes

0 answers

126

Linked list implementation of Previous
Consider the following function: Find(Element Type X,List L) { Position Prev_Pos,XPos; Prev_Pos=Find Previous(X,L); if(Prev_Pos--->Next!=NULL) /* found */ { XPos=Prev_Pos--->Next; Prev_Pos---->Next=XPos--->Next; ... lists $B)$Linked list implementation of singly linked lists $C)$Linked list implementation of doubly linked lists $D)$None of these

Consider the following function:Find(Element Type X,List L) { Position Prev_Pos,XPos; Prev_Pos=Find Previous(X,L); if(Prev_Pos ->Next!=NULL) /* found */ ...

Lakshman Bhaiya

526 views

Lakshman Bhaiya asked Oct 26, 2018

1 votes

0 answers

127

Reverse Linked list
What is the time complexity of the best-known algorithm to reverse a doubly linked list? $A) O(n)$ $B) O(logn)$ $C) O(1)$ $D) O(n^{2})$

What is the time complexity of the best-known algorithm to reverse a doubly linked list?$A) O(n)$$B) O(logn)$$C) O(1)$$D) O(n^{2})$

Lakshman Bhaiya

1.3k views

Lakshman Bhaiya asked Oct 26, 2018

1 votes

0 answers

128

IISC-CDS Written Test Sample Question

Sayan Bose

2.6k views

Sayan Bose asked Oct 25, 2018

0 votes

1 answer

129

Test series
Consider unsorted doubly linked list data structure containing n items. For decrease key operation a pointer is provided to the record on which the operation is performed. An algorithm performs the following operations on the list in this order: sqrt(n) insert operations, o(nlogn) decrease key and ... of all these operations put together? (a) O(n) (b) O(n2) (c) O(n2logn) (d) O(sqrt(n))

Consider unsorted doubly linked list data structure containing n items. For decrease key operation a pointer is provided to the record on which the operation is performed...

Somoshree Datta 5

791 views

Somoshree Datta 5 asked Oct 22, 2018

0 votes

1 answer

130

test question
We wish to implement a double ended queue using link list. The double ended queue must support , the operations of (i) struct node *push_back(struct node*,struct node * ,int ) - pushing at the end of the list (ii) struct node *pop_back(struct node* ) -popping ... rear; S3:front==NULL S4:front=front->next S1:rear->next=temp; S2:rear=temp; S3:front==NULL S4:front=front->next

We wish to implement a double ended queue using link list. The double ended queue must support , the operations of(i) struct node *push_back(struct node*,struct node * ,i...

Prince Sindhiya

529 views

Prince Sindhiya asked Oct 18, 2018

0 votes

1 answer

131

Linked list insertion
In a linked list with $n$ nodes, the time taken to insert an element after an element pointed by some pointer is: $(A) O(1)$ $(B) O(logn)$ $(C) O(n)$ $(D) O(nlogn)$

In a linked list with $n$ nodes, the time taken to insert an element after an elementpointed by some pointer is:$(A) O(1)$$(B) O(logn)$$(C) O(n)$$(D) O(nlogn)$

Lakshman Bhaiya

25.6k views

Lakshman Bhaiya asked Oct 17, 2018

1 votes

0 answers

132

Linked list
If the head of a Linked List is pointing to $k$ th element, then how will you get the elements before $k$ th element?

If the head of a Linked List is pointing to $k$ th element, then how will you get the elements before $k$ th element?

Lakshman Bhaiya

612 views

Lakshman Bhaiya asked Oct 17, 2018

0 votes

0 answers

133

Linked List Data Structures And Algorithms Made Easy By Narasimha Karumanchi
Suppose there are two singly linked lists both of which intersect at some point and become a single linked list. The head or start pointers of both the lists are known, but the intersecting node is not known. ... ; n. Give an algorithm for finding the merging point. And find the time complexity and space complexity also.

Suppose there are two singly linked lists both of which intersect at some pointand become a single linked list. The head or start pointers of both the lists are known, bu...

Lakshman Bhaiya

1.1k views

Lakshman Bhaiya asked Oct 17, 2018

0 votes

1 answer

134

Doubt
can anyone explain in detail why and how is merge sort optimal for linked list?

can anyone explain in detail why and how is merge sort optimal for linked list?

aditi19

451 views

aditi19 asked Sep 26, 2018

0 votes

1 answer

135

conceptual doubt
WHAT IS THE TIME COMPLEXITY TO ENQUEUE AN ELEMENT IF THE QUEUE IS IMPLEMENTED AS A CIRCULAR QUEUE AND WE HAVE GOT ONLY ONE POINTER TO FRONT ELEMENT??

WHAT IS THE TIME COMPLEXITY TO ENQUEUE AN ELEMENT IF THE QUEUE IS IMPLEMENTED AS A CIRCULAR QUEUE AND WE HAVE GOT ONLY ONE POINTER TO FRONT ELEMENT??

sushmita

1.2k views

sushmita asked Sep 20, 2018

0 votes

1 answer

136

Linked List Problem
struct node* foo(struct node* a, struct node* b) { struct node* result, *rec; if(a==null) return b; else if(b==null) return a; else { rec=foo(a->next,b->next); result=a; a->next=b; b->next=rec; return result; } }

struct node* foo(struct node* a, struct node* b){ struct node* result, *rec; if(a==null) return b; else if(b==null) return a; else { rec=foo(a->next,b->next...

Vaishnavi01

647 views

Vaishnavi01 asked Sep 17, 2018

0 votes

1 answer

137

Testbook Test Series: Programming & DS - Linked Lists
The answer is 'd' will be printed. Can someone draw the linked list after the operations are performed. I think the second operation of the code doesn't bring in any change to the list. thanks in advance

The answer is 'd' will be printed. Can someone draw the linked list after the operations are performed. I think the second operation of the code doesn't bring in any chan...

Kalpataru Bose

562 views

Kalpataru Bose asked Aug 23, 2018

0 votes

1 answer

138

Link list
Suppose we are deleting a node with data field as x. Which can be present anywhere in the list. Consider following Scenarios : S1 : You're only provided with pointer to the node which needs to be deleted. S2 : You're only provided with the pointer to the ... cases for S2. D. Deletion is not possible for certain cases in S2, but deletion is possible in all cases for S1. Ans. C

Suppose we are deleting a node with data field as x. Which can be present anywhere in the list.Consider following Scenarios :S1 : You're only provided with pointer to the...

Na462

859 views

Na462 asked Aug 22, 2018

1 votes

1 answer

139

Linked List
What kind of linked list is best to answer question like “What is the item at position n?” a) Singly linked list b) Doubly linked list c) Circular linked list d) Array implementation of linked list

What kind of linked list is best to answer question like “What is the item at position n?”a) Singly linked listb) Doubly linked listc) Circular linked listd) Array im...

pradeepchaudhary

1.8k views

pradeepchaudhary asked Aug 19, 2018

0 votes

0 answers

140

Linked list
Function to reverse the circular doubly linked list. Why is this function showing an error? head is a global variable. void reverse() { struct node *z; struct node *t = head -> forw; while(t != head) { z=t->back; t->back=t->forw; t->forw=z; t = t -> back; } z=t->back; t->back=t->forw; t->forw=z; head=t->forw; }

Function to reverse the circular doubly linked list.Why is this function showing an error?head is a global variable.void reverse() { struct node *z; struct node *t = h...

rishabhgupta12

815 views

rishabhgupta12 asked Aug 6, 2018

2 votes

2 answers

141

Linked list
How to trace the below program? p and q are the starting address of two different linked list struct node*Do(struct node*p,struct node*q){ struct node*ps,*qs; if(!p){ return(q); } else if(!q){ return(p); } else{ ps=p->link; qs=q->link; p->link=q; q->link=Do(ps,qs); return(p); } }

How to trace the below program?p and q are the starting address of two different linked list struct node*Do(struct node*p,struct node*q){ struct node*ps,*qs; if(!p...

rishabhgupta12

910 views

rishabhgupta12 asked Aug 3, 2018

1 votes

1 answer

142

Asymptotic time complexity to add a node at the end of singly linked list.
What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list? (a) O(1) (b) O(n) (c) θ (n) (d) θ (1) Confused between option (b) and (c) .

What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?(a) O(1) (b...

arya_stark

21.1k views

arya_stark asked Jul 4, 2018

0 votes

2 answers

143

Ace Test Series: Data Structures - Circular Linked List

Na462

943 views

Na462 asked Jun 29, 2018

1 votes

1 answer

144

Self-Doubt
In a circular linked list last node points to the : $Head$ $Tail$ $First Node$

In a circular linked list last node points to the :$Head$$Tail$$First Node$

Phlegmatic

1.1k views

Phlegmatic asked May 27, 2018

2 votes

3 answers

145

ISRO2018-63
Consider a singly linked list of the form where $F$ is a pointer to the first element in the linked list and $L$ is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list? ... list Delete the first element of the list Add an element after the last element of the list Interchange the first two elements of the list

Consider a singly linked list of the form where $F$ is a pointer to the first element in the linked list and $L$ is the pointer to the last element in the list. The time ...

Arjun

3.9k views

Arjun asked Apr 22, 2018

3 votes

2 answers

146

ISRO2018-79
A doubly linked list is declared as: struct Node { int Value; struct Node *Fwd; struct Node *Bwd; }; Where Fwd and Bwd represent forward and backward link to the adjacent elements of the list. Which of the following segment of code deletes the node pointed to by ... Bwd = X.Bwd; X$\rightarrow$Bwd$\rightarrow$Fwd = X$\rightarrow$Bwd; X$\rightarrow$Fwd$\rightarrow$Bwd = X$\rightarrow$Fwd;

A doubly linked list is declared as:struct Node { int Value; struct Node *Fwd; struct Node *Bwd; };Where Fwd and Bwd represent forward and backward link to the adjacent e...

Arjun

28.7k views

Arjun asked Apr 22, 2018

0 votes

1 answer

147

Printing elements of linked-list using recursion.
Can anyone check this program? I got some warning. #include<stdio.h> #include<stdlib.h> void func(struct node *); struct node { int data; struct node *next; }; int main() { struct node *head=(struct node *)malloc(sizeof(struct node)); ... void func(struct node *p) { if(p) { printf("\n%d",p->data); func(p->next); } }

Can anyone check this program?I got some warning.#include<stdio.h>#include<stdlib.h>void func(struct node *); struct node{ int data; struct node *next;}; int ...

Ahsanul Hoque

578 views

Ahsanul Hoque asked Mar 6, 2018

36 votes

6 answers

148

GATE CSE 2018 | Question: 3
A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let $n$ denote the number of nodes in the queue. Let 'enqueue' be implemented by inserting a new node at the head, and 'dequeue' ... $\Theta(1), \Theta(n)$ $\Theta(n), \Theta(1)$ $\Theta(n), \Theta(n)$

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let $n$ denote the number of node...

gatecse

15.4k views

gatecse asked Feb 14, 2018

0 votes

1 answer

149

linked list
the sorage requirements of a linked stack with n elements will be what

the sorage requirements of a linked stack with n elements will be what

kd.....

2.0k views

kd..... asked Feb 9, 2018

0 votes

1 answer

150

MadeEasy Test Series: Programming & DS - Programming In C
Consider the C node fragment given below: Which of the following true about above code if input is given as linked list of n-element in which for each node memory is created in heap area? A. Compiles successfully but execution may ... in else part. I think answer should be C. Because the return type is int node* Can someone please confirm.

Consider the C node fragment given below:Which of the following true about above code if input is given as linked list of n-element in which for each node memory is creat...

Rishabh Gupta 2

1.1k views

Rishabh Gupta 2 asked Jan 30, 2018

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