The Gateway to Computer Science Excellence
0 votes
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

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,616 answers
195,897 comments
102,352 users