C Tutorial

C Tutorial C Language Environment Setup Execution flow of C program C printf and Scanf C Data type C Token Variable in C Operators in C Comments in C Escape Sequence in C C – Storage Classes C Decision control statement Loop Statement in C Break, continue and goto statement in C Type Casting in C Function in C Recursion in C String in C C Array Pointer in C Dynamic memory allocation C –Structure Nested Structure in C Union in C File Handling in C C pre-processor Static Function In C Sizeof In C Selection Sort In C Scope Of Variables In C Runtime Vs Compile Time In C Random Access Lseek In C Queue Implementation In C Pseudo Code In C Prototype In C Pointer To Pointer In C Pointer Arithmetic In C Passing Array To Function In C Null Character In C Merge Sort In C Macros In C Library Functions In C Memory Leak In C Int In C Goto And Labels In C Fibonacci Series In C Fflush In C Derived Data Types In C Data Types In C Const Vs Volatile In C Character Set In C Character Class Tests In C Calloc In C C Pointers Arrays In C Include In C Clrscr In C C Vs Java String Literals In C Types Of Pointers In C Variables In C Volatile In C Why C Is A Middle Level Language Infix To Postfix Program In C Ceil function in C LCM of two numbers in C Quick sort in C Static in C function pointer as argument in C Top Array Keywords in C Add two numbers using the function in C Armstrong program in C using function Array, Declaring Arrays and Array Initialization Limitations of Inline Function in C Merge and Merge sort with example in C Do-While Loop in C For Loop in C While-Loop in C Difference between while and do-while loop in C Array Of Structures in C Data Structures And Algorithms in C Types Of Structures In C How to Avoid Structure Padding in C Use of Structure in C Do WHILE LOOP in C Programming Examples For Loop in C Programming Examples Entry Control Loop in C Exit control loop in C Infinite loop in C Nested loop in C pow() function in C String Handling functions in C Prime Number code in C Factorial Program in C using For Loop Factorial Program in C Using While Loop Fibonacci Series in C Using For Loop Fibonacci series in C using while loop Prime Number Program in C using for Loop While Loop in C programming examples Built-in functions in C Assert() Function C vs Java Strings Call Back Function in Embedded C Else If Ladder fgets() function Ftell() Function getc() function getch() function gets() function Heap Sort Nested if-else statement Pi() Function Positioning of file Write() function abs() function in C Attributes in C C program to find factorial of a number using Recursion Ferror() in c fopen() function in C Fibonacci series program in C using Recursion Formatted Input and output function in C Snake Game in C User Defined Functions in C Beep() function in C Cbrt() function in C Hook() function in C Isalnum() function in C C Program to find the Roots of a Quadratic Equation C Switch Statements Difference between rand() and srand() function in C Difference between while and for loop in C Doubly Linked list in C Example of Iteration in C How to use atoi() function in C How to use floor() function in C How to use sine() function in C How to use Typedef Struct in C Integer Promotions in C C Program Swap Numbers in cyclic order Using Call by Reference C Program to Find Largest Number Using Dynamic Memory Allocation C Program to Find the Largest Number using Ternary Operator C/C++ Program to Find the Size of int, float, double and char Find the Largest Three Distinct Elements in an Array using C/C++ Loop Questions in C Modulus on Negative Numbers in C Multiplication table program in C using For loop Nested Loops in C Programming Examples C Program for Mean and Median of an Unsorted Array Results of Comparison Operations in C and C++ Reverse a Stack using Recursion in C Simple hash() function in C strcat() Function in C Sum of N numbers in C using For loop Use of free() function in C Write a program that produces different results in C and C++ C Function Argument and Return Values Keywords in C Bank management system in C Calendar application in C Floor() Function in C Free() Function in C How to delete a file in C How to move a text in C Remove an element from an array in C Unformatted input() and output() function in C What are linker and loader in C SJF Scheduling Program in C Socket Programming in C Structure in C Tower of Hanoi in C Union Program in C Variable Declaration in C What is Linked List in C While Loop Syntax in C fork() in C GCD program in C Branching Statements in C Comma Operator in C Control statement in C Double Specifier in C How to create a binary file in C Long int in C Palindrome Number in C Pure Virtual Function in C Run Time Polymorphism in C Types of Array in C Types of Function in C What is a buffer in C What is required in each C Program Associativity of Operators in C Bit Stuffing Program in C Actual and Formal Parameters Addition of two Numbers in C Advantages of function in C Arithmetic Progression Program in C Binomial Coefficient Program in C Difference between Array and List in C Diffie-Hellman Algorithm in C How to convert a number to words in C How to convert a string to hexadecimal in C Difference between If and Switch Statement in C C and C++ Binary Files C program that does not Suspend when Ctrl+Z is Pressed Different ways to Declare the Variable as Constant in C Range of Int in C C Program to find the size of a File FIFO Example in the C Language For loop in C Programming GCD program of two numbers in C GPA Calculator in C How to Calculate Time Complexity in C How to include graphics.h in C How to measure time taken by a function in C How to return a Pointer from a Function in C What is the main in C Addition of Matrix in C Booleans in C C Program for Extended Euclidean algorithms C Program of Fencing the Ground Ceil and Floor in C Compound Interest Program in C Displaying Array in C Distance Vector Routing Protocol Program in c Dos.h Header File in C Language DSA Program in C Explain the two-way selection in C Fee Management System in C File Operations in C Malloc function in C Multiplication Table in C Simple Programs in C Language tolower() Function in C Type Conversion in the C Why does sizeof(x++) not Increment x in C Advantages of Dynamic Memory Allocation in C Armstrong Number in C Assignment Operator Program in C Banker’s Algorithm in C Binary Search in C with Best and Worst Time Complexity Caesar Cipher Program in C Call by Value and Call by Reference in C Conditional Operator in C CRC Program in C Deadlock Detection Program in C Decimal to Binary in C Difference between If Else and Nested If Else in C Difference between Pre-increment and Post-increment in C Difference between Scope and Lifetime in C Evaluation of Arithmetic Expression in C Explain the Increment and Decrement Operators in C Fseek Function in C Functions in C How to Find Square Free Numbers in C Length of an Array Function in C OpenGL in C Projects on C language in 2023 Purpose of a Function Prototype in C Stdio.h in C Two-Dimensional array in C What is String Comparison in C C Compilers for Windows Functions and Recursion in C How to Declare Boolean in C How to Declare Character in C How to Round up a number in C How to use strlen() in C Pointer Declaration in C Algorithm for String Palindrome in C C Program to find ASCII value of a character Constant Pointer in C How to find string length in C using strlen() function Implicit and Explicit in C Indirect Recursion in C Input and Output functions in C isupper() in C Jump Statement in C Lifetime of a Variable in C Linker Error in C Language Numeric Constant in C Size of Pointer in C Square Root in C Language Static and Dynamic Memory allocation String Declaration in C Strong Number in C Symmetric Matrix in C Types of C Tokens What is a Size of Pointer in C What is Increment and Decrement Operator in C 1 2 3 4 Series Program in C Advantages and Disadvantages of C Language C Program for Polynomial Addition C Program to Count the Number of Vowels in a String C Programming Errors and Solutions Compilation Errors in C Complex C Programs Difference between Argument and Parameter in C Difference between char s[] and char *s in C Evaluation of Postfix Expression Using Stack in C Find Leftmost and Rightmost Set Bit of a Number fprintf and fscanf in C Introduction to Dynamic Array in C Print Address in C Realloc function in C Ternary Operators in C Types of Tokens in C with Examples Difference between Static and Dynamic Memory Allocation in C Addition Program in C Array Definition in C Array of Pointers in C Arrow Operator in C Average of Two Numbers in C Binary to Decimal in C Binary to Octal in C BREAK STATEMENT in C C Programming Operators Questions C Programs Asked in Interview Calculator Program in C C Program to Read and Print an Employee's Detail Using Structure Bubble Sort Algorithm in C C Program to Find Area and Perimeter of Circle C Program to Check Whether a Given Number is Even or Odd C in Roman Numerals C Program to Make a Simple Calculator Using Switch Case Insertion Sort Program in C How to take input in string in C GCC Conflicting Types in C Function Definition in C Format Specifier for Hexadecimal in C Flowchart in C Float in C Fizzbuzz Implementation in C Conditional Statement in C Conio.h functions list in C Constants in C Dynamic Array in C Decision Making Statements in C Continue Statement in C Creation of Thread in C DFS Algorithm in C Difference between parameter and arguments in C Dijkstra's Algorithm in C Leap Year Program in C Jump Statements in C Modulus Operator in C Memory Allocation in C Simple Interest Program in C Reverse Array in C Recursive Function in C Queue in C Printing Pascal’s Triangle in C Preprocessor Directives in C Perror() in C Perfect Number in C Programming Language Parameter Passing Techniques in C Pascal Triangle in C Patterm Program in C Affine cipher in C Dereferencing pointer in C Internal static variable vs External static variables in C Difference between exit(0) and exit(1) in C Booth's Algorithm in C Condition Control Statements in C Double Specifier in C Dynamic variables in C How to print alphabets in C How to print char array in c Order of Evaluation in C Order of Operations in C Semantic Error in C Size of String Variable in C SJF PREEMPTIVE SCHEDULING PROGRAM C: Tree in C Arithmetic Progression Program in C Array, Declaring Arrays, and Array Initialization ARRAYS IN C Assert() Function in c Atoi in C Bar3d() function in C Graphics Beep function in c Bigint (BIG INTEGERS) in C with Example Builtin functions of GCC compiler Fibonacci series in C Priority Queue in C 2D ARRAY IN C 7 Best IDEs for C/C++ Developers in 2022 Addition of Two Numbers in C Advantages and Disadvantages of C Language Advantages of Function in C Algorithm for String Palindrome in C What is fgets in C language 2d Shearing Program in C Recursion Questions In C Static Identifier in C Inserting elements in an array using C Language

