Infinite memory addresses output when deleting node from circular doubly linked list

Question

I am trying to implement a function to delete a node from the end of a circular doubly linked list in C. However, when I run the code, it goes into an infinite loop and produces a continuous stream of memory addresses as output. I suspect there might be an issue with my deleteFromEnd() function. Could someone please review my code and help me identify the problem?

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node* next;
    struct node* prev;
} node;

void printList(node* head_ref) { // printing all the nodes
    if(head_ref == NULL) { // If there is no any node in the list
        printf("There are not nodes to print. Add nodes first!\n");
        return ;
    }
    node* tail = head_ref;
    do {
        printf("%d ", tail->data);
        tail = tail->next;
    } while(tail != head_ref);
    
    printf("\n");
}
void insertAtBeg(node** head_ref, int data) { // Insertion at the beginning
    node* newNode = (node*)malloc(sizeof(node));
    newNode->data = data;
    
    if(*head_ref == NULL) { // If there is no any node in the list, link to itself
        newNode->next = newNode;
        newNode->prev = newNode;
        *head_ref = newNode;
        return ;
    }
    node* tail = (*head_ref)->prev;
    
    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = *head_ref;
    *head_ref = newNode;
}

void deleteFromEnd(node** head_ref) { // Deletion from the end
    if(*head_ref == NULL) { // If there is no any node in the list
        printf("There are not nodes to print. Add nodes first!\n");
        return ;
    }

    node* tail = (*head_ref)->prev; // Last node of the list
    node* temp = (*head_ref)->prev; // The node we want to delete
    
    if (*head_ref == tail) { // If there is only one node in the list
        *head_ref = NULL;
        tail = NULL;
    }
    else {
        tail->prev->next = *head_ref;
        (*head_ref)->prev = tail->prev;
    }
    free(temp);
}
int main() {
    node* head = NULL;
    
    // Insertion at the beginning
    insertAtBeg(&head, 1);
    insertAtBeg(&head, 2);
    insertAtBeg(&head, 3);
    insertAtBeg(&head, 4);
    insertAtBeg(&head, 5);
    printList(head); // print all nodes
    
    // Deletion from the end
    
    deleteFromEnd(&head);
    printList(head);
    deleteFromEnd(&head);
    printList(head);
    deleteFromEnd(&head);
    printList(head); // print all nodes
    
    return 0;
}

Why do you think it has to do with deleteFromEnd()? There is no loop in the code you supplied us. Please update question with a minimal reproducible example so we at least know the code reproduces the problem at hand. — user9706
– user9706, Commented Jul 29, 2023 at 23:25
Good job revising the question. I get 5, 4, 3, 2, 1 and a segfault in printList() so I cannot reproduce the issue. — user9706
– user9706, Commented Jul 29, 2023 at 23:31
@AllanWind Thanks for your valuable comment! I tried to ask ChatGpt but it wasn't helpful, i hope there is someone able to show where we missed. — Tolga
– Tolga, Commented Jul 29, 2023 at 23:37

chux · Accepted Answer · 2023-07-30 01:27:14Z

At least these problems:

Missing update

In insertAtBeg(), the former head node's .prev is not updated.
Clue: 2 .prev and 2 .next members need updating. OP's code does 3 of these 4.

malloc() failure

Better to detect allocation failure.

void insertAtBeg(node** head_ref, int data) {
    node* newNode = (node*)malloc(sizeof(node));
    if (newNode == NULL) {
      TBD_code();
    }
    newNode->data = data;

Candidate alternative code with some additional minor changes (untested):

// Return error flag
bool insertAtBeg(node **head_ref, int data) { // Insertion at the beginning
  assert(head_ref);
  node *newNode = malloc(sizeof *newNode);
  if (newNode == NULL) {
    return true; // Failure
  }
  newNode->data = data;

  if (*head_ref == NULL) { // If there is no node in the list, link to self.
    newNode->next = newNode;
    newNode->prev = newNode;
  } else {
    newNode->next = *head_ref;
    newNode->prev = (*head_ref)->prev;
    (*head_ref)->prev->next = newNode;
    (*head_ref)->prev = newNode;
  }
  *head_ref = newNode;
  return false; // No error
}

Collectives™ on Stack Overflow

Infinite memory addresses output when deleting node from circular doubly linked list

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related