search
Log In

Recent questions tagged linked-lists

1 vote
1 answer
1
The address field of linked list : Contain address of next node May contain null character Contain address of next pointer Both $\left (A \right)$ and $\left ( B \right)$
asked Mar 31 in DS Lakshman Patel RJIT 260 views
2 votes
1 answer
2
What does the following function do for a given Linked List with first node as head? void fun1(struct node* head) { if(head==NULL) return; fun1(head->next); printf("%d",head->data); } Prints all nodes of linked lists Prints all nodes of linked list in reverse order Prints alternate nodes of Linked List Prints alternate nodes in reverse order
asked Mar 30 in DS Lakshman Patel RJIT 243 views
1 vote
1 answer
3
Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as $\textit{prev}$ and next pointer as $\textit{next}$. void fun(struct node ** ... $6 \leftrightarrow 5 \leftrightarrow 4 \leftrightarrow 3 \leftrightarrow 1 \leftrightarrow 2$
asked Mar 30 in DS Lakshman Patel RJIT 155 views
12 votes
10 answers
4
What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order? $\Theta(n)$ $\Theta(n \log n)$ $\Theta ( n)^{2}$ $\Theta(1)$
asked Feb 12 in DS Arjun 6.8k views
0 votes
0 answers
5
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$ to be $x.np=x.next$ $XOR$ $x.prev$, the $k$- ... to implement the $SEARCH$, $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 akash.dinkar12 214 views
0 votes
1 answer
6
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 akash.dinkar12 124 views
0 votes
1 answer
7
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 akash.dinkar12 74 views
0 votes
0 answers
8
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 akash.dinkar12 85 views
0 votes
0 answers
9
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 akash.dinkar12 59 views
0 votes
2 answers
10
0 votes
1 answer
11
0 votes
0 answers
12
0 votes
0 answers
13
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* new_node = ( ... new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; new_node->prev = last; return; }
asked May 24, 2019 in DS Arun Rout 190 views
0 votes
2 answers
14
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 srestha 177 views
0 votes
0 answers
15
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 srestha 323 views
3 votes
1 answer
16
Which of the following sorting algorithms performs efficiently to sort a singly linked list containing $\log n$ nodes and the corresponding time complexity is? $\text{Insertion sort, } O(\log ^2 n)$ $\text{Merge sort, } \Theta (( \log n) \log (\log n ))$ $\text{Heap sort, } \Theta ( \log ^2)(\log n ))$ $\text{Quick sort, } O ( \log 2)(\log n ))$
asked Dec 27, 2018 in Algorithms Ruturaj Mohanty 336 views
0 votes
1 answer
17
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 <= b → ... merges 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 sharadsingh 197 views
1 vote
1 answer
18
asked Dec 25, 2018 in Algorithms Sanjay Sharma 144 views
0 votes
0 answers
20
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 Mk Utkarsh 255 views
0 votes
1 answer
21
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 scenarios. S1. You're only provided ... provided with a 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 Ashish Roy 1 322 views
0 votes
0 answers
22
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: FRONT==REAR (or) REAR== ... location as rear. 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 srestha 351 views
0 votes
0 answers
23
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 before the ... 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 aditi19 223 views
0 votes
1 answer
24
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 srestha 277 views
1 vote
0 answers
25
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 Lakshman Patel RJIT 336 views
0 votes
0 answers
26
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 srestha 406 views
0 votes
0 answers
27
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; XPos--->Next=L--->Next; L- ... of self-adjusting 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 Lakshman Patel RJIT 132 views
0 votes
0 answers
28
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 Lakshman Patel RJIT 263 views
0 votes
0 answers
29
0 votes
1 answer
30
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 for the end of ... ; S2:temp=rear; S3:front==NULL S4:front=front->next S1:rear->next=temp; S2:rear=temp; S3:front==NULL S4:front=front->next
asked Oct 18, 2018 in Programming Prince Sindhiya 92 views
...