Singly Linked List in C

This C Tutorial explains Different Operations Performed on a Singly Linked List in C Programming.

Let’s see an example of a C program that creates a singly linked list and performs various operations on it.

/* sll.c -- a realistic approach */
#include <stdio.h>
#include <stdlib.h>
 
/* Symbolic constants declared */
#define T 1
#define I 2
#define S 3
#define D 4
#define Q 5
#define TRAVERSE "enter 1 to TRAVERSE the list..."
#define INSERT "enter 2 to INSERT new value in the list..."
#define SEARCH "enter 3 to SEARCH a value in the list..."
#define DELETE "enter 4 to DELETE a value from the list..."
#define QUIT "enter 5 to QUIT the program..."
 
typedef struct NODE {
                     struct NODE *link;
                     int value;
        } Node;
 
/* function declarations */
int traverse(Node **);
void insert(Node **, const int);
int search(Node **, const int);
int delete(Node **, const int);
 
int main(void)
{
    Node *root = 0;
    Node **p2r = &root;
    Node *found = 0;
    int op = 0;
    int value = 0;
 
    printf("\n**Program Shows different operations on Singly "
            "Linked List.**\n");
    printf("\nUser, what operation do you want to do, now?\n\n");
    printf("%s\n%s\n%s\n%s\n%s\n: ",
            TRAVERSE, INSERT, SEARCH, DELETE, QUIT);
    while (1) {
        while (scanf("%d", &op) == 1) {
                if (op == T) {
                    op = traverse(p2r);
                }
 
                if (op == I) {
                    printf("User, enter integer value you want to "
                           "insert: ");
                    scanf("%d", &value);
                    insert(p2r, value);
                }
 
               if (op == S) {
                    printf("User, enter an integer value you wish to "
                           "search in the list...: ");
                    scanf("%d", &value);
                    op = search(p2r, value);
 
                    if (op == I) {
                        printf("User, enter integer value you want to "
                               "insert: ");
                        scanf("%d", &value);
                        insert(p2r, value);
                    }
                }
 
                if (op == D) {
                    printf("User, enter a value you wish to delete: ");
                    scanf("%d", &value);
                    op = delete(p2r, value);
 
                    if (op == I) {
                        printf("User, enter integer value you want to "
                               "insert: ");
                        scanf("%d", &value);
                        insert(p2r, value);
                    }
                }
 
                if (op == 5) {
                    printf("Thank You!\n");
                    return 0;
                }
 
                printf("\nUser, what operation do you want now?\n\n");
                printf("%s\n%s\n%s\n%s\n%s\n: ",
                        TRAVERSE, INSERT, SEARCH, DELETE, QUIT);
 
        }
   }
}
 
void insert(Node **linkp, const int value)
{
    Node *current;
    Node *new;
 
    while (((current = *linkp) != NULL) && (current->value < value))
            linkp = &current->link;
 
    /* firstly we verify if value is already in the list */
    if (current != NULL) {
        if (current->value == value) {
            printf("Value %d is already in the list!\n", value);
            printf("So, we don't INSERT value.\n");
            return ;
        }
    }
 
    /* Value isn't already in the list */
    /* Let's allocate it in proper place in the list */
    /* Allocate space to new */
    new = (Node *)malloc(sizeof(Node));
 
    /* Verify if allocation successful */
    if (new == NULL) {
        printf("Error: Memory Allocation Failed!\n");
        exit(EXIT_FAILURE);
    }
 
    /* write in value in the new */
    new->value = value;
 
    /* Insert value in the list */
        *linkp = new;
        new->link = current;
    printf("Value %d inserted successfully!\n", value);
}
 
