Implement Linked List in C

Before starting to implement linked list in C, let’s see what self-referential structures are. Also, you need to know about dynamic memory allocation, which you can find here in this link. For example, let’s define a structure like below:

struct node {
    int data;
    struct node *nextPtr;
}; // end struct node

In the above struct node, we have two members, viz. integer member data and pointer member nextPtr. Also, the pointer points to same type struct node, hence the name self-referential structure. Moreover, it is also called a link.

Linked List in C

A linked list is a linear collection of self-referential structures, called nodes, connected by pointer links. That is why, the term ‘linked’ list. We can access a linked list via a pointer to the first node of the list. On the other hand, we access the subsequent nodes via the link pointer member which we store in each node. Finally, by convention, we set the link pointer in the last node to NULL to mark the end of the list. Also, we store the data dynamically in a linked list. Furthermore, a node can contain data of any type including other structs.

Implementation Example

Now, we are going to implement linked list in C, which stores a character in an alphabetical order.

#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");
    }
}

In the above example, we saw how we can perform insert and delete operations in linked list. It is all explained in the comments in the program. In a nutshell, you have to create a new node and point to its address from previous node. On the other hand, while deleting, you have to delete the node and set the nextPtr of previous node to NULL.

You can view the the code in the gist here.