Which condition I'm failing to satisfy in removing circular doubly linked list?

Question

This is my removing function.

void removeAt (int pos)
{
    struct Node *temp= (struct Node *) malloc(sizeof(struct Node *)); 
    struct Node *x=(struct Node *)malloc(sizeof(struct Node *));

if(pos==1)
{
if(head==tail)

{ 
    temp=head;
    head=tail=NULL; 
    free (temp);
}

else
{

temp=head;
head=head->next;

head->prev=tail;
tail->next=head;

free (temp);
}
}

else
{

    temp=NULL;
    for(int i=0;i<pos;i++)
    { 
        x=temp; 
        if(i==0)
        temp=head;

        else
        temp=temp->next;
    }

    x->next=temp->next;

    if(temp==tail)
    x->next=head;
    else
    temp->next->prev=x; 
    free (temp);

}

}

This function gets input as position and removes an element at that position. When I run this I'm getting private test case failed. I can't figure out which test case I'm failed to satisfy. Please do help me to solve this issue.

Answer 1

Some issues:

• Don't allocate memory: the function is not going to add any node, so this memory serves nothing, and will actually leak.

• head->tail is an invalid reference. Where you have this line, you should set head = tail = NULL;

• if(temp==tail) x->next=head; should not be needed: as your list is circular, it should always have tail->next == head, so this assignment is not needed.

• temp->next->prev=x; should always be executed, also when temp == tail. As the list is circular so the tail node does not need special treatment when it comes to setting prev or next.

• There is no code to adjust the tail reference when you have removed the tail node.

• As the list is circular, there should be no need to differentiate between pos==1 and others. The special cases to pay attention to are:

  • when the list is empty, the function should not do anything.
  • when the list has just one node, it should be emptied.
  • if the head node is deleted, that head reference should be updated (as you do)
  • if the tail node is deleted, that tail reference should be updated

Here is the corrected code:

void removeAt(int pos) {
    // Safeguard
    if (head == NULL || pos <= 0) return;

    // Don't allocate node memory with malloc
    struct Node *temp = head;
    if (head == tail) {
        head = tail = NULL; // fix
    } else { 
        for (int i = 1; i < pos; i++) { 
            temp = temp->next;
        }
        temp->prev->next = temp->next;
        temp->next->prev = temp->prev;
        if (temp == tail) tail = temp->prev;
        head = tail->next;  // Invariant
    }
    free(temp);
}