DSA Program in C

How is a Data Structure Implemented?

  • The foundational terms of a data structure are the following terms. Data may be arranged using data structures to make it easier to use.
  • Each data structure has an interface that represents the set of operations the data structure allows. An interface only gives a list of supported operations, the types of arguments that these operations can accept, and their return types.
  • The definitions of the algorithms used in a data structure's operations are also supplied by the implementation, together with the internal representation of the data structure.

Characteristics of Data Structure

  • Correctness of a Data Structure: The interface of a Data Structure should be implemented appropriately.
  • Time Complexity: The operations on the data structure must be completed in the least amount of time.
  • Space Complexity: A data structure action should need the least amount of memory.

Applications:

  • Today experience three main problems due to growing complexity and data density.
  • Consider a retail store's inventory of one million (106) goods. If an application is used to seek up a product each time it must search one of them 106 million items, and the search process takes longer. As data accumulates, this problem will only become worse.
  • Processing speed: Although processor speed is quite fast, it hits a limit once there are one billion records of data.
  • Multiple requests: Even the fastest server can't manage the number of numbers since hundreds of users can search a database on a web server at once.
  • The solutions to the aforementioned problems come from data structures, which can arrange data such that not all things need to be searched for but just the relevant data can be found almost instantly.

Time Cases of Execution:

