Data structure: Data Structures in C are used to store data in an organised and efficient

manner. The C Programming language has many data structures like an array, stack, queue,
linked list, tree, etc. A programmer selects an appropriate data structure and uses it according
to their convenience.
Data Structure is a particular way of storing and organizing data in the memory of the
computer so that these data can easily be retrieved and efficiently utilized in the future when
required. The data can be managed in various ways, like the logical or mathematical model
for a specific organization of data is known as a data structure.
i. It is also used for processing, retrieving, and storing data.
ii. There are different basic and advanced types of data structures that are used in almost
every program or software system that has been developed.
iii. So we must have good knowledge about data structures.
iv. It is the way of arranging data on a computer so that it can be accessed and updated
efficiently.
v. Data can be numbers or texts written on a piece of paper, in the form of bits and bytes
stored inside the memory of electronic devices, or facts stored within a person's mind.
vi. Data is a collection of facts and figures or a set of values or values of a specific format
that refers to a single set of item values.
vii. The data items are then classified into sub-items, which is the group of items that are
not known as the simple primary form of the item.

Terminologies of Data Structure:

Data Structures are the building blocks of any software or program. Selecting the suitable
data structure for a program is an extremely challenging task for a programmer.

The following are some fundamental terminologies used whenever the data structures are
involved:

1. Data: We can define data as an elementary value or a collection of values. For

example, the Employee's name and ID are the data related to the Employee.
2. Data Items: A Single unit of value is known as Data Item.
3. Group Items: Data Items that have subordinate data items are known as Group Items.
For example, an employee's name can have a first, middle, and last name.
4. Elementary Items: Data Items that are unable to divide into sub-items are known as
Elementary Items. For example, the ID of an Employee.
5. Entity and Attribute: A class of certain objects is represented by an Entity. It consists
of different Attributes. Each Attribute symbolizes the specific property of that Entity.

Features:
Some of the Significant Features of Data Structures are:

1. Robustness: Generally, all computer programmers aim to produce software that

yields correct output for every possible input, along with efficient execution on all
hardware platforms. This type of robust software must manage both valid and invalid
inputs.
2. Adaptability: Building software applications like Web Browsers, Word Processors, and
Internet Search Engine include huge software systems that require correct and
efficient working or execution for many years. Moreover, software evolves due to
emerging technologies or ever-changing market conditions.
3. Reusability: The features like Reusability and Adaptability go hand in hand. It is known
that the programmer needs many resources to build any software, making it a costly
enterprise. However, if the software is developed in a reusable and adaptable way,
then it can be applied in most future applications. Thus, by executing quality data
structures, it is possible to build reusable software, which appears to be cost-effective
and timesaving.

Types of Data Structure

• Linear data structure: Data structure in which data elements are arranged
sequentially or linearly, where each element is attached to its previous and next
adjacent elements, is called a linear data structure.
Examples: array, stack, queue, linked list, etc.
 o Static data structure: Static data structure has a fixed memory size. It is easier to
access the elements in a static data structure.
Example: array.
o Dynamic data structure: In dynamic data structure, the size is not fixed. It can be
randomly updated during the runtime which may be considered efficient
concerning the memory (space) complexity of the code.
Examples: queue, stack, etc.
• Non-linear data structure: Data structures where data elements are not placed
sequentially or linearly are called non-linear data structures. In a non-linear data
structure, we can’t traverse all the elements in a single run only.
Examples: trees and graphs.

1. Array: In an array, elements in memory are arranged in continuous memory. All the
elements of an array are of the same type. And, the type of elements that can be
stored in the form of arrays is determined by the programming language. An array is a
collection of items stored at contiguous memory locations. The idea is to store multiple
items of the same type together.
Syntax: datatype varname[size].

2. Linked List: A linked list is a linear data structure, in which the elements are not
stored at contiguous memory locations. The elements in a linked list are linked using
pointers. In simple words, a linked list consists of nodes where each node contains a
data field and a reference(link) to the next node in the list.

3. Stack: Stack is a linear data structure that follows a particular order in which the
operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last
Out). LIFO implies that the element that is inserted last, comes out first and FILO
implies that the element that is inserted first, comes out last.
4. Queue: A Queue is defined as a linear data structure that is open at both ends and the
operations are performed in First In First Out (FIFO) order. We define a queue to be a
list in which all additions to the list are made at one end, and all deletions from the list
are made at the other end. The element which is first pushed into the order, the
operation is first performed on that.

