Data Structures And Algorithms in C

C language is one of the most flexible and simple languages. So, it is always better to learn any concept in C language compared to other languages. Let us look into the data structures and algorithms in C. Before moving ahead, and we need to know the data structure.

Data structures

Data structures are made up of two words one is data, and the other one is structure. We all know that data is a piece of normal information stored in a device. Data can be in any format, numbers, characters, etc. And structure means arranging the data, so entirely Data Structure means it is an efficient way of arranging data in a system. If we think why Data Structure is necessary, the one good answer is using data structures, we can save a huge amount of memory and CPU utilization. We have two different types of data structures: a linear data structure and the second is a nonlinear data structure.

Let's have a look at the linear data structure.

Linear Data Structure

Linear data structure arranges the data sequentially in a specific order, simply one after another. Here every element has two neighbors. One is the left neighbor, and another one is the right neighbor. Some good examples of linear data structures are a linked list stack and queue. Linear data structures are widely used in software development.

Nonlinear Data Structure

In the nonlinear data structure, all the elements are attached hierarchically. For Example, in trees and graphs and nonlinear data structures, there are multiple levels compared to Linear data structures, and nonlinear data structures use the memory very efficiently. Nonlinear data structures are highly used in artificial intelligence and also best fit for the image processing. We can have a clear idea of all the data structures before that let us know the algorithms' basics.

Algorithm

An algorithm is a step-by-step process of solving a particular problem or finishing a particular task. A very big advantage of an algorithm is any nontechnical people can also understand an algorithm. There is a possibility of having many algorithms for the same problem.

Now let's step into the very basic Linear Data Structure named array.

Array

The Array is a collection of elements of similar data types, and it continuously allocates memory in an array we can access randomly. We may get doubt how we can access elements randomly. An array allows us to access elements just with the help of their addresses. Now let us understand the array concept practically. Major applications are to store information in a linear fashion. It works efficiently in applications where frequent searching takes place.

Let us start by understanding using the one-dimensional array.

One-Dimensional Array

The 1D array looks like a simple row here, and elements are stored one after another.

Declaration

Declaring an array is similar to declaring a variable in C language simply. We need to specify the data type, then the array name, and next, you need to tell the maximum size.

Check the below Syntax to get an idea:

int array_name[4];

Array Initialization

 We have two ways of initializing one is compile-time initialization, and the second one is run-time initialization. Initially, all the elements in an array will be assigned with some garbage values, so we need to initialize them to store them explicitly.

Compile-Time-Initialization

In compile-time initialization, we initialize the value within the code itself, so the memory will be allocated in the compile time.

Example program in C language

#include<stdio.h>
int main()
{
int numbers[2]={9,99};
printf(" We are initializing variables in compile time\n");
printf("%d \n",numbers[0]);
printf("%d \n",numbers[1]);
}

Output:

Run time Initialization

 This is also called dynamic initialization. Here elements are initialized at the run-time, and after successfully compiling the program, the memory is allocated in the run-time. We use the scanner function to initialize values in the run-time successfully. Check the below Example for a better understanding of Array Accessing. In a one-dimensional array, elements are accessed by specifying the exact array name and index value. Please make a note that our index always starts with Value 0. We can access it like this.

Example program in C language

#include<stdio.h>
int main()
{
int numbers[4];
printf("We are initializing in run time\n");
printf("Enter elements one by one\n");
for(int i=0;i<4;i++)
{
scanf("%d",&numbers[i]);
}
printf("The array elements are \n");
for(int i=0;i<4;i++)
{
printf("%d\n",numbers[i]);
}
return 0;
}

Output:

We have specific rules for declaring a one-dimensional array. They are as follows.

1. Before accessing, we need to declare the variable.

2. An array index always starts with zero and ends it size -1.

3. It is necessary to include data type and variable name while declaring an array.

Two-Dimensional Array

A two-dimensional array looks like a matrix in maths with columns and rows. It is also called an array of arrays.

Declaration

Similar to a one-dimensional array, we can declare the two-dimensional array as:

datatype arrayname[row-size][column-size]

Example:

int twodarray[4][4];

Initializing

The basic and first way of initializing is directly giving values when declaring themselves.

int twodarray[2][2] = {{1,2}, {1,2}};

Accessing

We can access elements by giving their correct location as rows and columns. Simply enter arrayname[row][column]

C program to initialize elements in runtime for two-dimensional array.

#include<stdio.h>
int main(){
int twodarray[2][2];
int i,j;
for(i=0;i<2;i++){
for(j=0;j<2;j++)
{
printf("Enter value for twodarray[%d][%d]\t",i,j);
scanf("%d",&twodarray[i][j]);
}
}
printf("The elements of Two Dimensional Array are\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf("%d \n",twodarray[i][j]);
}
}
return 0;
}

Output

In this program, we took a two-dimensional array named twodarray and assigned maximum row size and column size. Then we started taking values from the user and then displayed them in order.

Multi-Dimensional Array

The two-dimensional array also comes under the multi-dimensional array.

