Recent questions tagged linked-lists

0 votes

0 answers

1

Cormen Edition 3 Exercise 10.2 Question 8 (Page No. 241)
Explain how to implement doubly linked lists using only one pointer value $x.np$ per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as $k$-bit integers, and define $x.np$ ... $INSERT$, and $DELETE$ operations on such a list. Also, show how to reverse such a list in $O(1)$ time.

asked Jun 30, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 103 views

0 votes

0 answers

2

Cormen Edition 3 Exercise 10.2 Question 7 (Page No. 241)
Give a $\Theta(n)$ time nonrecursive procedure that reverses a singly linked list of $n$ elements. The procedure should use no more than constant storage beyond that needed for the list itself.

asked Jun 30, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 42 views

0 votes

0 answers

3

Cormen Edition 3 Exercise 10.2 Question 6 (Page No. 241)
The dynamic-set operation $UNION$ takes two disjoint sets $S_1$ and $S_2$ as input, and it returns a set $S=S_1 \cup S_2$ consisting of all the elements of $S_1$ and $S_2$.The sets $S_1$ and $S_2$ are usually destroyed by the operation. Show how to support $UNION$ in $O(1)$ time using a suitable list data structure.

asked Jun 30, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 19 views

0 votes

0 answers

4

Cormen Edition 3 Exercise 10.2 Question 5 (Page No. 240)
Implement the dictionary operations $INSERT$, $DELETE$, and $SEARCH$ using singly linked, circular lists. What are the running times of your procedures?

asked Jun 30, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 35 views

0 votes

0 answers

5

Cormen Edition 3 Exercise 10.2 Question 4 (Page No. 240)
LIST-SEARCH’(L, k) 1 x = L.nil.next 2 while x != L.nil and x.key != k 3 x = x.next 4 return x As written, each loop iteration in the LIST-SEARCH’ procedure requires two tests: one for $x\neq L.nil$ and one for $x.key\neq k$. Show how to eliminate the test for $x\neq L.nil$ in each iteration.

asked Jun 30, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 18 views

0 votes

1 answer

6

Cormen Edition 3 Exercise 10.2 Question 3 (Page No. 240)
Implement a queue by a singly linked list $L$. The operations of $ENQUEUE$ and $DEQUEUE$ should still take $O(1)$ time.

asked Jun 30, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 26 views

0 votes

0 answers

7

Cormen Edition 3 Exercise 10.2 Question 2 (Page No. 240)
Implement a stack using a singly linked list $L$. The operations $PUSH$ and $POP$ should still take $O(1)$ time.

asked Jun 30, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 14 views

0 votes

0 answers

8

Cormen Edition 3 Exercise 10.2 Question 1 (Page No. 240)
Can you implement the dynamic-set operation $INSERT$ on a singly linked list in $O(1)$ time? How about $DELETE$?

asked Jun 30, 2019 in Algorithms by akash.dinkar12 Boss (42.4k points) | 10 views

0 votes

0 answers

9

doubly linked linked list
why we use double pointer struct Node** head here? can anyone explain with details /* Given a reference (pointer to pointer) to the head of a DLL and an int, appends a new node at the end */ void append(struct Node** head_ref, int new_data) { struct Node* ... } while (last->next != NULL) last = last->next; last->next = new_node; new_node->prev = last; return; }

asked May 24, 2019 in DS by Arun Rout (117 points) | 79 views

0 votes

1 answer

10

Self Doubt on Linked List
Can somebody write the code or algorithm, how merge sort works efficiently in linked list? Is Heap sort most inefficient in Linked List Sorting? Elaborate plz

asked Apr 29, 2019 in DS by srestha Veteran (119k points) | 61 views

0 votes

0 answers

11

Locality of Rference(OS+DS) (ACE)
An OS uses virtual memory with paging technique for memory allocation. Which of the following searching technique on given data structure use locality of reference? Linear search on linked list Binary search on array Linear search on array Binary search on linked list

