Linked List - C programming - CRUD Operations - with details

Linked List Basics

A linked list is the collection of a set of nodes that are connected continuously and those nodes contain its data(value) and address(the next link position). A linked list is a branch of linear data structure. It is mostly like an array but more than an array and it is faster also.



1. The first node is called the head node.

linked list node list


2. The last node is known as the tail node.

3. Every node contains an address except the last tail node.

Node is the merge block of data and address values in a linked list.


linked list node list



Why should we use a linked list but not an array?

1. The Linked list is made for the Dynamically Memory Allocation (DAM). The linked list dynamically allocates memory by directly accessing the address.

2. No need to be defined the size of a linked list.

3. It is faster than an array in all operations ( to insert data, to delete data, to search data, to update data).

4. As we know, a linked list directly accesses the memory location. So, the execution time to access the data in a linked list is very fast than an array.


Code for the Linked List 


#include <stdio.h>
#include <stdlib.h>
struct node{
    int key, data;
    struct node *next;
};
struct node *start = NULL;
struct node *current = NULL;
bool isEmpty()
{
    if(start == NULL)
        return true;
    return false;
}
void listInsert(int key, int data)
{
    struct node *item;
    item = (struct node *)malloc(sizeof(struct node));
    item->key = key;
    item->data = data;
    item->next = start;
    start = item;
}
void showList()
{
    if(isEmpty())
    {
        printf("List is Empty\n");
    }
    else
    {
        current = start;
        while(current != NULL)
        {
            printf("Key: %d\tData: %d\n", current->key, current->data);
            current = current->next;
        }
    }
}
void listDeleteByKey(int key)
{
    if(isEmpty())
    {
        printf("List is Empty\n");
    }
    else
    {
        struct node *prev = NULL;
        current = start;
        while(current != NULL)
        {
            if(current->key == key)
            {
                if(prev == NULL)
                {
                    start = current->next;
                }
                else
                {
                    prev->next = current->next;
                }
                break;
            }
            prev = current;
            current = current->next;
        }
        if(current == NULL)
            printf("Key NOT FOUND\n");
    }
}
void listDeleteByData(int data)
{
    if(isEmpty())
    {
        printf("List is Empty\n");
    }
    else
    {
        struct node *prev = NULL;
        current = start;
        while(current != NULL)
        {
            if(current->data == data)
            {
                if(prev == NULL)
                {
                    start = current->next;
                }
                else
                {
                    prev->next = current->next;
                }
                break;
            }
            prev = current;
            current = current->next;
        }
        if(current == NULL)
            printf("Data NOT FOUND\n");
    }
}
bool findByKey(int key)
{
    if(isEmpty())
    {
        printf("List is Empty\n");
    }
    else
    {
        current = start;
        while(current != NULL)
        {
            if(current->key == key)
            {
                return true;
            }
            current = current->next;
        }
        return false;
    }
}
bool findByData(int data)
{
    if(isEmpty())
    {
        printf("List is Empty\n");
    }
    else
    {
        current = start;
        while(current != NULL)
        {
            if(current->data == data)
            {
                return true;
            }
            current = current->next;
        }
        return false;
    }
}
int main()
{
    int c, choice, v;
    bool exit_flag = false;
    while(true)
    {
        printf("Enter Choice:\n");
        printf("1\t-\tDisplay\n");
        printf("2\t-\tSearch\n");
        printf("3\t-\tInsert\n");
        printf("4\t-\tDelete\n");
        printf("5\t-\tUpdate\n");
        printf("0\t-\tExit\n");
        scanf("%d", &choice);
        switch(choice)
        {
            case 1://display
                    showList();
                    break;
            case 2://search
                    printf("1 - By Key\n");
                    printf("2 - By Data\n");
                    scanf("%d", &c);
                    if(c == 1)
                    {
                        printf("Enter Key to Search: ");
                        scanf("%d", &v);
                        if(findByKey(v))
                            printf("Key %d FOUND!\n", v);
                        else
                            printf("Key %d NOT FOUND!\n", v);
                    }
                    else if(c == 2)
                    {
                        printf("Enter Data to Search: ");
                        scanf("%d", &v);
                        if(findByData(v))
                            printf("Data %d FOUND!\n", v);
                        else
                            printf("Data %d NOT FOUND!\n", v);
                    }
                    else
                        printf("Invalid Choice\n");
                    break;
            case 3://insert
                    printf("Enter (KEY, DATA): ");
                    scanf("%d %d", &c, &v);
                    listInsert(c, v);
                    printf("\nList after inserting (%d %d)\n", c, v);
                    showList();
                    printf("\n");
                    break;
            case 4://delete
                    printf("1 - By Key\n");
                    printf("2 - By Data\n");
                    scanf("%d", &c);
                    if(c == 1)
                    {
                        printf("Enter Key to Delete: ");
                        scanf("%d", &v);
                        listDeleteByKey(v);
                        printf("\nList after deleting key %d\n", v);
                        showList();
                        printf("\n");
                    }
                    else if(c == 2)
                    {
                        printf("Enter Data to Delete: ");
                        scanf("%d", &v);
                        listDeleteByData(v);
                        printf("\nList after deleting data %d\n", v);
                        showList();
                        printf("\n");
                    }
                    else
                        printf("Invalid Choice\n");
                    break;
            //case 5://update //Do it by yourself
             //       break;
            case 0://exit
                    exit_flag = true;
                    break;
            default:
                    printf("Invalid Choice\n");
        }
        if(exit_flag)
            break;
    }
    return 0;
}


The time complexity for the linked list

As it is made for the dynamical memory allocation, the time complexity is very low than other array operational algorithms. The time complexity is O (n) for accessing and searching data in the linked list. The best time complexity which is O (1) is found in the linked list. The update, insert, and delete operational time complexity in a linked list is O (1).

Post a Comment

Previous Post Next Post