search
Log In
0 votes
484 views

Which of the following operations is performed more efficiently by doubly linked list than by singly linked list?

(a) Deleting a node whose location in given

(b) Searching of an unsorted list for a given item

(c) Inverting a node after the node with given location

(d) Traversing a list to process each node

why the answer is A)

Since for deleting a node from any given location we have to move from head to that location for that we need a pointer for both doubly and singly linked list (say q)

Steps in doubly linked list are as follow:-

q->prev->next = q->next;

q->next->prev = q->prev;

free(q);

and steps in singly linked list :-

q->next = q->next->next;

free(q->next);

it is easy to delete in singly than in doubly.

crct me?

in Algorithms 484 views
0
See the edited answer.

2 Answers

2 votes
In double linked list, you do not need to move from first node to that node....
Suppose the elements of double linked lists are     4 5 6 7 8 9
You want to delete 6, pointer to 6 is given.
You need not traverse from 4 to 5 to remove 6.
Directly go to 6.
Now....
p->prev->next = p->next
p->next->prev= p->prev

Thats it.  O(1).

In single linked list ....  4 5 6 7 8 9
You want to delete 6.  (Pointer to 6 is given)
Your code is not correct.
Deletion can be done as..

p->data= p->next->data;
temp=p->next
p->next= p->next->next
free(temp);
O(1) time complexity in single linked list too..
Both can be done in O(1).

edited by
0
Moreover singly linked list cannot do direct deletion.

Means suppose if q is pointing to a node u want to delete, u cannot delete it by singly linked list. Because we need address of previous node , to delete q,rt? @Ahwan
0
@srestha You can delete directly.  Using another trick. Just copy the next element to current..  then delete next...  so indirectly current one is deleted.  

I have written code for it.  Hence it can be done in O(1) in single linked list too.
0
yes, thats correct.

but in that case if the nodes are 5->6->7->8

then in next step it will be 5->5->7->8

and after deletion it will be 5->7->8

will not @Ahwan

then will the value 5 getting deleted? :(
0
@Srestha     5->6->7->8
You want to delete which node & pointer to which node is given ?
0 votes
The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

Related questions

0 votes
1 answer
1
292 views
Insertion of a node into a doubly linked list requires how many changes to various Next and Previous Pointer? A. No Change B. 1 Next , 1 Previous C. 2 Next , 2 Previous D. 3 Next , 3 Previous
asked Jun 28, 2017 in DS Arnab Bhadra 292 views
0 votes
2 answers
2
147 views
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 147 views
4 votes
1 answer
3
307 views
Consider the following code which is used to detect the loop in the linked list. Find the missing statement A? p = head; q = head->next; while(A) { if(p == q) exit(0) //loop detected p = p->next; q = (q->next)?(q->next->next) : q->next; } Which of the following are ... NULL) d) (p!=NULL) || (q!=NULL) Given ans is c.......but I think b could also be correct if not than why..... Please explain
asked Nov 3, 2017 in Programming Shivi rao 307 views
0 votes
1 answer
4
253 views
Why the following code is not giving desired results? The code simple push & appends the nodes in the linked list. #include <stdio.h> #include <stdlib.h> struct Node{ int item; struct Node* next; }; void push(struct Node** head,int item){ struct Node* fresh = (struct Node*) malloc( ... (head); return 0; } Output desired : 7->6->5->51->53 Shown output : ->51->53 Where is the error in this code?
asked Aug 18, 2017 in Programming Aghori 253 views
...