Examples for Execution Time to examine the relative execution speeds of different data structures, three basic cases are typically employed.

  • Worst Situation: In this case, a certain data structure operation takes the largest amount of time possible to complete.
  •  Average Case: This case illustrates how long it typically takes to complete a data structure operation. If an operation takes (n) times to complete, then m operations will likewise take (n) times to complete. If an operation takes (n) times to complete, then (n) times represent the function of n.
  • Best Case: If an operation on a data structure requires (n) time to complete, then the actual process may take up to (n) time, or the smallest possible amount of time for that operation to complete.

Algorithm

  • An algorithm is a step-by-step process that describes a series of instructions that must be followed in a certain order in order to the intended result. In terms of data structures, algorithms fall into the following categories:
  • Using search algorithms to look up a certain item in a database.
  • Analysis of algorithms the execution time or running time of various operations on a data structure is the topic of analysis of algorithms. It adds an item to a data structure, modifies an item that already exists there, and removes an item that already exists from a data structure.
  •  An operation's running time may be defined as the number of computer commands that are executed for each operation.
  • Since the precise running time varies from machine to computer, we normally examine every operation's running time as a function of n, where n is the number. Of items in a data structure processed by that operation.

Asymptotic Analysis:

  1. It is the process of calculating any operation's running time in mathematical computation units. For example, the running time of one operation can be calculated as f(n) and that of another as g(n2).
  2.  As a result, the first operation's running time will increase linearly with n while the second operation's running time will increase exponentially with n. Similarly, if n is significantly small, the running times of both operations will be nearly same.
  3. The run the ing time complexity of an algorithm is typically expressed using the asymptotic notations shown below.
    • Ο Notation
    • Ω Notation
    • θ Notation
  4. The core concepts of a data structure are those that are given below. Data may be structured using data structures in a way that makes. The Data Definition provides a list of certain data attributes.
    • A data element should be able to be mapped to a traceable definition. Atomic Definition need to define by June the definition
  5. Accurate the definition must be unambiguous.
  6. The definition should be understandable and clear.

Data Type

  • Internal Data Type Data types that have built-in support in a language are known as built-in data types. For instance, the majority of languages have the following built-in data types.
  • Derived Data Types: Character, Strings, Floating (decimal numbers), Boolean (true, false), and Integers. Because they may be implemented in a variety of ways, derived data types are implementation independent.
  • Implementation-independent produced by fusing basic or built-in data types with their corresponding operations. For instance, "Stack Queue," "List," and "Array."

Array Representation

  • The index starts at zero.
  • The array can accommodate eight elements because it is eight elements long.
  • Each element can be retrieved using its index.
  • For example, we may get the element at index 6 as 9.
  • The following is a list of the basic operations an array is capable of.
  • Insertion: Add a new element at a specific index.
  • Erasing an element at a given index is deletion.
  • Search: Use the provided index or the element's value to do a search.
  • Update an element searching a specified index.
