__Introduction__

Data is defined as a value assigned to a variable.

Data Structures is a method or technique of storing huge amounts of data in the memory in a classified manner where we can access the data efficiently at any point of time.

We need data structures to achieve a proper classification of data in a systematic manner, it helps to speed up the execution and also to save memory.

__Classification of Data Structures__

Let’s see the classification of data structures in c:

**Data structure**

__Primitive data Structure__

Primitive Data Structures are the structures that operate directly on the instructions by the machine.

Under Primitive Data structures, we have Integer, Character, Double, Float and Pointer. These are pre-defined in nature and will have certain defined values.

__Non primitive data structures__

Non Primitive data structures are created by the users, i.e, programs are created using Primitive data structures.

Under Non primitive data structures, we have Linear and Non linear data structure.

__Linear data structure__– Data elements are organized sequentially, where the elements are attached to its preceding and next element in what is called a linear data structure.

__Non Linear data structure-__ Data elements are not organized sequentially or linearly are called non-linear data structures.

** Let’s discuss the data structures in C programming language:**

** **There are 8 types of data structures:

- Arrays
- Linked list
- Stack
- Queue
- Binary tree
- Binary search tree
- Heap
- hashing

__Arrays data structure
__

Array is a type of Linear data structure which is a collection of data, stored at contiguous memory locations.it is used to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array.** **

__Declaration of array__

An array is declared just as same as any other variable in C, data type followed for array name; in addition to that, we need to ask the subscript to mention the memory allocation inside a square brackets[].

**Eg: intage[5];**

Here the variable age holds integer values which is stored as below:

age[0] age[1] age[2] age[3] age[4]

we can access this easily by printf(“%d”,age[1]);

in the output ‘b’ will be printed.

__Array Initialization__

We can initialize and array as shown below:

Age[5]={20,32,45,22,21};

It will be stored as

age[0] age[1] age[2] age[3] age[4]

similarly using char data type we can store string values.

__Single Dimensional array__

It is the basic form of an array. The array is given a name, and its elements are referred to by their subscripts or indices.

E.g: intage[5];

__2 Dimensional array__

It is a collection of elements with ‘a’ rows and ‘b’ columns. It has two subscripts, one to represent the row and the other column. It is very similar to the matrix in Mathematics. Operations performed on 2D arrays are the addition of two matrices, multiplication, traversal etc., with the same rules as in Mathematics.

Eg :int a[3][3];

__Multi-dimensional array__

An array with more than two dimensions is a multi-dimensional array.

For e.g., if we have three dimensions inta[3][2][4];

The first subscript is plane number, the second is rows, and the third is columns.

3*2*4=24 therefore it contains 24 elements.

__Operations of data structures in C__

Traversal: when we have a collection of data stored in the computer, we will have to move from one end of the list to the other end to modify or print the data for this reason.

Insertion or deletion:

Insertions refer to the operation of adding an element to an array.

Deletion refers to the operation of deleting an element from an array.

Traversal of elements helps in adding or removal of an element from the middle of an array.

__Sorting__

It is a process of rearranging the elements in some specified order. We have different sorting algorithms for sorting, such as bubble sort, quick sort, heap sort, selection sort and merge sort. The simplest sorting algorithm is bubble sort.

__Searching__

It refers to the operation of finding the location of any element in the array.

There are different techniques that are used based on the arrangement of elements such as linear search, binary search, sequential search, jump search etc.

__Pointer in array__

According to the data structure in C, Pointer is a variable that contains the address of another variable, supports dynamic allocation routines, and ‘&’ is used to represent pointers.

Syntax: data_type (*var_name)[size_of_array]** **

__2) Linked Lists__

It is a linear data structure that consists of a set of nodes connected together and organized by pointers. Each node holds its own data and addresses to the next node forming a chain structure.

__Types of linked list__

- Singly linked list consists of nodes which have data and address to the next node. We can perform traversal insertion and deletion in singly linked lists.
- Doubly linked list-each node consists of data and 2 addresses (1-address to previous node, 2-address to next node).
- Circular linked list-the last node consists of the address of the first node forming a circle.

** **__Application of linked list__

Used to implement stacks, queues, linked lists etc.

Used to insert elements at the beginning and end of the list

Helps in dynamic allocation of memory

__3) Stacks__

A stack is a linear data structure that is used to store data in a columnar order. It follows a last in first out fashion (LIFO), i.e. the element which is inserted at last is the first element to be deleted. The top is the pointer used to check the top element.

__Operations performed on stack__:

Push()-used to insert an element to the stack

Pop()-use to delete an element from the stack

ISempty()-is used to check if the stack is empty

Isfull()-is used to check if the stack is full

Peek()-get the value of the top element without popping

__4) Queue__

It is a linear data structure used to store data. It follows First in First out fashion(FIFO), .i.e. the element which is inserted first is the first element to be deleted. The front is the pointer used to insert an element, and the rear is the element used to delete an element.

__Operations performed on queue:__

Enqueue()-used to insert an element to the queue

Dequeue()-use to delete an element from the queue

ISempty()-is used to check if the queue is empty

Isfull()-it is used to know if the queue is full.

__5) Binary Tree__

A tree with a maximum of two children is known as a binary tree. It is a non-linear data structure(Hierarchical).

A binary tree consists of 3 parts-data, pointer to left child, pointer to right child.

The top element is known as the root of the tree.

Common traversal methods: Preorder(-print, left ,right), postorder(-left, right, print), in order(-left , print, right).

__Applications of Binary tree__

- File System Hierarchy.
- Wide variety of applications due to multiple variations of binary tree.

__6) Binary Search Tree__

A binary tree with additional restriction is known as binary search tree.

__Restrictions:__

- Left child must always be less than the root node.
- The right child must always be greater than the root node.

__7) Heap__

Heap is a data structure which is based on a complete binary tree. There are two types of heap:

- Max heap-the root node must be larger than any of its children nodes. This property must be throughout the sub tree.
- Min Heap-the root node must be smaller than any of its children nodes. This property must be throughout the sub tree

__Heap operations:__

- Heapify- it is used to create a Heap data structure(max or min heap)
- To delete element from heap
- To insert element to a heap
- Peek-to find max or min element without deleting the element
- Extract-to print the max or min element and deleting it

** Applications of heap**

- To implement priority queue
- Heap sort
- Dijkstra’s algorithm

__8) Hashing__

It is used to retrieve and store elements in an efficient manner.

It is a process of mapping values or keys to a table known as a hash table using a hash function.

It helps in faster access of elements.

Efficiency of hashing depends on the function which is used.

__Formula used to calculate hash key:__

**Key=element%size.**

__Operations on hash table:__

- Insert element to hash table
- Delete element from hash table
- Search element from hash table

I hope this helped you in understanding topics related to Data structures in C.