5. Graph: A Graph is a non-linear data structure consisting of vertices and edges. The
vertices are sometimes also referred to as nodes and the edges are lines or arcs that
connect any two nodes in the graph. More formally a Graph is composed of a set of
vertices( V ) and a set of edges( E ). The graph is denoted by G(E, V).

6. Tree: The tree in C is a non-linear data structure, i.e. The elements are not stored
sequentially, and in the tree in C, they are present in levels. A binary tree in C is a
data structure in which every node can have a maximum of two children nodes.
Recursion: Recursion is the technique of making a function call itself. This technique
provides a way to break complicated problems down into simple problems which are easier
to solve.
i. Recursion may be a bit difficult to understand. The best way to figure out how it
works is to experiment with it.
ii. Recursion is the process of repeating items in a self-similar way.
iii. In programming languages, if a program allows you to call a function inside the same
function, then it is called a recursive call of the function.
iv. Recursion cannot be applied to all the problem, but it is more useful for the tasks
that can be defined in terms of similar subtasks.
For Example, recursion may be applied to sorting, searching, and traversal problems.
v. A recursive function performs the tasks by dividing it into the subtasks. There is a
termination condition defined in the function which is satisfied by some specific
subtask. After this, the recursion stops and the final result is returned from the
function.
Syntax:
void recursive_fun() //recursive function
{
Base_case; // Stopping Condition
recursive_fun(); //recursive call
}
int main()
{
recursive_fun(); //function call
}

