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.