GATE CSE 2023 | Question: 3

Question

Let $\textsf{SLLdel}$ be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let $\textsf{DLLdel}$ be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list.
Let $n$ denote the number of nodes in each of the linked lists. Which one of the following choices is $\text{TRUE}$ about the worst-case time complexity of $\textsf{SLLdel}$ and $\textsf{DLLdel}?$

• A. $\textsf{SLLdel}$ is $O(1)$ and $\textsf{DLLdel}$ is $O(n)$
• B. Both $\textsf{SLLdel}$ and $\textsf{DLLdel}$ are $O(\log (n))$
• C. Both $\textsf{SLLdel}$ and $\textsf{DLLdel}$ are $O(1)$
• D. $\textsf{SLLdel}$ is $O(n)$ and $\textsf{DLLdel}$ is $O(1)$

Comments

That is a nice trick, but we should use that if we were told to delete the value present at the node-pointer being provided..
If you do that in this case, it will change the order of elements in the Singly Linked List which is to be avoided when deleting the node.

---

@Shrutik whatever operation you've suggested is NOT EVEN a valid delete operation. Please refer to some textbook to know what delete operation is supposed to do in a List ADT.

There are other ways from which you can simulate delete in O(1), but then question arises how to delete last node.

But that also is NOT the prime issue, as a node can have any data, we don't know what data, so we cannot guarantee swapping of values of nodes in O(1).

---

for swapping it takes O(n) time.so no use

Answer 1

The answer should be D)

What we can do is traverse from the head pointer to find object 1. Then change the node its pointing to object 3. Then we can free the Object 2.
 

The reason this algorithm is O(n) that we have to traverse from from the head node. To the node just before we want to delete (object 1) here.

Can’t it be done in O(1) by copying?

No, there has been a solution in which some say we swap object3 ↔ object2 and delete object2 node. But what we don’t consider here is the swapping complexity.

If the object that the node holds isn’t swappable O(1) then the complexity would depend upon the complexity to swap.


How O(1) in DLL?

1. I arrive at Object2.
2. Save the pointer to the next node.
3. Traverse the link back to object 1 set the node next to object3.
4. Free object2 node

Each step can be performed in O(1) hence its O(1)

Comments

suppose we have 1 to n elements in linked list 

if we want to delete 1^st node it will take O(1)time 

if we want to delete node from 2 to (n-1) we can use the swap method and delete it in O(1)

in worst case which is if we want to delete the last element (nth element ) there is nothing to swap  because it is a last node ,so we need to traverse to the (n-1)^th node to make (n-1)^th node pointer to null

so time complexity for worst case will be O(1)in case of SLL

---

How is it O(1) in case of Singly Linked List? That is wrong.

---

Its O(n) buddy for SLL and O(1) for DLL

Answer 2

In Singly Linked-List:

First we have to traverse that takes O(n) time. Using while loop as :

                 while(h->next!=q) {

                                               h= h->next;

                                           }  

Then delete node (Pointed by q) in O(1) time

                                          h->next = q->next;

                                             free(q);

Total time = O(n) + O(1) = O(n).

In Doubly Linked-List:

We can delete the node(Pointed by q) without traversing it as:

                            q->prev->next = q->next;

                             q->next->prev = q->prev;

                                   free(q);

That only take O(1) time.