The structure will be like this

datatype arrayname[size 1][size 2][size 3].....[size n]

Linked List

It is a Linear Data Structure, and here elements can be stored as per the memory availability. Generally, if we have 4 bytes of memory in the array, we can store 4 bytes at maximum. And sometimes, there is a case where we declare an array of size 20 bytes and use only 4 bytes means the other 16 bytes of memory are going to be wasted. In a linked list, we can save a lot of memory by using junks of memory in our system, which is ignored in the array case. We can access elements only in a linear fashion means we cannot randomly access them we need to travel in a linear model. Similar to arrays, the linked lists also store similar data type elements. Linked List is dynamic in size means there is no need to specify the maximum size. We can increase the size dynamically. Insertion and deletion are easy on Linked List. The starting element of the Linked List is called a head.

Applications

1. This is best suitable for systems where memory is limited

2. Very suitable for software programs where frequent insertion and deletion occur.

3. Works well where time complexity is important while inserting and deleting.

Types of Linked List

1. Singly Linked List

2. Doubly Linked List

3. Circular Linked List

Singly Linked List

Here we have a head that points to the first element of the Linked List to make it clear head is a pointer that always points to the first element. The most important thing is we never manipulate. If we manipulate, then we will get undesired results. Every block is called a node, and it contains two parts: Data and the second one is a link. The link part links to the next element. You will get a good better idea after watching the below image.

Doubly Linked List

In the Doubly Linked List, we have two pointers, the previous node address, and the next node address, and here also head will point to the first node whose previous address is NULL as there are no previous elements to it. From next, every node will have both the previous and next link address, and finally, the last node won't have any next link address.

The structure of a double-Linked List will be like this.

Uses

1. Used in navigation systems that require forward and backward navigation.

 2. The browser implements navigation before and after the web page, you visit. You can use it both as a back button and a forward button.

 3. It is also used to represent the classic deck of cards.

 4. Also used in various applications to implement undo and redo functionality.

Disadvantages

1. It uses additional memory compared to arrays and single-linked lists.

2. Therefore, the elements are randomly stored in memory, so the elements are accessed in sequence, and direct access is not allowed.

Circular Linked List

A circular linked list is a variant of a linked list where the first element points to the last element and the last element points to the first element.

See the below diagram to understand it in a good way.

You can convert both single and double-linked lists to circular linked lists.

Advantages

1. Helps implement queues.

 2. Each node can be the starting point.

 3. Circular lists help your application repeat the List repeatedly.

 4. Circular double-linked lists implement advanced data structures like the Fibonacci heap.

In a circular linked list, the first node's previous pointer and the last node's next pointer will not be null, so it efficiently links and uses pointer space.

Now let us move to the programming part step by step in C.

Declaration and Initialization

Here initially, we need to learn how to declare the node. As we know, that node has two parts, one is the head, and the other is the next, which is a pointer, so we use structure here in the example, we used the structure of the name "node."

Basic code for creation of node in C

struct node
{
int data;
struct node * next;
}*tmp;
tmp=(struct node*)malloc(sizeof(struct node));
tmp->data=1;
tmp->next=NULL

With variables, one is data of int data type and the next pointer, which is a self-referencing structure variable. To allocate memory, we are using the malloc method. Once we allocate memory to tmp by declaring the size of operator "struct node " and then type casting into type node, we get some address that will be stored in tmp.

Till here, we will be getting this

Check this picture to get a better idea.

Let us think the address is 1000, allocated using the malloc function and stored in temp variables. In the next line, we said "tmp->data=1" which means the data is going to be one till here, and then "tmp->next=NULL" which means the NULL value is going to be stored in the next part of the node.

Next, we defined a tmp through which we can access data members of the structure. If we think about why it is a self-referencing variable, the pointer points to the next element, also a type node.

Head is a variable that needs to store the value of the first node address. The first node stores the second node's address, and so on. Finally, when we are at the end of the List, it stores the NULL value.

Implementation of insertion of an element in Linked List at beginning

We have a function named insertbeg, and now we are passing the argument, which is the element value to be inserted into Linked List.

CODE

Example program in C language

