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

| 430 views
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).
by Boss (12.3k points)
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.
by (435 points)