linkedList.c

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

// Self-referential Structure
struct listNode {
    char data;  // A character data in the list
    struct listNode *nextPtr;   // Pointer to next node
}; // end struct listNode

typedef struct listNode ListNode; // alias for the struct
typedef ListNode *ListNodePtr;  // alias for ListNode*

// Declarations
void insert(ListNodePtr *sPtr, char value);
char delete(ListNodePtr *sPtr, char value);
int isEmpty(ListNodePtr sptr);  // Memory!
void showList(ListNodePtr currentPtr); 
void showMenu(void);

int main() {
    // Initially, there are no nodes
    ListNodePtr startPtr = NULL;
    // User's choice
    unsigned int ch;
    // User's entered character
    char item;
    
    // Display the menu
    showMenu();
    printf("? ");
    scanf("%u", &ch);
    
    // Loop unless user chooses 3
    while(ch != 3) {
        switch(ch) {
            case 1:
                printf("Enter a character: ");
                scanf("\n%c", &item);
                
                // insert the item in list
                insert(&startPtr, item);
                showList(startPtr);
                break;
            case 2:
                // if list is not empty
                if(!isEmpty(startPtr)) {
                    printf("Enter character to be deleted: ");
                    scanf("\n%c", &item);
                    
                    // Remove the character if found
                    if (delete(&startPtr, item)) {
                        printf("%c deleted.\n", item);
                        showList(startPtr);
                    }
                    else {
                        printf("%c not found. \n\n", item);
                    }
                }
                else {
                    printf("The list is empty. \n");
                }
                
                break;
            default:
                printf("Invalid choice.\n");
                showMenu();
                break;
        }
        showMenu();
        printf("? ");
        scanf("%u", &ch);
    }
    printf("Thank You!\n");
    return 0;
}

// Display Menu Function
void showMenu(void) {
    printf("Enter your choice:\n"
        "   1 to insert element into the list.\n"
        "   2 to delete element from the list.\n"
        "   3 to end" );
}

// insert a new value into the list in sorted order
void insert(ListNodePtr *sPtr, char value) {
    ListNodePtr newPtr; // pointer to new node
    ListNodePtr previousPtr;    // pointer to previous node
    ListNodePtr currentPtr;     // pointer to current node
    
    newPtr = malloc(sizeof(ListNode)); // Create a node
    
    // if allocated
    if (newPtr != NULL) {
        newPtr->data = value;   // put value in the node
        newPtr->nextPtr = NULL; // doesn't have to link to another node
        
        previousPtr = NULL;
        currentPtr = *sPtr;
        
        // find the correct location in the list
        while(currentPtr != NULL && value > currentPtr->data) {
            previousPtr = currentPtr;
            currentPtr = currentPtr->nextPtr;
        }
        
        // insert new node at beginning of list
        if (previousPtr == NULL) {
            newPtr->nextPtr = *sPtr;
            *sPtr = newPtr;
        }
        else {
            previousPtr->nextPtr = newPtr;
            newPtr->nextPtr = currentPtr;
        }
    }
    else {
        printf("%c is not inserted. \n", value);
    }
}

// delete a list element
char delete(ListNodePtr *sPtr, char value) {
    ListNodePtr previousPtr;
    ListNodePtr currentPtr;
    ListNodePtr tmpPtr;
    
    // delete first node
    if (value == (*sPtr)->data) {
        tmpPtr = *sPtr; // hold onto node being removed
        *sPtr = (*sPtr)->nextPtr; // de-thread the node
        free(tmpPtr);   // free the de-threaded node
        return value;
    }
    else {
        previousPtr = *sPtr;
        currentPtr = (*sPtr)->nextPtr;
        
        // find the correct location in the list
        while (currentPtr != NULL && currentPtr->data != value) {
            previousPtr = currentPtr;
            currentPtr = currentPtr->nextPtr;
        }
        
        // delete node at currentPtr
        if (currentPtr != NULL) {
            tmpPtr = currentPtr;
            previousPtr->nextPtr = currentPtr->nextPtr;
            free(tmpPtr);
            return value;
        }
    }
    return '\0'; // NULL
}

// return 1 if the list is empty, otherwise 0
int isEmpty(ListNodePtr sPtr) {
    return sPtr == NULL;
}

// show the list
void showList(ListNodePtr currentPtr) {
    // if list is empty
    if (isEmpty(currentPtr)) {
        printf("The list is empty!\n");
    }
    else {
        printf("The list is: \n");
        
        // while not the end of list
        while(currentPtr != NULL) {
            printf("%c ==> ", currentPtr->data);
            currentPtr = currentPtr->nextPtr;
        }
        printf("NULL\n");
    }
}