how to delete node from doubly-linked list

Question

I am currently trying to delete a Node from a doubly linked list, but when only one item is left it throws an access violation exception upon attempting to delete it on line 11 (*sPtr)->prevPtr = NULL;. This is my current delete function:

char del(ListNodePtr *sPtr, char value)
{
    ListNodePtr previousPtr; /* pointer to previous node in list */
    ListNodePtr currentPtr; /* pointer to current node in list */
    ListNodePtr tempPtr; /* temporary node pointer */

    /* delete first node */
    if (value == (*sPtr)->data) {
        tempPtr = *sPtr; /* hold onto node being removed */
        *sPtr = (*sPtr)->nextPtr; /* de-thread the node */
        (*sPtr)->prevPtr = NULL;
        if ((*sPtr)->nextPtr != NULL) {
            free(tempPtr); /* free the de-threaded node */
        }
        return value;
    } /* end if */
    else {
        previousPtr = *sPtr;
        currentPtr = (*sPtr)->nextPtr;

        /* loop to find the correct location in the list */
        while (currentPtr != NULL && currentPtr->data != value) {
            previousPtr = currentPtr; /* walk to ...   */
            currentPtr = currentPtr->nextPtr; /* ... next node */
        } /* end while */

          /* delete node at currentPtr */
        if (currentPtr != NULL) {
            tempPtr = currentPtr;
            previousPtr->nextPtr = currentPtr->nextPtr;
            free(tempPtr);
            return value;
        } /* end if */
    } /* end else */

    return '\0';
}

EDIT: I am going to add my main function and my print function in that order below for better context of what I am trying to do so that my question can be reopened:

here is my main function with my listNode struct:

struct listNode {
    char data; /* each listNode contains a character */
    struct listNode *nextPtr; /* pointer to next node*/
    struct listNode *prevPtr; /* pointer to previous node*/
}; /* end structure listNode */

typedef struct listNode ListNode; /* synonym for struct listNode */
typedef ListNode *ListNodePtr; /* synonym for ListNode* */

        /* prototypes */
void insert(ListNodePtr *sPtr, char value);
char del(ListNodePtr *sPtr, char value);
int isEmpty(ListNodePtr sPtr);
void printList(ListNodePtr currentPtr);
void printReverse(ListNodePtr currentPtr);
void instructions(void);

int main(void)
{
    ListNodePtr startPtr = NULL; /* initially there are no nodes */
    int choice; /* user's choice */
    char item; /* char entered by user */

    instructions(); /* display the menu */
    printf("? ");
    scanf("%d", &choice);

    /* loop while user does not choose 3 */
    while (choice != 3) {

        switch (choice) {
        case 1:
            printf("Enter a character: ");
            scanf("\n%c", &item);
            insert(&startPtr, item); /* insert item in list */
            printList(startPtr);
            printReverse(startPtr);
            break;
        case 2:
            /* if list is not empty */
            if (!isEmpty(startPtr)) {
                printf("Enter character to be deleted: ");
                scanf("\n%c", &item);

                /* if character is found, remove it */
                if (del(&startPtr, item)) { /* remove item */
                    printf("%c deleted.\n", item);
                    printList(startPtr);
                    printReverse(startPtr);
                } /* end if */
                else {
                    printf("%c not found.\n\n", item);
                } /* end else */
            } /* end if */
            else {
                printf("List is empty.\n\n");
            } /* end else */

            break;
        default:
            printf("Invalid choice.\n\n");
            instructions();
            break;
        } /* end switch */

        printf("? ");
        scanf("%d", &choice);
    } /* end while */

    printf("End of run.\n");
    return 0; /* indicates successful termination */
} /* end main */

and here are my printReverse and printList functions:

void printList(ListNodePtr currentPtr)
{

    /* if list is empty */
    if (currentPtr == NULL) {
        printf("List is empty.\n\n");
    } /* end if */
    else {
        printf("The list is:\n");

        /* while not the end of the list */
        while (currentPtr != NULL) {
            printf("%c --> ", currentPtr->data);
            currentPtr = currentPtr->nextPtr;
        } /* end while */

        printf("NULL\n\n");
    } /* end else */
} /* end function printList */

