alphabetically sorted insertion into doubly-linked list

Question

I am currently trying to create a doubly linked list that sorts the inserted char value alphabetically, however it is not updating the previous nodes properly because of the loop used to compare data values.

This is my current insert code:

void insert(ListNodePtr *sPtr, char value)
{
    ListNodePtr newPtr; /* pointer to new node */
    ListNodePtr previousPtr; /* pointer to previous node in list */
    ListNodePtr currentPtr; /* pointer to current node in list */

    newPtr = (ListNode*)malloc(sizeof(ListNode)); /* create node */

    if (newPtr != NULL) { /* is space available */
        newPtr->data = value; /* place value in node */
        newPtr->nextPtr = NULL; /* node does not link to another node */
        newPtr->prevPtr = NULL;

        previousPtr = NULL;
        currentPtr = *sPtr;

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

          /* insert new node at beginning of list */
        if (previousPtr == NULL) {
            newPtr->nextPtr = *sPtr;
            *sPtr = newPtr;
        } /* end if */
        else { /* insert new node between previousPtr and currentPtr */
            previousPtr->nextPtr = newPtr;
            newPtr->prevPtr = previousPtr;
            newPtr->nextPtr = currentPtr;
        } /* end else */
    } /* end if */
    else {
        printf("%c not inserted. No memory available.\n", value);
    } /* end else */
} /* end function insert */

here is my node structure:

/* self-referential structure */
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* */

and here is my print function:

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 */

and here is the output that I get:

output when entering chars in ascending order of ASCII value it works properly

but when I add a larger value and then a value smaller than that one it does not print the correct previous value.

I have been working on this for the last few days trying to figure out what to do, but I cannot find any related situations that others have been in so I would appreciate any help that I can get. Thanks!

P.S. This is a hw assignment and I normally wouldn't ask for help with it, but the book says nothing about doubly-linked lists and even less on how to insert data alphabetically with them so I am just really desperate for help right now and I will gladly take any info I can get to point me in the right direction!

Mike Holt Mike Holt · Accepted Answer · 2016-04-30T01:08:07

You are forgetting to assign one a pointer. Since this is a HW assignment, I'll just give you a hint. Think about all the cases for insertion. You should count four cases, depending on whether previousPtr and currentPtr are NULL after your while loop in the insert function:

Both previousPtr and currentPtr are NULL. (empty list)
Only previousPtr is NULL. (you are prepending to the list)
Only currentPtr is NULL. (you are appending to the list)
Neither previousPtr nor currentPtr are NULL. (inserting between two existing nodes)

Your code handles cases 1-3 properly, but fails on case 4 because you haven't assigned all the pointers that you need to assign. With a doubly-linked list, there are four pointers that need to be assigned for case 4: previousPtr->next, newNode->prevPtr, newNode->nextPtr, and ????.

alphabetically sorted insertion into doubly-linked list

1 Answers