asked Mar 2, 2019 in Programming by srestha Veteran (119k points) | 106 views

0 votes

1 answer

12

Linked list
What does the following program do on two linked lists? Struct node *myFun (struct node * a, struct node * b) { Struct node *new = NULL ; If (a = = NULL) return (b) ; if (b = = NULL) return (a) ; If (a → data <= ... two linked lists by selecting the alternate nodes merges two sorted linked lists into final sorted linked list merges two linked lists by selecting the nodes in reverse.

asked Dec 27, 2018 in DS by sharadsingh (29 points) | 128 views

+1 vote

1 answer

13

NTA NET DEC18 Q6

asked Dec 25, 2018 in Algorithms by Sanjay Sharma Boss (49.3k points) | 100 views

+1 vote

0 answers

14

Gateforum Test Series: Programming & DS - Linked Lists

asked Dec 24, 2018 in DS by Gupta731 Active (4.8k points) | 127 views

0 votes

0 answers

15

Testbook - Linked List
int find (struct node * first, int n) { while (first data ! = n) first = first — next; if (first data = = n) return(1); else return (-1); in the above code segment if the value of 'n' is 5, then the function return 1, but if the value of 'n' is 9, then what does it do ?

asked Dec 5, 2018 in DS by Mk Utkarsh Boss (36.6k points) | 149 views

0 votes

0 answers

16

MadeEasy Test Series: Programming & DS - Linked Lists
You're entrusted with the task of deleting a node in a singly linkedlist, whose data field is 'x'. Note that, the node which is to be deleted can be at any arbitrary position in the linked list. Consider the following ... pointer to the starling node of the linked list. Which of the following options is correct? How deletion possible with S2?

asked Dec 3, 2018 in DS by Ashish Roy 1 (167 points) | 195 views

0 votes

0 answers

17

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?

asked Nov 20, 2018 in Programming by srestha Veteran (119k points) | 188 views

0 votes

0 answers

18

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?

asked Nov 20, 2018 in DS by aditi19 Loyal (5.2k points) | 124 views

0 votes

1 answer

19

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?

asked Nov 19, 2018 in Programming by srestha Veteran (119k points) | 138 views

0 votes

0 answers

20

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})$

asked Nov 18, 2018 in Programming by Lakshman Patel RJIT Veteran (59.1k points) | 207 views

0 votes

0 answers

21

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?

asked Nov 4, 2018 in DS by srestha Veteran (119k points) | 206 views

0 votes

0 answers

22

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

asked Oct 26, 2018 in DS by Lakshman Patel RJIT Veteran (59.1k points) | 81 views

0 votes

0 answers

23

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})$

asked Oct 26, 2018 in DS by Lakshman Patel RJIT Veteran (59.1k points) | 85 views

0 votes

0 answers

24

IISC-CDS Written Test Sample Question

asked Oct 25, 2018 in Programming by Sayan Bose Loyal (7.4k points) | 469 views

0 votes

1 answer

25

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)$

asked Oct 17, 2018 in DS by Lakshman Patel RJIT Veteran (59.1k points) | 127 views

+1 vote

0 answers

26

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?

asked Oct 17, 2018 in DS by Lakshman Patel RJIT Veteran (59.1k points) | 77 views

0 votes

0 answers

27

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.

asked Oct 17, 2018 in DS by Lakshman Patel RJIT Veteran (59.1k points) | 166 views

0 votes

1 answer

28

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

asked Sep 26, 2018 in DS by aditi19 Loyal (5.2k points) | 54 views

0 votes

1 answer

29

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??

asked Sep 20, 2018 in DS by sushmita Boss (17.7k points) | 197 views

0 votes

0 answers

30

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; } }

asked Sep 17, 2018 in Programming by Vaishnavi01 (153 points) | 133 views

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

Recent questions tagged linked-lists

Recent Posts

Recent Blog Comments