void insertbeg()
{
tmp=(struct node*)malloc(sizeof(structnode));
tmp->data=ele;
if(p==NULL)
{
tmp->next=NULL;
}
else
{
tmp->next=p;
}
p=tmp;

Note that the root node that is the first node is created in the main function itself means it is created globally, so there is no need to declare all other functions in the program. There will be two cases. The first case is the entire Linked List is empty. At this time, the root is null means p=null as we said, "tmp->next=p" for the second case where at least two elements exist. In the Linked List for both cases, we need to have the address of the first node, so we create a new node named "p". This will act as the head node. First, we allocate memory to tmp and initialize the data part with the element. And then, by using the if-else block, we are checking whether Linked List is empty or not in the empty case "tmp->next=NULL" in the else case, the tmp node, which is the new node, will get its next pointer value as p that is first element value and finally, we are updating the p address value to the current temp value.

Implementation of Inserting At END

Generally, we cannot manipulate the head value. To link at the end, the last node should point to null, and this won't change even if many nodes get added. Here in the code, we initially assigned p to the temp value to store our data, and we know that p points to the first element. Here also, we have two cases: Linked List is empty, and the second one is at least two nodes exist on Linked List. Here we declared a function named insertend().

Example program in C language

void insertend(int ele)
{
tmp=p;
tmp1=(struct node*)malloc(sizeof(struct node));
tmp1->data=ele;
tmp1->next=NULL;
if(p==NULL)
p=tmp1;
else
{
while(tmp->next!=NULL)
      tmp=tmp->next;
tmp->next=tmp1;
}
}

Here in the code, we are giving the next address in the temp variable as null as the last element address should always be null. Now we start checking the condition if Linked List is empty, then the p stores tmp1 address that is "NULL”.

In the else condition, we need to start the loop as we need to traverse around the linked List, so we used while (condition), and after that, the tmp value traverses’ step by step ahead "temp=temp->next;" and after loop, the temp value address gets updated to tmp1, so we are making the next element address is null.

C program to do Insertion at end and beginning in Single Linked List:

#include <stdio.h>
struct node
{
int data;
struct node *link;
}*head=NULL,*temp;;
int main()
{
void insertbeg(int);
void insetend(int);
void display();
struct node *temp;
int x,ch;
do{
printf("\n1.insert at beg ");
printf("2.insert at end ");
printf("3.display ");
printf("4.exit \n");
printf("enter ur choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("enter the element to insert ");
scanf("%d",&x);
insertbeg(x);
break;
case 2:printf("enter the element to insert ");
scanf("%d",&x);
insertend(x);
break;
case 3:display();
break;
case 4:exit(0);
break;
default: printf("You entered other character make sure to enter number in between 1 to 4 ");
break;
}
}while(ch!=6);
}
void create(int x)
{
// struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=x;
temp->link=NULL;
}
void insertbeg(int x)
{
//struct node *temp;
create(x);
if(head==NULL)
head=temp;
else
{
temp->link=head;
head=temp;
}
printf("element inserted at the beg is %d \n",head->data);
}
void insertend(int x)
{
struct node *ptr;
create(x);
if(head==NULL)
head=temp;
else
{
ptr=head;
while(ptr->link!=NULL)
ptr=ptr->link;
ptr->link=temp;
}
printf("element inserted at end is %d \n",x);
}


void display()
{
struct node *ptr;
if(head==NULL)
printf("list is empty \n");
else
{
printf("the elements are ");
for(ptr=head;ptr!=NULL;ptr=ptr->link)
printf("%d ",ptr->data);
}
}

Output:

CODE EXPLAINATION

Here we created a node Initially, and then by using a do-while loop, we are showing MENU where the user can select an option 1 for insertion at the beginning, 2 for insertion at the ending, 3 for display, and finally, 4 for exiting from the loop. According to the selection, the functions get executed. We used "next" in the above implementation and "link" in this program.

Stack

Stack follows the Last In First Out(LIFO) principle. It means the last element entered will be removed first. A stack of books is a good real-time example where we remove the last book inserted first.

Queue

Queue follows the First In First Out FIFO. The queue is open at both ends. Here we insert an element at the rear end, and deletion is done at the tail end. A simple Queue at the ticket counter is an example of a "Queue."

Tree

The tree is a simple data structure with levels and elements stored in nodes. Non-linear data structures such as trees are popular. The tree represents a hierarchical structure unlike other data structures such as an array, stack, queue, and linked list, which are linear. It is not important to know the order of trees. A tree contains nodes and two pointers. The two pointers represent the left and right children of the parent node, respectively. It is helpful to understand the terms of a tree in more detail.

Searching

1. Linear Search:

It helps us search elements in linear data structure example array.

Linear Search checks all the elements one after another. It is a simple straight brute-forced algorithm.

Linear Search Algorithm

linearSearch(arr,item)
for each element in the array
if item==element
return its index
return -1.

This algorithm uses the "for each" loop to search for the key elements in the given array. Inside the loop, we iterate through each element and check whether it matches the key and if the matched algorithm returns the index. There is a scenario where the element won't exist in the array. In that case, our algorithm returns "-1."

2. Binary Search

This algorithm can only be used for the sorted array. The Binary Search technique follows the divide and conquers methodology. Binary Search is more efficient than Linear Search.

Binary Search-Iterative Algorithm

binarySearch(arr,size)
loop until beg is not qual to end 
midindex=(beg+end)/2
if(item==arr[midindex])
return midindex
else if(item>arr[midindex])
beg=midindex+1
else
end=midindex-1

We iterate until the beginning is less than the ending. Have a look at the below image to get an idea.

To iterate, the begging should always be less than the end. We create a new middle index, the beginning and ending index average. With the help of conditional statements, we check first whether the item matches the central index element. If so, we return the mid index, the element we are searching for. Next, we check whether an item is greater than the central element.