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

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?

0

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

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