#include <stdio.h>
#include <string.h>
static void display(int intArray[], int length){
   int i=0;
   printf("Array : [");
   for(i = 0; i < length; i++) {
      /* display value of element at index i. */
      printf(" %d ", intArray[i]);  }
   printf(" ]\n ");    }
int main() {
   int i = 0;
   /* Declare an array */
   int intArray[8];
   // initialize elements of array n to 0          
   for ( i = 0; i < 8; i++ ) {
      intArray[ i ] = 0; // set elements to default value of 0;  }
   printf("Array with default data.");
   /* Display elements of an array.*/
   display(intArray,8);     
   /* Operation : Insertion 
   Add elements in the array */
   for(i = 0; i < 8; i++) {
      /* place value of i at index i. */
      printf("Adding %d at index %d\n",i,i);
      intArray[i] = i;  }
   printf("\n");
   printf("Array after adding data. ");
   display(intArray,8);


/* Operation : Insertion 
   Element at any location can be updated directly */
   int index = 5;
   intArray[index] = 10;
   printf("Array after updating element at index %d.\n",index);
   display(intArray,8);
   /* Operation : Search using index
   Search an element using index.*/
   printf("Data at index %d:%d\n" ,index,intArray[index]);
   /* Operation : Search using value
   Search an element using value.*/
   int value = 4;
   for(i = 0; i < 8; i++) {
      if(intArray[i] == value ){
         printf("value %d Found at index %d \n", intArray[i],i);
         break;
      }
   }
   return 0;
}


Linked List

  • The LinkedList's link element comes first.
  • Each link carries a data field and a next link field.
  • Each link is connected to the one after it using the following link.
  • The Last Link includes a null link to denote the conclusion of the list.
  • The many kinds of linked lists are shown below.
  • In a Simple Linked List, there is just forward-facing item navigation.
  • You can access items in the double-linked list both forward and backward.
  • In a circular linked list, the first element links to the last element as the previous item, and the first element links to the first element as the next item.
  • The following is a list of the fundamental operations that a list can handle.
  • Insertion: Add a new element to the list's first position.
  • Deletion: the act of deleting the first item from the list.
  • presenting a complete list
  • Search: To find an element, use the provided key.
  • Delete: To remove an element, press the designated key.
  • There are two phases in Operation Deletion: 1. Obtain the URL that the First Connection has indicated is the temporary link.
  • Direct the First Link to the Next Link of the Temporary Link.
  • Navigation many operations, including delete and others like it, are built on operation navigation. It involves recursive steps. Obtain the initial links pointing link to the present link.
  • If it is not null, show the current link.
  • Pointing the Current Link to the Next Link of the Current Link will advance you to the following stage.
  • Advanced Techniques the following is a list of list's advanced operations.
  • Arranging a list in a certain manner recursively reverse a linked list.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//display the list
void printList(){


struct node *ptr = head;
   printf("\n[ ");
      //start from the beginning
   while(ptr != NULL){        
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}
//insert link at the first location
void insertFirst(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
      //point it to old first node
   link->next = head; 
   //point first to new first node
   head = link;
}
//delete first item
struct node* deleteFirst(){
   //save reference to first link
   struct node *tempLink = head;
   //mark next to first link as first 
   head = head->next;
   //return the deleted link
   return tempLink;
}


//is list empty
bool isEmpty(){
   return head == NULL;  }
int length(){
   int length = 0;
   struct node *current;
   for(current = head; current!=NULL;
      current = current->next){
      length++;
   }
   return length;  }
//find a link with given key
struct node* find(int key){
   //start from the first link
   struct node* current = head;
   //if list is empty
   if(head == NULL){
      return NULL;
   }
   //navigate through list
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return NULL;
      } else {
         //go to next link
         current = current->next;   }   }
   //if data found, return the current Link
   return current;
  }