int traverse(Node **linkp)
{
    Node *current = *linkp;
    int op = 0;
 
    /* Let's verify if list is Empty */
    if (current == NULL) {
        printf("\nList is EMPTY.\n");
        printf("So, you can either enter a value in the list or ");
        printf("QUIT the program.\nEnter 2 to INSERT value in the list, "
               "or enter 5 to QUIT.: ");
        while (scanf("%d", &op) == 1 && (op != I && op != Q))
            printf("Entered value is INCORRECT, enter CORRECT value: ");
 
        return op;
    }
    /* List isn't EMPTY, Traversing the list */
    else {
            printf("\nList is as follows: ");
            while (current != NULL) {
                    printf("%d ,", current->value);
                    current = current->link;
            }
            puts("\n");
            return op;
    }
}
int delete(Node **linkp, const int value)
{
    Node *current = *linkp;
    int op = 0;
 
    /* let's see if list is empty */
    if (current == NULL) {
        printf("List is empty.\n");
        printf("User, you can either enter an integer value or "
               "you can quit the program.\n");
        printf("Enter 2 to INSERT a value and enter 5 to QUIT the "
               "program: ");
        while (scanf("%d", &op) == 1 && (op != I && op != Q))
                 printf("You entered WRONG value! Please try again.\n");
 
        return op;
    }
    else {
        /* 
         * List isn't empty. We search through the entire list for 
         * desired value and once found, we'll delete the node
         * containing the value
         */
        while ((current = *linkp) != NULL && current->value != value)
                linkp = &current->link;
 
        /* now there are 2 cases, Either we've reached the end of list */
        if (current == NULL) {
           printf("We have reached the end of the List.\n");
           printf("Value %d is NOT in the list.\n", value);
           return op;
        }
        else if (current->value == value) {
                    printf("We have found value %d in the List.", value);
                    /*we delete the specified value from the list */
                    /* now we free up memory allocated to that node */
                    *linkp = current->link;
                    printf(" And deleted the value!\n");
                    /* set link field of previous node to point to 
                       node current->link points to */
                    free(current); 
                    /* free up current node back to free pool of memory */
                    return op;
        }
    }
}
 
int search(Node **linkp, const int value)
{
    Node *current = *linkp;
    int op = 0;
 
    /* Let's verify if list is Empty */
    if (current == NULL) {
        printf("\nList is EMPTY.\n");
        printf("So, you can either enter a value in the list or ");
        printf("QUIT the program.\nEnter 2 to INSERT value in the list, "
               "or enter 5 to QUIT.: ");
        while (scanf("%d", &op) == 1 && (op != I && op != Q))
            printf("Entered value is INCORRECT, enter CORRECT value: ");
 
        return op;
    }
    /* List isn't EMPTY, Searching value in the list */
    else {
            while ((current != NULL) && current->value != value)
                    current = current->link;
 
            if (current == NULL) {  /* reached end of list */
                printf(" %d is NOT in the list.\n", value);
                return op;
            }
            else {
                printf("%d is FOUND in the list.\n", value);
                return op;
            }
    }
}

Output of the above program for arbitrary choices is as follows,

 
**Program Shows different operations on Singly Linked List.**
 
User, what operation do you want to do, now?
 
enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 1
 
List is EMPTY.
So, you can either enter a value in the list or QUIT the program.
Enter 2 to INSERT value in the list, or enter 5 to QUIT.: 2
User, enter integer value you want to insert: 65
Value 65 inserted successfully!
 
User, what operation do you want now?
 
enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 2
User, enter integer value you want to insert: -87
Value -87 inserted successfully!
 
User, what operation do you want now?
 
enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 1
 
List is as follows: -87 ,65 ,
 
 
User, what operation do you want now?
 
enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 3
User, enter an integer value you wish to search in the list...: 55
 55 is NOT in the list.
 
User, what operation do you want now?
 
enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 3
User, enter an integer value you wish to search in the list...: 65
65 is FOUND in the list.
 
User, what operation do you want now?
 
enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 4
User, enter a value you wish to delete: 55
We have reached the end of the List.
Value 55 is NOT in the list.
 
User, what operation do you want now?
 
enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 4
User, enter a value you wish to delete: 65
We have found value 65 in the List. And deleted the value!
 
User, what operation do you want now?
 
enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 1
 
List is as follows: -87 ,
 
 
User, what operation do you want now?
 
enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 5
Thank You!

Notice various operations performed on Ordered Singly Linked List. Further, you can try writing all declarations in yours own header with .h extension and functions’ definitions in a separate file with .c extension to allow other programs to share those functions.

Sanfoundry Global Education & Learning Series – 1000 C Tutorials.

advertisement
advertisement
If you wish to look at all C Tutorials, go to C Tutorials.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.