Linked List Implementation in C with User Input

#c #datastructure #algorithms #beginners

Table of Content

Intro
Pre-requisites
What is LinkedList
Why are we using LinkedList
Implementing a LinkedList in C

If you are reading this article, I imagine you are starting your journey in data structures and algorithms. If that is the case, you are reading the right article. Before we begin, let me lay out some prerequisites - the terms and concepts we need to know to understand the concept of LinkedList fully.

Contiguous and non-contiguous memory blocks: In contiguous memory allocation, a single block of memory with a unique address is allocated to a file or process that needs it. In a Non-contiguous memory block, random memory blocks in different locations are allocated to the file or process. LinkedList falls into the latter. This is one of the core differences between LinkedList and array. Arrays are stored in contiguous memory locations.

Struct: It is a way to group related variables of different data types in C and other related languages.
Struct

Dynamic Memory Allocation Using Malloc: Since items in LinkedList are stored in random or different locations in machine memory, we will need to manipulate memory dynamically - on the fly. This brings us to the need to understand the standard c lib () function called malloc.

WHAT IS A LINKED LIST?

I imagine that at this point in your journey you are familiar with arrays. A linked list just like arrays is a linear data structure. You store data sequentially one after another. In an array however elements are stored in the same memory location, but in LinkedList elements are stored in different locations in memory. The elements of the list or the list items or NODES are stored in different memory locations. Each of these list item or node contain two things:

The data - can be any data type
Memory address to next item or node - a pointer

WHY USED A LINKED LIST?

Dynamic Size: Linked lists have variable sizes. Arrays have fixed sizes. If for your purpose number or volume of data will be varying during program runtime, it is fair to use LinkedList.
Faster Insertion and Deletion: With LinkedList insertion and deletion operations are faster or more compute-efficient. If you will be doing lots of insertion and deletion on your data, then LinkedList is better.

IMPLEMENTING A LINKED LIST
Okay in this part of this article, we will write a code in C language to implement a LinkedList. It will take multiple data from the user and use them to create a LinkedList. The first data it will require and get from the user is several data for the list to hold. Then It will prompt the user to input data until it equals the number of the data defined by the user. Next, the program will print out everything.

Now let's begin.
Step 1. First, create a C project in code blocks IDE. Inside the

main.c file: 
#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data; //data of the node
    struct node *nextPtr; //address of the next node
};

In the above code, we imported standard C libraries we will need for this program and also created a node for our list. The node has two variables - an int variable to store the data. And another variable is to store a pointer(memory address) to the next node or list item.

Step 2:

struct node *startNode;

//function to create the list
static void createNodeList(int totalNodes);
static void displayList();

We declared a pointer to the starting node.and also created two function prototypes. The first function will create the linkedList. The second one will print it.

Step 3:

int main()
{
    int numberOfNodes;

    printf("Input the number of nodes: ");
    scanf("%d ", &numberOfNodes);
    createNodeList(numberOfNodes);
    displayList();
    return 0;
}

Main function is the entry point to every C program. So We created our main function and inside the main function, we declared an int variable numberOfNodes to hold the number of nodes for the list. Next, we print the user to enter the max number of nodes the list will contain, which we will store in the already declared variable.

Step 4:

static void createNodeList(int totalNodes)
{
    struct node *newNode;
    struct node *nodeBuffer;
    int nodeData;
    int nodeCounter;

    //allocate memory for starting node
    startNode = (struct node*)malloc(sizeof(struct node));

   //at this point you can check if the memory allocation is      
   //and stop the program if not 
}

In step four I started defining the first function. I created a number of variables, first of struct node type to hold new nodes. Next one is a buffer. The next node data, and node counter.
Next, I allocated memory to the starting node using malloc. Note the comment. I jumped that.

Step 5:

printf("input data for node1: ");
        scanf("%d", &nodeData);

        //save user input to the data element of the node
        startNode->data = nodeData;
        //initialize the nodes next pointer to null
        startNode->nextPtr = NULL;
        //Point the buffer to address of the first node
        nodeBuffer = startNode;

You have requested for the first user input and assigned it to a node. The thing is to use a for loop to get the rest. A linked list with one node containing data basically has two nodes. So….

Step 6:

for(nodeCounter =2; nodeCounter<=totalNodes; nodeCounter++)
        {

            newNode = (struct node*)malloc(sizeof(struct node));

            //exit if new node cannot be allocated
            if(newNode == NULL)
            {
                printf("Memory cannot be allocated.");
                break;
            }
            else
            {
                printf("input data for node %d: ",nodeCounter);
                scanf("%d", &nodeData);

                newNode->data = nodeData;
                newNode->nextPtr = NULL;

                //Link the previous node to the current node
                nodeBuffer->nextPtr = newNode;
                //copies address of current node
                nodeBuffer = nodeBuffer->nextPtr;
            }

        }

NB: code up to this point is still inside the CreateNodelist function we started in step 4.

The next thing we need to do now is to create a function that will print out our node list to the console.

Step 7:

static void displayList(){
    struct node *nodeBuffer;
    nodeBuffer = startNode;
    //exit if it is empty
    if(nodeBuffer == NULL){
        printf("List is empyt");
        return 0;
    }
    else{
        //check if the current node is empty
        while (nodeBuffer != NULL)
        {
            //PRINT THE DATA OF CRRENT NODE
            printf("DATA: %d \n", nodeBuffer->data);
            //go to the next node
            nodeBuffer = nodeBuffer->nextPtr;
        }
    }
}

In this article you must have learn the things you need to understand to understand linkedlist, also what a linkedlist is, the difference between linkedlist and array and why we use linkedlist.

References:
Image Credit goes to Geekforgeeks
Useful Resource:
Source Code: Here

I am Vincent Ikechukwu, Full Stack Web Developer and Software Engineer. Connect with me on social media via links below