//delete a link with given key
struct node* delete(int key){
   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;
   //if list is empty
   if(head == NULL){
      return NULL;
   }
   //navigate through list
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return NULL;
      } else {
         //store reference to current link
         previous = current;
         //move to next link
         current = current->next;           }  }
   //found a match, update the link
   if(current == head) {
      //change first to point to next link
      head = head->next;
   } else {
      //bypass the current link
      previous->next = current->next;
   }
   return current;
}
void sort(){
   int i, j, k, tempKey, tempData ;
   struct node *current;
   struct node *next;
   int size = length();
   k = size ;
   for ( i = 0 ; i < size - 1 ; i++, k-- ) {
      current = head ;
      next = head->next ;
      for ( j = 1 ; j < k ; j++ ) {            
         if ( current->data > next->data ) {
            tempData = current->data ;
            current->data = next->data;
            next->data = tempData ;


            tempKey = current->key;
            current->key = next->key;
            next->key = tempKey;
         }
         current = current->next;
         next = next->next;                        
      }
   }
}
void reverse(struct node** head_ref) {
   struct node* prev   = NULL;
   struct node* current = *head_ref;
   struct node* next;
while (current != NULL) {
      next  = current->next;  
      current->next = prev;   
      prev = current;
      current = next;
   }
   *head_ref = prev;
}
main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 
   printf("Original List: "); 
   //print list
   printList();
   while(!isEmpty()){            
      struct node *temp = deleteFirst();
      printf("\nDeleted value:");  
      printf("(%d,%d) ",temp->key,temp->data);        }
printf("\nList after deleting all items: ");          
   printList();
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
insertFirst(6,56); 
   printf("\nRestored List: ");  
   printList();
   printf("\n");  
   struct node *foundLink = find(4);
   if(foundLink != NULL){
      printf("Element found: ");  
      printf("(%d,%d) ",foundLink->key,foundLink->data);  
      printf("\n");  
   } else {
      printf("Element not found.");  
   }
   delete(4);
   printf("List after deleting an item: ");  
   printList();
   printf("\n");
   foundLink = find(4);
   if(foundLink != NULL){
      printf("Element found: ");  
      printf("(%d,%d) ",foundLink->key,foundLink->data);  
      printf("\n");  
   } else {
      printf("Element not found.");    }
printf("\n");  
   sort();
   printf("List after sorting the data: ");  
   printList();
   reverse(&head);
printf("\nList after reversing the data: ");  
printList();  }


Output:

Original List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Deleted value:(6,56) 
Deleted value:(5,40) 
Deleted value:(4,1) 
Deleted value:(3,30) 
Deleted value:(2,20) 
Deleted value:(1,10) 
List after deleting all items: 
[ ]
Restored List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Element found: (4,1) 
List after deleting an item: 
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Element not found.
List after sorting the data: 
[ (1,10) (2,20) (3,30) (5,40) (6,56) ]
List after reversing the data: 
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]

Double Linked List:

  • The link element, known as first and last, is present in the Double Linked List the next link field and data field are carried by each link.
  •  Using its next link will link each link to its next link each link is linked to its previous link using its previous link to mark the end of the list, the last reference contains a null reference.
  • The main operations supported by the list are given below Insert: Inserting item at the beginning of the list.
  • Delete: Removes an item from the top of the list. Insert Last: Inserts the item at the end of the list.
  • Remove Last: Removes an item from the end of the list. Insert After: Inserts an item after the list item
  •  Delete: Use the button to remove an item from the list Show Forward: Shows the entire list forward.
  • Show in reverse order: Shows the entire list in reverse order
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};
//this link always point to first Link 
struct node *head = NULL;
//this link always point to last Link 
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
   return head == NULL;
}
int length(){
   int length = 0;
   struct node *current;
   for(current = head; current!=NULL;
      current = current->next){
      length++;
   }
   return length;
}
//display the list in from first to last
void displayForward(){
   //start from the beginning
   struct node *ptr = head;
   //navigate till the end of the list
   printf("\n[ ");
   while(ptr != NULL){        
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}
//display the list from last to first
void displayBackward(){
   //start from the last
   struct node *ptr = last;


   //navigate till the start of the list
   printf("\n[ ");
while(ptr != NULL){    
      //print data
      printf("(%d,%d) ",ptr->key,ptr->data);
      //move to next item
      ptr = ptr ->prev;
      printf(" ");
   }
   printf(" ]");
}
//insert link at the first location
void insertFirst(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()){
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }
   //point it to old first link
   link->next = head;
   //point first to new first link
   head = link;
}
//insert link at the last location
void insertLast(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()){
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     


      //mark old last node as prev of new link
      link->prev = last;
   }
   //point last to new last node
   last = link;
}
//delete first item
struct node* deleteFirst(){
   //save reference to first link
   struct node *tempLink = head;