Example:
#include<stdio.h>
int fibonacci(int);
void main ()
{
int n,f;
 printf("Enter the value of n?");
scanf("%d",&n);
f = fibonacci(n);
printf("%d",f);
}
int fibonacci (int n)
{
if (n==0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
else
{
return fibonacci(n-1)+fibonacci(n-2);
}
}

Types of Recursion

There are two types of recursion in the C language.

1. Direct Recursion
2. Indirect Recursion

1. Direct Recursion

Direct recursion in C occurs when a function calls itself directly from inside. Such functions
are also called direct recursive functions.
2. Indirect Recursion

Indirect recursion in C occurs when a function calls another function and if this function calls
the first function again. Such functions are also called indirect recursive functions.

Recursive Algorithm: A recursive algorithm calls itself with smaller input values and
returns the result for the current input by carrying out basic operations on the returned
value for the smaller input. Generally, if a problem can be solved by applying solutions to
smaller versions of the same problem, and the smaller versions shrink to readily solvable
instances, then the problem can be solved using a recursive algorithm.
A recursive function performs the tasks by dividing it into the subtasks. There is a
termination condition defined in the function which is satisfied by some specific subtask.
To build a recursive algorithm, you will break the given problem statement into two parts.
The first one is the base case, and the second one is the recursive step.

• Base Case: It is nothing more than the simplest instance of a problem, consisting of a
condition that terminates the recursive function. This base case evaluates the result
when a given condition is met.
• Recursive Step: It computes the result by making recursive calls to the same function,
but with the inputs decreased in size or complexity.
Syntax:
if (test_for_base)
{
return some_value;
}
else if (test_for_another_base)
{
return some_another_value;
}
else
{
// Statements;
recursive call;
}
Example:
#include <stdio.h>
int sum(int n);
int main() {
int number, result;
printf("Enter a positive integer: ");
scanf("%d", &number);
result = sum(number);
printf("sum = %d", result);
return 0;
}
int sum(int n) {
if (n != 0)
// sum() function calls itself
return n + sum(n-1);
else
return n;
}

• Linear Recursion
In linear recursion a function calls exactly once to itself each time the function is invoked,
and grows linearly in proportion to the size of the problem. Finding maximum among an
array of integers could be a good example of linear recursion.
Example:
#include <stdio.h>
#define SIZE 10
int recursiveMax (int *, int );
int max (int, int);
int main ()
{
 int arr[SIZE] = {1, 3, 5, 4, 7, 19, 6, 11, 10, 2};
int max = recursiveMax(arr, SIZE);
printf("Maximum element among array items is: %d\n", max);
}
int recursiveMax (int *arr, int n)
{
if (n == 1)
return arr[0];
return max (recursiveMax (arr, n-1), arr[n-1]);
}
/* helper function to compute max of two decimal integers */
int max (int n, int m)
{
if (n > m) return n;
return m;
}

OUTPUT
======
Maximum element among array items is: 19

• Binary Recursion:
As name suggests, in binary recursion a function makes two recursive calls to itself when
invoked, it uses binary recursion. Fibonacci series is a very nice example to demonstrate
binary recursion.
Example:
#include <stdio.h>
int recursiveFib (int);
int main ()
{
 int n = 6;
printf ("%dth fibonacci number is %d\n", n, recursiveFib(n));
}
int recursiveFib (int n)
{
// base case
if (n <= 1)
return n;
// binary recursive call
return recursiveFib(n-1) + recursiveFib (n - 2);
}
OUTPUT
======
6th fibonacci number is 8

Linked List: A Linked List is a linear data structure. Every linked list has two parts, the data
section and the address section that holds the address of the next element in the list, which
is called a node.
o The size of the linked list is not fixed, and data items can be added at any locations in the
list.
o The disadvantage is that to get to a node, we must traverse to all the way from the first
node to the node that we require.
o The Linked List is like an array but unlike an array, it is not stored sequentially in the
memory.
o Linked List can be defined as collection of objects called nodes that are randomly stored
in the memory.
o A node contains two fields i.e. data stored at that particular address and the pointer
which contains the address of the next node in the memory.
o The last node of the list contains pointer to the null.
LinkedList is a collection of nodes, where every node contains two fields:
o Data field: It stores the actual value address field.
o Address field: It stores the reference of the next node.
 There are three types of linked list they are:
1. Single linked list
2. Double linked list
3. Circular linked list

1. Single Linked List: Singly linked list can be defined as the collection of ordered set of
elements. The number of elements may vary according to need of the program.
A node in the singly linked list consist of two parts:
o Data part and
o link part.
Data part of the node stores actual information that is to be represented by the node while
the link part of the node stores the address of its immediate successor.
One way chain or singly linked list can be traversed only in one direction. In other words, we
can say that each node contains only next pointer, therefore we can not traverse the list in
the reverse direction.

Insertion

The insertion into a singly linked list can be performed at different positions. Based on the
position of the new node being inserted, the insertion is categorized into the following
categories.

SN Operation Description

1 Insertion at It involves inserting any element at the front of the list. We just need to
beginning a few link adjustments to make the new node as the head of the list.
 2 Insertion at end It involves insertion at the last of the linked list. The new node can be
of the list inserted as the only node in the list or it can be inserted as the last one.
Different logics are implemented in each scenario.

3 Insertion after It involves insertion after the specified node of the linked list. We need
specified node to skip the desired number of nodes in order to reach the node after
which the new node will be inserted. .

Deletion and Traversing

The Deletion of a node from a singly linked list can be performed at different positions. Based
on the position of the node being deleted, the operation is categorized into the following
categories.

SN Operation Description

1 Deletion at It involves deletion of a node from the beginning of the list. This is the simplest
beginning operation among all. It just need a few adjustments in the node pointers.

2 Deletion at the It involves deleting the last node of the list. The list can either be empty or full.
end of the list Different logic is implemented for the different scenarios.

3 Deletion after It involves deleting the node after the specified node in the list. we need to
specified node skip the desired number of nodes to reach the node after which the node will
be deleted. This requires traversing through the list.

4 Traversing In traversing, we simply visit each node of the list at least once in order to
perform some specific operation on it, for example, printing data part of each
node present in the list.

5 Searching In searching, we match each element of the list with the given element. If the
element is found on any of the location then location of that element is
returned otherwise null is returned. .
 2. Double Linked list: A doubly linked list consists of two pointers that store the address
of the next successive node and the address of the previous node. The traversal in a
doubly linked list happens in both forward and backward directions.
o Therefore, in a doubly linked list, a node consists of three parts: node data, pointer
to the next node in sequence (next pointer) , pointer to the previous node (previous
pointer).
o In a singly linked list, we could traverse only in one direction, because each node
contains address of the next node and it doesn't have any record of its previous
nodes.
o However, doubly linked list overcome this limitation of singly linked list.
o Due to the fact that, each node of the list contains the address of its previous node,
we can find all the details about the previous node as well by using the previous
address stored inside the previous part of each node.

Operations on doubly linked list

SN Operation Description

1 Insertion at beginning Adding the node into the linked list at beginning.

2 Insertion at end Adding the node into the linked list to the end.

3 Insertion after specified Adding the node into the linked list after the specified node.
node

4 Deletion at beginning Removing the node from beginning of the list

5 Deletion at the end Removing the node from end of the list.

6 Deletion of the node Removing the node which is present just after the node containing
having given data the given data.

7 Searching Comparing each node data with the item to be searched and return
the location of the item in the list if the item found else return null.

8 Traversing Visiting each node of the list at least once in order to perform some
specific operation like searching, sorting, display, etc.
Syntax:
struct node
{
int data;
struct node* prev;
struct node* next;
};

Example:
#include <stdio.h>
#include <stdlib.h>
void display();
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
int main()
{
struct Node* head;
struct Node* first=NULL;
struct Node* second=NULL;
struct Node* third=NULL;
struct Node* fourth=NULL;
first = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
fourth = (struct Node*)malloc(sizeof(struct Node));
first->data = 10;
second->data = 20;
third->data = 30;
fourth->data = 40;
first->next = second;
first->prev=NULL;
second->next = third;
second->prev=first;
third->next = fourth;
third->prev=second;
fourth->next = NULL;
fourth->prev = third;
head=first;
display(first);
return 0;
}
void display(struct Node* ptr) {
struct Node* last;
printf("The doubly linked list elements are:\n");
while (ptr != NULL) {
printf("%4d ", ptr->data);
last = ptr;
ptr = ptr->next;
}
}
 3. Circular Linked List: In a Circular linked list, every element has a link to its next
element in the sequence, and the last element has a link to the first element. A
circular linked list is similar to the singly linked list except that the last node points to
the first node.
o A Circular singly linked list is a collection of data called nodes, where the last node
links to the first node.
o The traversal of a circular singly linked list is until we reach the same node we
started in a list.

Syntax:
struct node
{
int data;
struct node* next;
};

Operations on Circular Singly linked list:

Insertion

SN Operation Description

1 Insertion at beginning Adding a node into circular singly linked list at the beginning.

2 Insertion at the end Adding a node into circular singly linked list at the end.
Deletion & Traversing

SN Operation Description

1 Deletion at Removing the node from circular singly linked list at the beginning.
beginning

2 Deletion at the Removing the node from circular singly linked list at the end.
end

3 Searching Compare each element of the node with the given item and return the
location at which the item is present in the list otherwise return null.

4 Traversing Visiting each element of the list at least once in order to perform some
specific operation.

o Singly Circular Linked List in C

A node in a circular singly linked list contains a data block and a next block to store the
address of the next node. The last node's next block contains the address of the first (head)
node.
Synatx:
struct node{
<data__type> data;
struct node* next;
};
o Doubly Circular Linked list in C
A node in a circular doubly linked list contains a data block, and two blocks (prev and next)
to store the addresses of the previous node and the next node. The first (head) node
contains the address of the last node in the prev block, and the last node's next block
contains the address of the first (head) node.
Syntax:
struct node{
<data__type> data;
 struct node* next;
struct node* prev;
};

Example:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//Represents the node of list.
struct node{
int data;
struct node *next;
};

//Declaring head and tail pointer as null.

struct node *head = NULL;
struct node *tail = NULL;

//This function will add the new node at the end of the list.
void add(int data){
//Create new node
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
//Checks if the list is empty.
if(head == NULL){
//If list is empty, both head and tail would point to new node.
head = newNode;
tail = newNode;
newNode->next = head;
}else {
 //tail will point to new node.
tail->next = newNode;
//New node will become new tail.
tail = newNode;
//Since, it is circular linked list tail will point to head.
tail->next = head;
}
}

//This function will display the nodes of circular linked list

void display(){
struct node *current = head;
if(head == NULL){
printf("List is empty");
}
else{
printf("Nodes of the circular linked list: \n");
do{
//Prints each node by incrementing pointer.
printf("%d ", current->data);
current = current->next;
}while(current != head);
printf("\n");
}
}

int main()
{
//Adds data to the list
 add(1);
add(2);
add(3);
add(4);
//Displays all the nodes present in the list
display();

return 0;
}