3.3k views

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

1. Deleting a node whose location is given
2. Searching an unsorted list for a given item
3. Inserting a node after the node with a given location
4. Traversing the list to process each node
in DS | 3.3k views

ANSWER: (1) Deleting a node whose location is given.

REASON:

In this question, we can simply eliminate the (2) and (4) from our choice, since in both the cases we need to visit every node one after other. Doubly LL will serve no extra good in these two cases as we need to proceed from starting node and go until the last note in LL or vice-versa .

(2)  To insert a new node in the LL after some specific node, we need not go back to the previous node in the LL. And thus, doubly LL will serve no purpose in this case too.

At last, in the case of (1) we are supposed to delete the node (say x) whose location is given. Which means that before we remove node x from the LL we need to store the address of next node in the list, linked to node x in the address field of node just before node x (which currently store the address of node x). Since we need to go back-and-forth in the list during this operation, doubly linked list will be a good help in increasing the efficiency by decreasing the time required for the operation.

LL referes to Linked List

by Active (4.7k points)
selected
0
I think even deletion can be done in O(1) in simple linked List.

[s]->[a]->[c]->[e]->[f]

to delete  ^  this i.e. node c

we can replace content of node c with content of node e and make c.next =e.next(i.e. node f) and delete original node e (whose content is already copied in node c). So content of node c is deleted ,this is what we want.
0

This absolutely right, there is nothing wrong in it. Except one small assumption.

All nodes of linked list have same structure abstractly, i.e., a linked list has two parts, one part for data and other for storing address. But this definition of nodes does not say anything about the type of data.

What I am trying to state is, that in a linked list, it is not necessary that all the nodes have to store same type of data. Pactically having different type of data stored in linked do not seems legit. Though that is again not true, cause lists in higher level language do allow storing data of different type (refer python's list). Another example is dictionary in higher level language.

So your assumptiom can be a valid optimisation when implementing linked list practically, but theoretically this can have major impact on run time analysis, as you can see.

0
what does same and different type of data have to do with this?
0
I was trying to explain that assuming that we can copy the content of one node to another is not reasonable assumption in this case.
0
1 -> 2 -> 3 -> 4 ->5

if 4 has to be deleted

connect 3 to 5 and free(4)

same way for doubly linked list

so  how does doubly become more efficient, can u explain a bit more
+4
Sure. See the questions says that the pointer to the node that has to be deleted is given. So in your example, we have the pointer to node 4 (as that is the one to be deleted). Now, to connect node 3 to node 5, we also need a pointer to node 3.
$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$$
In the singly linked list we cannot travel from current node to the previous node, thus getting to node 3 is not possible from node 4. We got to traverse the linked list from the start node until we reach a node (node 3 in this case) just before the node that is to be deleted (node 4 in this case) which will be $O(n)$, where $n$ is the number of nodes in the linked list. And then do the connection between node 3 and node 5 as you suggested.

Now consider the Doubly linked list
$$1 \rightleftharpoons 2 \rightleftharpoons 3 \rightleftharpoons 4 \rightleftharpoons 5$$
In the Doubly linked list we can traverse back and forth from a node. Thus, if we have a pointer to node 4, we can move back to locate node 3. Once we have the pointer node 3 we can do the connection just the way you suggested. All of this will take $O(1)$ time.

+1 vote