void printReverse(ListNodePtr currentPtr)
{
    /* if list is empty */
    if (currentPtr == NULL) {
        printf("List is empty.\n\n");
    } /* end if */
    else {
        printf("The list in reverse is:\n");

        while (currentPtr->nextPtr != NULL)
            currentPtr = currentPtr->nextPtr;

        /* while not the beginning of the list */
        while (currentPtr != NULL) {
            printf("%c --> ", currentPtr->data);
            currentPtr = currentPtr->prevPtr;
        } /* end while */

        printf("NULL\n\n");
    } /* end else */
} /* end function printList */

I really hope this makes it more clear on everything that is happening because I have been stuck on this for the last 3 days and there are little to no topics I can find online that talk about how to do what I'm doing, because the list is sorted alphabetically on insertion and deletion.

So if anyone can attempt to tell me what is wrong and why it throws an access violation exception on line 11 when trying to delete the last item in the list I would be ever so grateful. Thanks!

Not checked, it is probably because `(*sPtr)->nextPtr`, which is assinged to `*sPtr`, was `NULL` because only one node is left. — MikeCAT, Apr 30 '16 at 02:48
if you don't have head (for a singly linked list) and tail (both for a doubly linked list) pointers, I would highly recommend them. I don't know how anyone does linked lists without them. Inserting and deleting nodes is a special case when you have 0 or 1 elements in the list, which I think is much easier when you maintain head and tail pointers. Although having said that I'm sure somebody here can get fancy and do linked lists without them. — yano, Apr 30 '16 at 03:04
@yano is there a way to do it without creating a head and tail pointer? thanks in advance! :) — Ian Lundberg, Apr 30 '16 at 06:04
Your title says 'doubly-linked list' but your code only manipulates the `nextPtr` — do you have a singly-linked or doubly-linked list? Is your list circular or 'null-terminated'? That is, does the `nextPtr` of the last item contain a NULL pointer, or does it point back to the start of the list (and if it is a doubly-linked list, does the previous pointer of the first item point to the tail of the list or is that NULL)? Please note that for these sorts of reasons, it is highly desirable to post an MCVE ([MCVE]) — so that we don't have to ask such questions. — Jonathan Leffler, Apr 30 '16 at 06:40
@JonathanLeffler yeah that's my problem! I can't figure out how to get the delete function to work for a doubly linked list. I also apologize for the lack of information. I updated the post and hopefully it has enough information now for you and others to understand what I am trying to do better — Ian Lundberg, Apr 30 '16 at 13:03
Well, for a doubly linked-list I suppose you could simply keep track of a "current" element, then traverse to the beginning from there using the `prev` pointer and traverse to the end using the `next` pointer. I've never done this, but no brick walls come to mind thinking about it. As J Leffler points out, "beginning" and "end" are defined differently if you're talking about a null-terminated or circular list. But this seems silly to me. The extra bookkeeping that's needed for head and tail pointers is well worth it in my opinion, unless you have a very good reason for not wanting to use them. — yano, Apr 30 '16 at 20:48

score 1 · Answer 1 · edited May 23 '17 at 12:23

Your code does not check whether the new head node is null after deleting the last node, so the code crashes when you try to set the head node's next pointer to null.

Fixed code (runs leak-free and error-free under valgrind):

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

struct listNode
{
    char data;
    struct listNode *nextPtr;
    struct listNode *prevPtr;
};

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void insert(ListNodePtr *sPtr, char value);
char del(ListNodePtr *sPtr, char value);
int isEmpty(ListNodePtr sPtr);
void printList(ListNodePtr currentPtr);
void printReverse(ListNodePtr currentPtr);

static void ins_check(ListNode **list, char c)
{
    printf("Inserting [%c] (%p)\n", c, (void *)*list);
    insert(list, c);
    printList(*list);
    printReverse(*list);
}

static void del_check(ListNode **list, char c)
{
    printf("Deleting [%c] (%p)\n", c, (void *)*list);
    if (del(list, c) != c)
        printf("Did not find [%c] in list.\n", c);
    printList(*list);
    printReverse(*list);
}

int main(void)
{
    ListNodePtr startPtr = NULL;

    printList(startPtr);
    printReverse(startPtr);

    ins_check(&startPtr, 'a');
    ins_check(&startPtr, 'b');
    ins_check(&startPtr, 'c');

    del_check(&startPtr, 'c');
    del_check(&startPtr, 'a');
    del_check(&startPtr, 'b');

    assert(startPtr == 0);

    printf("End of run.\n");
    return 0;
}

