edited by
10,301 views
8 votes
8 votes

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}?$

  1. $\textsf{SLLdel}$ is $O(1)$ and $\textsf{DLLdel}$ is $O(n)$
  2. Both $\textsf{SLLdel}$ and $\textsf{DLLdel}$ are $O(\log (n))$
  3. Both $\textsf{SLLdel}$ and $\textsf{DLLdel}$ are $O(1)$
  4. $\textsf{SLLdel}$ is $O(n)$ and $\textsf{DLLdel}$ is $O(1)$
edited by

2 Answers

6 votes
6 votes

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?

Doubly linked list

  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)

edited by
5 votes
5 votes

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.

Answer:

Related questions

14 votes
14 votes
3 answers
1
admin asked Feb 15, 2023
6,538 views
Which one of the following sequences when stored in an array at locations $A , \ldots, A[10]$ forms a max-heap?$23,17,10,6,13,14,1,5,7,12$$23,17,14,7,13,10,1,5,6,12$$23,1...