ISRO2008-72

Question

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

• A. Deleting a node whose location is given
• B. Searching an unsorted list for a given item
• C. Inserting a node after the node with a given location
• D. Traversing the list to process each node

Comments

is ans is (A)

Answer 1

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

Comments

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

---

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.

---

Wow that’s a splendid reasoning! About data type assumptions

Answer 2

Answer is A) as it takes  O(1) to delete from doubly linked list as compared to O(n) from single linked list only in case tail pointer is given otherwise both will take O(n).

So for deletion if we take tail pointer then DLL is efficient

Answer 3

yes answer should be A