   //if only one link
   if(head->next == NULL){
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
   head = head->next;
   //return the deleted link
   return tempLink;
}
//delete link at the last location
struct node* deleteLast(){
   //save reference to last link
   struct node *tempLink = last;
   //if only one link
   if(head->next == NULL){
      head = NULL;
   } else {
      last->prev->next = NULL;
   }
   last = last->prev;
   //return the deleted link
   return tempLink;
}
//delete a link with given key
struct node* delete(int key){
   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;
   //if list is empty
   if(head == NULL){
      return NULL;
   }
   //navigate through list
while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return NULL;
      } else {
         //store reference to current link
         previous = current;


         //move to next link
         current = current->next;             
      }
   }
   //found a match, update the link
   if(current == head) {
      //change first to point to next link
      head = head->next;
   } else {
      //bypass the current link
      current->prev->next = current->next;
   }    
   if(current == last){
      //change last to point to prev link
      last = current->prev;
   } else {
      current->next->prev = current->prev;
   }
   return current;
}
bool insertAfter(int key, int newKey, int data){
   //start from the first link
   struct node *current = head;      
   //if list is empty
   if(head == NULL){
      return false;
   }
   //navigate through list
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return false;
      } else {           
         //move to next link
         current = current->next;             
      }
   }
   //create a link
   struct node *newLink = (struct node*) malloc(sizeof(struct node));
   newLink->key = key;
   newLink->data = data;
   if(current==last) {
      newLink->next = NULL; 
      last = newLink; 
   } else {
      newLink->next = current->next;         
      current->next->prev = newLink;
   }
newLink->prev = current; 
   current->next = newLink; 
   return true;  }
main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 
   printf("\nList (First to Last): ");  
   displayForward();
   printf("\n");
   printf("\nList (Last to first): "); 
   displayBackward();
   printf("\nList , after deleting first record: ");
   deleteFirst();        
   displayForward();
   printf("\nList , after deleting last record: ");  
   deleteLast();
   displayForward();
   printf("\nList , insert after key(4) : ");  
   insertAfter(4,7, 13);
   displayForward();
   printf("\nList  , after delete key(4) : ");  
   delete(4);
   displayForward();
}

Output:

List (First to Last): 
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
List (Last to first): 
[ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]
List , after deleting first record: 
[ (5,40) (4,1) (3,30) (2,20) (1,10) ]
List , after deleting last record: 
[ (5,40) (4,1) (3,30) (2,20) ]
List , insert after key(4) : 
[ (5,40) (4,1) (4,13) (3,30) (2,20) ]
List , after delete key(4) : 
[ (5,40) (4,13) (3,30) (2,20) ]

Stack:

  • A stack is a type of data structure that allows you to manipulate data at only one end. Only recently added data can be accessed.
  • The push-stop operations are linked so that only the last element can be pushed (added to the stack) and popped (removed from the stack)
  • A stack is also known as a LIFO (Last In First Out) data structure Basic Operations Two major stacking operations follow. Push the top stack element. Pop an item to pop an item off the top of the stack.
  • Below are some of the other operations the stack supports. Peek to get the top item on the stack.
  • isFull: Determines if the stack is full Empty: Determines if the stack is empty.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
// size of the stack
int size = 8;       
// stack storage
int intArray[8];     
// top of the stack
int top = -1;            
// Operation : Pop
// pop item from the top of the stack 
int pop() {
   //retrieve data and decrement the top by 1
   return intArray[top--];        
}
// Operation : Peek
// view the data at top of the stack 
int peek() {       
   //retrieve data from the top
   return intArray[top];
}
//Operation : isFull
//return true if stack is full 
bool isFull(){
   return (top == size-1);   }
// Operation : isEmpty
// return true if stack is empty 
bool isEmpty(){
   return (top == -1);
}
// Operation : Push
// push item on the top of the stack 
void push(int data) {
   if(!isFull()){
      // increment top by 1 and insert data 
      intArray[++top] = data;
   } else {
      printf("Cannot add data. Stack is full.\n");
   }      
}
main() {
   // push items on to the stack 
   push(3);
   push(5);
   push(9);
   push(1);
   push(12);
   push(15);
   printf("Element at top of the stack: %d\n" ,peek());
   printf("Elements: \n");
   // print stack data 
   while(!isEmpty()){
      int data = pop();
      printf("%d\n",data);
   }
   printf("Stack full: %s\n" , isFull()?"true":"false");
   printf("Stack empty: %s\n" , isEmpty()?"true":"false");
}

Output

Element at top of the stack: 15
Elements: 
15
12
1
9
5
3
Stack full: false
Stack empty: true

Queue:

  • The main difference between Queue and Stack is that Queue is based on FIFO (First In First Out) principle whereas Stack is based on LIFO (Last In First Out) principle.
  • Inserts and enqueues are basic operations that add elements to the end of a queue.
  •  Delete or Dequeue: First dequeue the item. This article uses arrays to implement queues.
  •  Below are some additional operations supported by queues? Peek to get the element at the beginning of the lineiis full Determines if the queueis fullisEmpty — make sure the queue is empty.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek(){
   return intArray[front];
}
bool isEmpty(){
   return itemCount == 0;
}
bool isFull(){
   return itemCount == MAX;
}
int size(){
   return itemCount;
}
void insert(int data){
   if(!isFull()){
      if(rear == MAX-1){
         rear = -1;            
      }       
      intArray[++rear] = data;
      itemCount++;
   }
}
int removeData(){
   int data = intArray[front++];
   if(front == MAX){
      front = 0;
   }
   itemCount--;
   return data;   }
