Doubly circular linked list leaving trailing 0 at the end when deleting a node from start

Question

Can somebody please specify why this deleteB function is leaving a trailing 0 at the end after deleting. I tried this method out of curiosity.

I tried to access the previous pointer of head and making it's next pointer point to head->next instead of head.

After that I am changing the previous pointer of head->next and make it point to head->prev instead of head.

Finally I free the temp after changing the head.

Maybe method is wrong...Guide me if am wrong.

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

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

void deleteB(Node **head)
{
    if (*head != NULL)
    {
        if ((*head)->next == *head)
        {
            *head = NULL;
            return;
        }
        Node *temp = *head;
        (*head)->prev->next = (*head)->next;
        (*head)->next->prev = (*head)->prev;
        *head = (*head)->next;
        free(temp);
        // Node *curr = *head;
        // while (curr->next != *head)
        // {
        //  curr = curr->next;
        // }
        // curr->next = (*head)->next;
        // (*head)->next->prev = curr;
        // *head = (*head)->next;
        // free(temp);
    }
}

void prepend(Node **head, int value)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->data = value;
    if (*head == NULL)
    {
        *head = newNode;
        (*head)->next = *head;
        (*head)->prev = *head;
        return;
    }
    Node *temp = *head;
    while (temp->next != *head)
    {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
    newNode->next = *head;
    *head = newNode;
}

void append(Node **head, int value)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->prev = NULL;
    newNode->next = NULL;
    newNode->data = value;
    if (*head == NULL)
    {
        *head = newNode;
        (*head)->next = *head;
        (*head)->prev = *head;
        return;
    }
    Node *temp = *head;
    while (temp->next != *head)
    {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
    newNode->next = *head;
}

void display(Node *head)
{
    printf("\nPrinting the list: ");
    Node *temp = head;
    do
    {
        printf("-->%d", temp->data);
        temp = temp->next;
    } while (temp != head);
}

int main()
{
    Node *head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    append(&head, 4);
    // insertAtN(&head, 9, 1);
    deleteB(&head);
    display(head);
    printf("\n");
    return 0;
}

Answer 1

When inserting a node in a (non-empty, circular) doubly linked list, there are 4 pointers to set. Two pointing away from the new node, and two pointing to it. You missed one of the latter two:

(*head)->prev = newNode;

Some other remarks:

• prepend has the same code as append, with just one more statement following it. So avoid code repetition, and let prepend call append.

• Create a separate function just for constructing the new node

• Don't initialise the prev and next members as NULL, since that is never the value they should have in a circular list. Why not initialise them with a self reference... then there is at least a chance this will be the final value, and you'll never have to check if their value is NULL.

• In append (and prepend) there is no good reason why you should walk with temp forward along all the nodes of the list in order to find the last node, when you have a direct reference from the head node to that tail node! (prev)

• Don't cast the value returned by malloc

• display will have undefined behaviour when passing it an empty list. So add a guard.

Updated code:

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

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

void deleteB(Node **head)
{
    if (*head != NULL)
    {
        if ((*head)->next == *head)
        {
            *head = NULL;
            return;
        }
        Node *temp = *head;
        (*head)->prev->next = (*head)->next;
        (*head)->next->prev = (*head)->prev;
        *head = (*head)->next;
        free(temp);
    }
}

// Separate function, just to construct a node
Node *newNode(int value) 
{
    Node *node = malloc(sizeof(Node)); // Don't cast
    node->prev = node; // Circular list never has NULL here, so don't put it
    node->next = node;
    node->data = value;
    return node;
}

void append(Node **head, int value)
{
    Node *node = newNode(value);
    if (*head == NULL)
    {
        *head = node;
        return;
    }
    // We can find the tail with one step
    Node *tail = (*head)->prev;
    tail->next = node;
    node->prev = tail;
    node->next = *head;
    (*head)->prev = node; // This was missing
}

void prepend(Node **head, int value)
{
    append(head, value); // Code reuse
    *head = (*head)->prev;
}

void display(Node *head)
{
    printf("Printing the list: ");
    if (head == NULL) // Guard!
    { 
       return;
    }
    Node *temp = head;
    do
    {
        printf("-->%d", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

int main()
{
    Node *head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    append(&head, 4);
    deleteB(&head);
    display(head);
    return 0;
}