Linked List in C

As my specification in engineering was Electronics, I never got an opportunity to study Data Structures during my college days. When I started my career I had to undergo training provided by the company. Data structure was part of that training. A session was taken on Linked List as it is a data structure. Conceptual wise I understood linked list very well, but somehow I was facing trouble while coding. I reached a stage where I started hating linked list and skipped using it by using files instead.

As one get into real time projects one can see the code filled up with the usage of Linked List. Always I could point my weakness whenever I was browsing the code. If I do not like my weakness I should overcome it. Then I decided to learn linked list in a way I do not forget it. I started searching in net, visited different sites, walked through many blogs. Finally I reached a state where I got clear understanding of Linked list. That time I could hear an inner voice saying “Nothing is impossible”

Story apart. Let me explain you what I have understood about Linked list.

One should understand the meaning of data structure before stepping into linked list. Data structure is way of storing data and organizing it. By doing this data can be used efficiently. 

Linked list is a data structure. It is a group of Nodes linked together. Node is a template which contains one or more fields which again linked with other nodes.

NODE

Data 1

Data 2

Address of Next Node

In the above table you can see Node contains 3 fields totally. It contains 2 data members and 1 link. 

Link contains address of next node. The variable which stores address of another variable is a pointer. Pointer does the job of storing address of next node.

Assume an application requires storing names of 5 students and their ID number.  Let us see how to implement using Linked list.

Linked list stores data in below format for the above application.

Assume address of first NODE is 96b9010.

Here Data 1 holds name of student; Data 2 holds ID number of the student. Link holds address of next node. When you observe the fifth node, you can notice Link node has value NULL. This means end of linked list. No more nodes to point.

In terms of programming let us create a NODE template. NODE template is given below.

=========================================================================

Struct node

{

                Char studentName[50];

                Char studentIDNumber[10];

                Struct node *next;

}

Struct node *head;

=========================================================================

Node is the name of the structure.

studentName is array of characters which holds name of a student.

studentIDNumber is again array of characters which holds ID number of a student.

Next holds the address of next node. It is a pointer of type struct node. Generally for integer variable you take integer pointer, for char character pointer. So here is it pointer of type struct node.

Head is the pointer of type struct node through which one can access structure members [variables].

 

Below is the C code which does the job.

=========================================================================

#include <stdio.h>

#include <stdlib.h>

void createLinkedList(char Name[50],char IDNumber[10]);

void addFirstData(char Name[50],char IDNumber[10]);

void addDataAtEnd(char Name[50],char IDNumber[10]);

void displayLinkedList();

/***********************************************************

node: A node with two members

data: variable

next: contains address of next node

***********************************************************/

struct node

{

        char studentName[50];

        char studentIDNumber[10];

        struct node *next;

};

/**********************************************************

head: Pointer of type struct node

***********************************************************/

struct node *head;

/**********************************************************

main: Main function that invokes createLinkedList function.

***********************************************************/

int main()

{

        unsigned int count = 0;         /*Loop count*/

        unsigned int maxCount = 5;      /*Loop for 5 times*/

        char Name[50];                         /* Local variable that holds name of student */

        char IDNumber[10];                /* Local variable that holds ID Number of a student */

        for(count = 0; count < maxCount; count++)

        {

                printf("Please enter name of student %d\n",count+1);

                gets(Name);

                printf("Please enter ID number of student %d\n",count+1);

                gets(IDNumber);

                createLinkedList(Name,IDNumber);        /*Function that invokes Linked list creation*/

        }

        displayLinkedList();                    /*Function that displays created Linked List*/

        return 0;

}

/*********************************************************************************

createLinkedList: Function that invokes linked list creation

If createLinkedList fuction is called for the  first time it inturn calls addFirstData.

Else it calls addDataAtEnd.

*********************************************************************************/

void createLinkedList(char Name[50],char IDNumber[10])

{

        if(head == NULL)                        /*For the first time[first loop] linked list node will be empty*/

        {

                addFirstData(Name,IDNumber);

        }

        else

        {

                addDataAtEnd(Name,IDNumber);

        }

}

/********************************************************************************

addFirstData: Adds first data member.

********************************************************************************/

void addFirstData(char Name[50],char IDNumber[10])

{

        head = (struct node *)malloc(sizeof(struct node));      /*Allocates memory to node */

        strcpy(head->studentName,Name);

        strcpy(head->studentIDNumber,IDNumber);

        head->next = NULL;                               /*As this is the First item pointing next to NULL */

}

/********************************************************************************

addDataAtEnd: Except first data member rest are added through this function.

This function insert node at the end of Linked list.

********************************************************************************/

void addDataAtEnd(char Name[50],char IDNumber[10])

{

        struct node *temp1;

        struct node *temp2;

        temp2 = (struct node *)malloc(sizeof(struct node));     /*Allocates memory to temporary node */

        strcpy(temp2->studentName,Name);

        strcpy(temp2->studentIDNumber,IDNumber);

        temp2->next = NULL;

        temp1 = head;                                           /*Assigning head contents to temp1*/

        while(temp1->next != NULL)                              /*Trverse till end of Linked List*/

        {

                temp1 = temp1->next;

        }

        temp1->next = temp2;                                    /*point temp1->next to temp2 node */

}

/********************************************************************************

displayLinkedList: Displays data members of created linked list

This function displays the created list.

********************************************************************************/

void displayLinkedList()

{

        struct node *temp;

        unsigned int count = 1;

        temp = head;

        printf("\n");

        while(temp != NULL)

        {

        printf("Data in node %d is %s %s\n",count++,temp->studentName,temp->studentIDNumber);

        temp = temp->next;

        }

        printf("\n%d",sizeof(struct node));

}

=========================================================================

When you run the above code below output will be generated.

Please enter name of student 1

Shilpa

Please enter ID number of student 1

S100101

Please enter name of student 2

Prutha

Please enter ID number of student 2

S100102

Please enter name of student 3

Bhavana

Please enter ID number of student 3

S100103

Please enter name of student 4

Swathi

Please enter ID number of student 4

S100104

Please enter name of student 5

Sireesha

Please enter ID number of student 5

S100105

Data in node 1 is Shilpa S100101

Data in node 2 is Prutha S100102

Data in node 3 is Bhavana S100103

Data in node 4 is Swathi S100104

Data in node 5 is Sireesha S100105