int main() {
   /* insert 5 items */
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);
   // front : 0
   // rear  : 4
   // ------------------
   // index : 0 1 2 3 4 
   // ------------------
   // queue : 3 5 9 1 12
   insert(15);
   // front : 0
   // rear  : 5
   // ---------------------
   // index : 0 1 2 3 4  5 
   // ---------------------
   // queue : 3 5 9 1 12 15
int removeData(){
   int data = intArray[front++];
   if(front == MAX){
      front = 0;   }
   itemCount--;
   return data;  
}
int main() {
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);
insert(15);
if(isFull()){
      printf("Queue is full!\n");   
   }   int num = removeData();
   printf("Element removed: %d\n",num);
insert(16);
insert(17);
   insert(18);
printf("Element at front: %d\n",peek());
   printf("----------------------\n");
   printf("index : 5 4 3 2  1  0\n");
   printf("----------------------\n");
   printf("Queue:  ");
   while(!isEmpty()){
      int n = removeData();           
      printf("%d ",n);
   }   
}

Output:

The queue is full!
Element removed: 3
Element at the front: 5
index : 5 4 3 2 1 0
Queue: 5 9 1 12 15 16

Tree:

  • A tree represents nodes connected by edges. Binary search trees or binary trees are specifically mentioned.
  • It stores data using a unique data structure called a binary tree. A unique feature of binary trees is that each node cannot have more than three children.
  • moreDeletion is as fast on binary trees as on ordered arrays. The following are important terms related to trees.
  • Path: A path is a series of nodes along an edge of a tree. Root: The root is the node at the top of the tree.
  •  Every tree has exactly one root and only one path from the root node to all other nodes.
  • Parent node: A parent node can be accessed from any node except the root node a child node is a node below the specified node, connected by the bottom edge.
  • Leaf node: A leaf node is a node that has no children Subtree: A subtree represents the descendants of a node. Visit: If the control is on a node, visiting means checking its value.
  • Traverse: When traversing, nodes are traversed in the order specified. Level: A node's generations represented by its level. If the root node is level 0, its next child node level el 1.
  • Key: The key is the value of the node used as the basis for searching for the node. Binary search trees have special behaviour
  • A node's special behaviour has  a lower value than its parent, and the node's right child must have a higher value than  s parent  The following basic major operations on the tree are called element operations
  •  Find: Find tree items. Embed - Embeds the component in the tree Preorder Traversal: Traverse the tree in the order specified.
  •  Traversing the tree in an irregular order is called inorder traversal Use postorder traversal to traverse the tree in a postorder fashion.
  • Whenever a new component is to be added. First, locate where it belongs. If the data is less than the value, search for an empty location in the left subtree and insert the data
  • .Otherwise, insert the data and search for an empty location.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;
   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;
   //if tree is empty
   if(root == NULL){
      root = tempNode;
   }else {
      current = root;
      parent = NULL;
      while(1){                
         parent = current;
         //go to left of the tree
         if(data < parent->data){
            current = current->leftChild;  
   if(current == NULL){
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else{
            current = current->rightChild;
            //insert to the right
            if(current == NULL){
               parent->rightChild = tempNode;
               return;
}   }    }   }   }
struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
   while(current->data != data){
      if(current != NULL)
         printf("%d ",current->data); 
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }//else go to right tree
         else{                
            current = current->rightChild;
         }
         //not found
         if(current == NULL){
            return NULL;
         }
      }
  return current;
}
void preOrder(struct node* root){
   if(root!=NULL){
      printf("%d ",root->data);
      preOrder(root->leftChild);
      preOrder(root->rightChild);
   }  }
void inOrder(struct node* root){
   if(root!=NULL){
      inOrder(root->leftChild);
      printf("%d ",root->data);          
      inOrder(root->rightChild);
   }
}
void postOrder(struct node* root){
   if(root!=NULL){            
      postOrder(root->leftChild);
      postOrder(root->rightChild);
      printf("%d ",root->data);   }   }
void traverse(int traversalType){
   switch(traversalType){
      case 1:
         printf("\nPreorder traversal: ");
         preOrder(root);
         break;
      case 2:
         printf("\nInorder traversal: ");
         inOrder(root);
         break; }  }