void printList(ListNodePtr currentPtr)
{
    if (currentPtr == NULL)
        printf("List is empty.\n");
    else
    {
        printf("The list is: ");
        while (currentPtr != NULL)
        {
            printf("%c --> ", currentPtr->data);
            currentPtr = currentPtr->nextPtr;
        }
        printf("NULL\n");
    }
}

void printReverse(ListNodePtr currentPtr)
{
    if (currentPtr == NULL)
        printf("List is empty (even in reverse).\n");
    else
    {
        printf("The list in reverse is: ");
        while (currentPtr->nextPtr != NULL)
            currentPtr = currentPtr->nextPtr;
        while (currentPtr != NULL)
        {
            printf("%c --> ", currentPtr->data);
            currentPtr = currentPtr->prevPtr;
        }
        printf("NULL\n");
    }
}

char del(ListNodePtr *sPtr, char value)
{
    ListNodePtr previousPtr;
    ListNodePtr currentPtr;
    ListNodePtr tempPtr;

    assert(*sPtr != 0);
    if (value == (*sPtr)->data)
    {
        tempPtr = *sPtr;
        printf("Deleting 1: [%c] (node = %p, next = %p, prev = %p\n", tempPtr->data,
                (void *)tempPtr, (void *)tempPtr->nextPtr, (void *)tempPtr->prevPtr);
        *sPtr = (*sPtr)->nextPtr;
        if (*sPtr != 0)   // Crucial change!
            (*sPtr)->prevPtr = NULL;
        free(tempPtr);
        return value;
    }
    else
    {
        previousPtr = *sPtr;
        currentPtr = (*sPtr)->nextPtr;

        while (currentPtr != NULL && currentPtr->data != value)
        {
            previousPtr = currentPtr;
            currentPtr = currentPtr->nextPtr;
        }

        if (currentPtr != NULL)
        {
            assert(previousPtr != 0);
            tempPtr = currentPtr;
            printf("Deleting 2: [%c] (node = %p, next = %p, prev = %p\n", tempPtr->data,
                    (void *)tempPtr, (void *)tempPtr->nextPtr, (void *)tempPtr->prevPtr);
            previousPtr->nextPtr = currentPtr->nextPtr;
            free(tempPtr);
            return value;
        }
        else
            printf("Did not find [%c]\n", value);
    }

    return '\0';
}

void insert(ListNode **list, char value)
{
    ListNode *node = malloc(sizeof(*node));
    if (node == 0)
    {
        fprintf(stderr, "Out of memory\n");
        exit(EXIT_FAILURE);
    }
    node->data = value;
    node->nextPtr = 0;
    node->prevPtr = 0;
    if (*list != 0)
    {
        node->nextPtr = *list;
        assert((*list)->prevPtr == 0);
        (*list)->prevPtr = node;
    }
    *list = node;
}

Example run:

