Doubly linked list in C- delete node function

Question

Doubly linked list nodes are created at the main function. Ender and header defined. Breaks at the delete node function- ender is null.

What's the best way to free the memory of the last and first input, i.e.: delete: 233,A and 888,F?

#include <stdafx.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>

typedef struct record {
    int idnumber;
    char initial;
    struct record *prevStudent;
    struct record *nextStudent;
} STUDENT;

STUDENT *header = NULL;  //pointer to the start of linked list
STUDENT *ender = NULL;   //pointer to the end of the linked list

void Makenode(int x, char y);
void deletenode();

int main() {
    Makenode(233, 'A');
    Makenode(456, 'H');
    Makenode(746, 'G');
    Makenode(888, 'F');
    deletenode();

    fflush(stdin);
    getchar();
    return 0;
}

void Makenode(int x, char y) {
    STUDENT *ptr;

    ptr = (STUDENT *)malloc(sizeof(STUDENT));
    if (ptr != NULL) {
        ptr->idnumber = x;
        ptr->initial = y;
        ptr->nextStudent = header;
        ptr->prevStudent = NULL;

        if (header == NULL)
            ender = ptr;
        else
            header->prevStudent = ptr;

        header = ptr;

    } else {
        printf("Memory not allocated\n");
    }
}

void deletenode() {
    //delete the first and the last node of the linked list
    STUDENT *p = header, *q = ender;
    char c;

    printf("Are you sure you want to delete Y/N:\n");
    fflush(stdin); c=getchar();
    while (c == 'Y' || c == 'y') {
        ender=ender->nextStudent;
        header=header->prevStudent;
        free(p); free(q);
    }
}

while (c == 'y') ... You never change c in that loop; if it is entered, it will loop forever. Did you mean to wrap that loop around c = getchar()? — M Oehm
– M Oehm, Commented Jun 3, 2014 at 13:49
Also, shouldn't header->prevStudent and ender->nextStudent be NULL by definition? — M Oehm
– M Oehm, Commented Jun 3, 2014 at 13:50
hi, my question is how do i correct my delete function to delete the first and the last node of the list? — user3703271
– user3703271, Commented Jun 3, 2014 at 14:57

M Oehm · Accepted Answer · 2014-06-03 18:20:59Z

Your delete function leaves the linked list in an ilegal state. At all times (except temporarily inside your insert and delete functions), the following must be true:

If the header is null, the ender must also be null and the list is empty.
If a node p has a non-null link to p->next, then p->next->prev == p.
Likewise, if a node p has a non-null link to p->prev, then p->prev->next == p.
The header has no previous node; the ender has no next node.

These are the invariants of your linked list.

If you check your code for deleting:

void deletenode()
{
    STUDENT *p = header, *q = ender;

    ender=ender->nextStudent;
    header=header->prevStudent;
    free(p); free(q);
}

you can see that you just set the header and ender to NULL, because that's what ender->nextStudent and header->prevStudent are. But even reversing that won't help, because you must update the adjacent nodes' links.

Here are two functions - one for each task - that work:

void delete_first()
{
    STUDENT *p = header;

    if (p) {
        if (p->nextStudent == NULL) {
            header = ender = NULL;
        } else {
            p->nextStudent->prevStudent = NULL;
            header = p->nextStudent;
        }
        free(p);
    }
}

void delete_last()
{
    STUDENT *p = ender;

    if (p) {
        if (p->prevStudent == NULL) {
            header = ender = NULL;
        } else {
            p->prevStudent->nextStudent = NULL;
            ender = p->prevStudent;
        }
        free(p);
    }
}

Collectives™ on Stack Overflow

Doubly linked list in C- delete node function

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