int main()
{
insert(11);
   insert(20);
   insert(3);        
   insert(42);
  insert(54);
   insert(16);
   insert(32);
   insert(9);
   insert(4);
   insert(10);
  struct node * temp = search(32);
   if(temp!=NULL){
      printf("Element found.\n");
      printf("( %d )",temp->data);
      printf("\n");
   } else {
      printf("Element not found.\n");   }
   struct node *node1 = search(2);
   if(node1!=NULL){
      printf("Element found.\n");
      printf("( %d )",node1->data);
      printf("\n");
   } else {
      printf("Element not found.\n");   }
   traverse(1);
   traverse(2);
   traverse(3);       
}

Output:

Visiting elements: 11 20 42 Element found.(


32)
Visiting elements: 11 3 Element not found.
Preorder traversal: 11 3 9 4 10 20 16 42 32 54 
Inorder traversal: 3 4 9 10 11 16 20 32 42 54 
Postorder traversal: 4 10 9 3 16 32 54 42 20 11

Hash Table:

  • Regardless of the size of the hash table, inserts and lookups are extremely quick with the Hash Table data structure. It uses an array as a storage medium and a hashing technique to create an index into which an element is to be inserted or from which it is to be found, making it nearly constant or O(1) Hash Table.
  • Hashing is a technique for transforming a set of key values into a set of indexes for an array. To obtain a set of key values, we will make use of the modulo operator.
  •  Consider a 20-column hash table in which the following elements must be stored: The element has the format (key, value).fundamental operations A hash table's fundamental operations are listed below.
  • Lookup: Search the hash table for an element.
  • Insert is a function that adds a new element to the hash table. Delete is used to get rid of an item from the hash table.
  • Data item define a data item with some data and a key that can be used to search the hash table. Process of searching whenever an element needs to be found. Find the element by using the passed key's hash code as an index in the array. If the element is missing, use linear probing to bring it forward.
  • Whenever a new component is to be added. Find the index in the array by computing the hash code of the passed key and using that hash code as the index. If an element is found at the computed hash code, use linear probing to find an empty location.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define SIZE 20
struct DataItem {
   int data;   
   int key;
};
struct DataItem* hashArray[SIZE]; 
struct DataItem* dummyItem;
struct DataItem* item;
int hashCode(int key){
   return key % SIZE;
}
struct DataItem *search(int key){               
   //get the hash
   int hashIndex = hashCode(key);         
   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL){
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex]; 
      //go to next cell
      ++hashIndex;
      //wrap around the table
      hashIndex %= SIZE;
   }        
   return NULL;        
}
void insert(int key,int data){
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     
   //get the hash 
   int hashIndex = hashCode(key);
   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] !=NULL &&
      hashArray[hashIndex]->key != -1){
      //go to next cell
      ++hashIndex;
      //wrap around the table
      hashIndex %= SIZE;
   }
   hashArray[hashIndex] = item;        }
struct DataItem* delete(struct DataItem* item){
   int key = item->key;
   //get the hash 
   int hashIndex = hashCode(key);
   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL){
      if(hashArray[hashIndex]->key == key){
         struct DataItem* temp = hashArray[hashIndex]; 
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;  }
      //go to next cell
      ++hashIndex;
      //wrap around the table
      hashIndex %= SIZE;  }
void display(){
   int i=0;
   for(i=0; i<SIZE; i++) {
      if(hashArray[i] != NULL)
         printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data);
      else
         printf(" ~~ ");
   }
   printf("\n");
}
int main(){
   dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
   dummyItem->data = -1;  
   dummyItem->key = -1; 
   insert(1, 20);
   insert(2, 70);
   insert(42, 80);
   insert(4, 25);
   insert(12, 44);
   insert(14, 32);
   insert(17, 11);
   insert(13, 78);
   insert(37, 97);
   display();
   item = search(37);
   if(item != NULL){
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }


   delete(item);
   item = search(37);


   if(item != NULL){
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }
}

Output:

An element found: 97
Element not found

Recursion:

  • A programming language technique in which a function calls itself is called recursion. A recursive method is a function that calls itself In a recursive function, the following two characteristics must be present: base case(s) A set of rules that, after reducing the cases, result in a base case  Recursive Factorial
  • The factorial is one of the old-style illustrations of recursion. A factor is a non-negative number that satisfies the following conditions 0!=1

1!=1

n!= n * n-1!

  • "!" stands for faculty. Rule 3 is the factorial rule, and rules 1 and 2 are the base cases The Fibonacci series is another famous example of recursion.
  • The Fibonacci series is a set of integers that meet the following requirements Fibonacci is represented by the letter "F". F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 Rule 3 and Rule 1 are the Fibonacci rules and Rule 2 and Rule 1 are the base cases Example: F5 = 0 1, 1, 2, 3,