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.

CodePudding user response：

There are a few significant problems. First of all, since you are deleting nodes, I would expect to see free statements but no malloc statements.

Regarding lines:

struct Node *temp= (struct Node *) malloc(sizeof(struct Node *)); 
struct Node *x=(struct Node *)malloc(sizeof(struct Node *));

Pointers x and temp should be left uninitialized or set to NULL.

Under condition if(pos==1) / if(head==tail), you only have one node, so you would basically be freeing head and setting both head and tail pointers to NULL.

Under condition if(pos==1) / else, your code should work as-is.

Under condition else, it doesn't make sense to begin the for loop at zero, since the position can never actually be zero and since this requires an extra conditional statement. However, if pos were set to zero, you would be dereferencing a Null pointer, which would cause an exception. Also, I am not sure why this condition is needed:

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

CodePudding user response：

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);
}