List is empty.
List is empty (even in reverse).
Inserting [a] (0x0)
The list is: a --> NULL
The list in reverse is: a --> NULL
Inserting [b] (0x7fccc3503070)
The list is: b --> a --> NULL
The list in reverse is: a --> b --> NULL
Inserting [c] (0x7fccc3503090)
The list is: c --> b --> a --> NULL
The list in reverse is: a --> b --> c --> NULL
Deleting [c] (0x7fccc35030b0)
Deleting 1: [c] (node = 0x7fccc35030b0, next = 0x7fccc3503090, prev = 0x0
The list is: b --> a --> NULL
The list in reverse is: a --> b --> NULL
Deleting [a] (0x7fccc3503090)
Deleting 2: [a] (node = 0x7fccc3503070, next = 0x0, prev = 0x7fccc3503090
The list is: b --> NULL
The list in reverse is: b --> NULL
Deleting [b] (0x7fccc3503090)
Deleting 1: [b] (node = 0x7fccc3503090, next = 0x0, prev = 0x0
List is empty.
List is empty (even in reverse).
End of run.

Note the use of wrapper functions (ins_check() and del_check()) and the use of fixed data to make it easy to test (no input required). Also note the printing of what's going on.

I'm hoping your insert() is somewhat similar to the one I devised — a true MCVE (How to create a Minimal, Complete, and Verifiable Example?) or SSCCE (Short, Self-Contained, Correct Example) would have provided that function.

Note that the 'new' code obeys the strictures suggested by Is it a good idea to typedef pointers — the succinct answer is "No" (for non-opaque data pointers).

Note that your delete function is as complicated as as necessary for a singly-linked list, but can be a lot simpler because each node in a doubly-linked list knows its own predecessor. This version also works cleanly:

char del(ListNodePtr *sPtr, char value)
{
    assert(*sPtr != 0);
    ListNode *curr = *sPtr;
    while (curr != NULL)
    {
        if (curr->data == value)
        {
            if (curr->prevPtr != NULL)
                curr->prevPtr->nextPtr = curr->nextPtr;
            if (curr->nextPtr != NULL)
                curr->nextPtr->prevPtr = curr->prevPtr;
            if (*sPtr == curr)
                *sPtr = curr->nextPtr;
            free(curr);
            return value;
        }
        curr = curr->nextPtr;
    }

    printf("Did not find [%c]\n", value);
    return '\0';
}

score 0 · Accepted Answer · answered Apr 30 '16 at 17:20

I think you've made things too complicated. You don't separate the "list" type from the "node" type, but I think you can get by without passing pointers-to-pointers if you just return a replacement.

You might want to write a "find" method to handle looking up the character and returning a pointer to that node.

/**
  Delete the node containing value from the list starting with start.
  If value is not found in list, then the list is unchanged. Returns
  a replacement value for start, which may be needed if the value is
  contain in the start node.
*/

ListNodePtr  del(ListNodePtr start, char value)
{
    ListNodePtr curr;

    for (curr = start; curr && curr->data != value; curr = curr->nextPtr) {
        // skip this node
    }

    if (!curr) {
        // Value not found in list. List is unchanged.
        return start;
    }

    /* Compute return value */

    if (curr == start) {
        start = start->nextPtr;
    }

    /* Remove curr node from chain */

    if (curr->prevPtr) {
        curr->prevPtr->nextPtr = curr->nextPtr;
    }

    if (curr->nextPtr) {
        curr->nextPtr->prevPtr = curr->prevPtr;
    }

    free(curr);
    return start;
}

score 0 · Answer 3 · answered Apr 30 '16 at 17:36

I ended up realizing my problem. Visual Studio wasn't letting me use breakpoints, but that was because I didn't realize I had it set to "Release" and not "Debug". So doing that I tracked the pointers to figure out where they became unlinked or linked to the wrong ones and came up with this solution:

  /* Delete a list element */
char del(ListNodePtr *sPtr, char value)
{
    ListNodePtr previousPtr; /* pointer to previous node in list */
    ListNodePtr currentPtr; /* pointer to current node in list */
    ListNodePtr tempPtr; /* temporary node pointer */

    /* delete first node */
    if (value == (*sPtr)->data) {
            tempPtr = *sPtr; /* hold onto node being removed */
            *sPtr = (*sPtr)->nextPtr; /* de-thread the node */
            if(*sPtr != NULL) /* if the list is not empty */
                (*sPtr)->prevPtr = NULL; /* the previos pointer is null*/
            free(tempPtr); /* free the de-threaded node */
            return value;
    } /* end if */
    else {
        previousPtr = *sPtr;
        currentPtr = (*sPtr)->nextPtr;

        /* loop to find the correct location in the list */
        while (currentPtr != NULL && currentPtr->data != value) {
            previousPtr = currentPtr; /* walk to ...   */
            currentPtr = currentPtr->nextPtr; /* ... next node */
        } /* end while */

          /* delete node at currentPtr */

        if (currentPtr != NULL) {
            tempPtr = currentPtr;
            previousPtr->nextPtr = currentPtr->nextPtr;
            if(previousPtr->nextPtr != NULL) /* if the next pointer isn't null */
                previousPtr->nextPtr->prevPtr = currentPtr->prevPtr; /* the previous pointer of the next pointer is the previous pointer of the current pointer */
            free(tempPtr);
            return value;
        } /* end if */

    } /* end else */
    return '\0';
} /* end function delete */

how to delete node from doubly-linked list

3 Answers3