Deleting an element from double linked list in C-CodePudding

The program is for deleting a node from a double linked list and printing out the new list

The code works great for almost every testcase except when the element to be deleted is the 2nd last element from the end of the list. When that is given I get a segmentation fault error in my delete function, which i just have not been able to fix and hope to get fixed.

#include <stdio.h>
#include <stdlib.h>
//no work
struct node{
    int data;
    struct node *next;
    struct node *prev;
};

struct node *head = NULL;
void display();
void addnode(int x){
    struct node *current = (struct node *)malloc(sizeof(struct node));

    current->data = x;
    current->next = NULL;
    current->prev = NULL;

    if (head == NULL)
        head = current;
    else{
        struct node *temp;
        for (temp = head; temp->next != NULL; temp = temp->next);
        temp->next = current;
        current->prev = temp;
    }
}

void delete(int t){
    struct node *temp;
    if (head->next == NULL){
        if (head->data != t)
            printf("Target Element is Not Found\n");
        else{
            display();
            printf("List is Empty\n");
        }
    }else{
        for (temp = head; temp->next != NULL && temp->data != t; temp = temp->next);
        if (temp->data == t){
            if (temp->next != NULL){
                temp->next->next->prev = temp;
                temp->next = temp->next->next;
            }
        }
    }
}

void display(){
    struct node *temp;
    printf("List->");
    for (temp = head; temp->next != NULL; temp = temp->next)
        printf("%d ", temp->data);
    printf("%d->NULL\n", temp->data);
}

int main(){
    int n, temp;
    scanf("%d", &n);

    while (n--){
        scanf("%d", &temp);
        addnode(temp);
    }
    int t;
    scanf("%d", &t);
    
    display();
    delete(t);
    display();
}

There seem to be some world limit for this so let me try to fill that up very quick. Cuz i really want to earn some reputation and finally ask a whole bunch of stuff i wanted to ask. [1]: https://i.stack.imgur.com/Nke8q.png

CodePudding user response：

When temp points to the node to be deleted, and it is the next-to-last, then temp->next is not null but temp->next->next is, and your code attempts to execute temp->next->next->prev = temp;. Since temp->next->next is null, using temp->next->next->prev does not work. You need to rethink what your code is doing and why.

CodePudding user response：

The code works great for almost every testcase except when the element to be deleted is the 2nd last element from the end of the list.

I don't agree and below is the reason:

Multiple problems in your delete() function.

Major (you are already aware of this): If the list has more than 1 elements in it and, for deletion, user entered second last node to delete then segmentation fault is occurring. Its because of this in delete():
```
              temp->next->next->prev = temp;
```

temp->next->next is NULL and your code is attempting to access NULL pointer.

Major: If the list contain only one element and if you give that element as input to delete, it will output - List is Empty and node with that value will not be deleted:

  if (head->next == NULL){
      if (head->data != t)
          printf("Target Element is Not Found\n");
      else{
          display();
          printf("List is Empty\n");
      }
  ....
  ....

Major: If the list has more than 1 elements in it and, for deletion, user entered any node to delete other than last and second last node, the delete() will end up deleting the node next to the node entered by user (which is supposed to be delete). Moreover, there is memory leak in this scenario.
```
      if (temp->data == t){
          if (temp->next != NULL){
              temp->next->next->prev = temp;
              temp->next = temp->next->next;
          }
      ....
      ....
```

All statements are making changes in temp->next pointer and not in temp pointer. Also, deleted node memory is not freed up anywhere.

Major: If the list has more than 1 elements in it and, for deletion, user entered last node, no deletion will happen and the last node will remain part of list. Its because of this in delele():
```
      if (temp->data == t){
          if (temp->next != NULL){
```

If temp is pointing to last node then temp->next will be NULL.

Minor: If the list has more than 1 elements in it and, for deletion, user entered some node which does not exists in the list than no output message to inform this to the user.

Problem in display() function:

Major: Pass NULL to display() function and it will give segmentation fault. This will be the case when your list will have only one element and that element will be deleted then the list will be empty and when display() will be called after delete(), it will result in segmentation fault. It's because of this in display():
```
  for (temp = head; temp->next != NULL; temp = temp->next)
                    ^^^^^^^^^^
```

If temp is NULL then it will attempt to access NULL pointer which is UB.

To delete a node in doubly linked list, you need to take care of it's previous and next pointer. The next of previous should be reset to its next node and previous of next should be reset to its previous node. If its previous is NULL that means its first node of the list and, in this case, reset the head of list to pointing to its next node.

Implementation:

void delete (int t) {
    struct node *temp;
    for (temp = head; temp != NULL && temp->data != t; temp = temp->next);

    if (temp == NULL) {
        printf("Target Element is Not Found\n");
        return;
    }

    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
        temp->prev = NULL;
    }
    else {
        head = temp->next;
    }

    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
        temp->next = NULL;
    }

    free (temp);
}

Need to fix the display as well. It should be like this:

void display (void) {
    struct node *temp;
    printf("List->");
    for (temp = head; temp != NULL; temp = temp->next)
        printf("%d ", temp->data);
    printf ("\n");
}

CodePudding user response：

To delete the element pointed to by cur, you need to redirect the pointer next of the previous and the pointer pred of the following, provided these elements exist. Get these elements with

node* pred= cur->pred, * next= cur->next;

Now shunt

(pred ? pred->next : head)= next;
(next ? next->pred : tail)= pred;

and release the current element:

delete cur;