recategorized by
3,400 views
0 votes
0 votes

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?

recategorized by

2 Answers

2 votes
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 votes
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
0 votes
1 answer
1
Arnab Bhadra asked Jun 28, 2017
3,311 views
Insertion of a node into a doubly linked list requires how many changes to various Next and Previous Pointer?A. No ChangeB. 1 Next , 1 PreviousC. 2 Next , 2 PreviousD. 3 ...
0 votes
0 votes
2 answers
3
srestha asked Apr 29, 2019
718 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