DS Handbook V1

A data structure is a particular way of organizing data in a computer so that it can be used effectively.

Complexity Graph:

Data Structure Operations:-

Traversing()

Searching()

Inserting()

Updating()

Deleting()

Sorting()

Merging()

An Abstract Data type (ADT) is a type for objects whose behaviour is defined by a set of values and a set of operations. ADT = Type + Function Names + Behaviour of each

Array

Searching

Linear Search


#include<iostream>
using namespace std;
int main()
{
  int arr[10]={10,20,30,40,50,60,70,80,90};
  int num = 30,index;
  for(int i=0; i<10; i++)
  {
    if(arr[i]==num)
    {
      index = i;
      break;
    }
  }
  cout<<"\nFound at Index No."<<index;
  cout<<endl;
  return 0;
}

The time complexity of the above algorithm is O(n) Space complexity: O(1)

Binary Search


#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int l, int r, int x){
if (r >= l) { //we are not using (l+r)/2 because
int mid = l + (r - l) / 2; //it fails if the sum of low and high is
if (arr[mid] == x) //greater than the maximum positive int value(231 – 1 )
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main(void){
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}

Average complexity: O(log n) Space complexity: O(1) For Binary Search the array should be sorted first.

Sorting

Internal Sort: All data items are held in main memory and no secondary memory is required for this sorting process. Example➖

SELECTION - Selection sort algorithm, Heap Sort algorithm

INSERTION:- Insertion sort algorithm, Shell Sort algorithm

EXCHANGE:- Bubble Sort Algorithm, Quick sort algorithm

External Sort: Sorting a large amount of data requires external or secondary memory. This process uses external memory such as HDD, to store the data which is not fit into the main memory. So, primary memory holds the currently being sorted data only. Ex- Merge Sort

Insertion Sort


#include <bits/stdc++.h>
using namespace std;
void insertionSort(int arr[], int n){
int i, key, j;
for (i = 1; i < n; i++){
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n){
int i;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main(){
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}

Time Complexity: O(n^2) Auxiliary Space: O(1)

Bubble Sort


#include <bits/stdc++.h>
using namespace std;
void swap(int *xp, int *yp){
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubbleSort(int arr[], int n){
int i, j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
void printArray(int arr[], int size){
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main(){
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
cout<<"Sorted array: \n";
printArray(arr, n);
return 0;
}

If you want to swap the values without any additional variables follow this guide

Insertion


#include <stdio.h>
int main(){ //Don't inititate with static size
int LA[] = {1,3,5,7,8}; //n is element number in array
int item = 10, k = 3, n = 5;//item is to insert at k place
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++)
printf("LA[%d] = %d \n", i, LA[i]);
//Shifting the rest of array to insert the item
n = n + 1;
while( j >= k){ //From k elements all the elements should be shifted
LA[j+1] = LA[j];
j = j - 1;
}
LA[k] = item; //Then we will put item in k place
printf("The array elements after insertion :\n");
for(i = 0; i<n; i++)
printf("LA[%d] = %d \n", i, LA[i]);
} //To get rid of stack smash error put 10 or more at LA[10] like this at the time of initialization

Deletion


#include <stdio.h>
int main(){
int LA[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++)
printf("LA[%d] = %d \n", i, LA[i]);
//Shifting elements to left starts here
j = k;
while( j < n){
LA[j-1] = LA[j]; j = j + 1;
}
n = n -1;
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++)
printf("LA[%d] = %d \n", i, LA[i]);
}

A sparse matrix is a matrix that is comprised of mostly zero values. Representing a sparse matrix by a 2D array leads to the wastage of lots of memory as zeroes in the matrix are of no use in most cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means storing non-zero elements with triples- (Row, Column, value). It is used to solve partial differential equations by using the finite element method.

Recursion

Some computer programming languages allow a module or function to call itself. This technique is known as recursion.

Properties

A recursive function can go infinite like a loop. To avoid infinite running of a recursive function, there are two properties that a recursive function must have −

Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.

Progressive approach − recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

Examples


int recursive_sum(int n)
{if(n≤0){

return 0;
}
return n+recursive_sum(n-1);
}
//TIME COMPLEXITY-O(n)

recursive_sum(5) →15


bool fun(int *arr,int a){
if(a==1){return 1;}
return (arr[0]<arr[1]&&fun(arr+1,a-1));}
// to check if a given array is sorted using recursion

Linked List

Singly Linked List


#include <iostream>
using namespace std;
struct Node{
int data;
struct Node *next;
}*head = NULL;  //Declare Globally is easy so that you don't
//have to pass a pointer in every function.
void insertAtBeginning(int value){
Node *newNode = new Node();
newNode->data = value;
if(head==NULL){head=newNode; newNode->next=NULL;}
else{newNode->next = head; head=newNode;}
cout<<"Node Inserted at Beginning. Value: "<<newNode->data<<endl;
}
void insertAtEnd(int value){
Node *newNode = new Node();  //Allocates memory
newNode->data = value;
newNode->next = NULL;
if(head==NULL){head=newNode; newNode->next=NULL;}
else{ struct Node *temp=head;
while(temp->next!=NULL){temp=temp->next;}
temp->next = newNode;}
cout<<"Node Inserted at End. Value: "<<newNode->data<<endl;
}
void insertBetween(int value,int loc){  //prev_ptr is back node of inserted Node
struct Node *curr_ptr=head, *prev_ptr;  //curr_ptr is front node of inserted Node
Node *newNode = new Node();
newNode->data = value;
if(head==NULL){head=newNode; newNode->next=NULL;}
else{for(int i=1;i<loc;i++){prev_ptr = curr_ptr;
curr_ptr = curr_ptr->next;
}prev_ptr->next = newNode;
newNode->next = curr_ptr;
}cout<<"Node Inserted. Value: "<<newNode->data<<" after the node value: "<<prev_ptr->data<<endl;
}
void removeBeginning(){if(head==NULL){cout<<"Linked List is Empty!!\n";}
else{struct Node *temp = head;
if(temp->next==NULL){head==NULL; free(temp);}
else{head=temp->next; free(temp);}
cout<<"Front Node Deleted"<<endl;}
}
void removeEnd(){if(head==NULL){cout<<"Linked List is Empty!!\n";}
else{struct Node *temp1=head, *temp2; //temp1 will be deleted
if(temp1->next==NULL){head==NULL;} //temp2 is the back node of temp1
else{ while(temp1->next!=NULL){temp2=temp1;temp1=temp1->next;}
temp2->next = NULL;
}free(temp1);
cout<<"End Node Deleted"<<endl;}
}
void removeSpecific(int delValue){ struct Node *temp1=head, *temp2;
while(temp1->data!=delValue){if(temp1->next==NULL){cout<<"Given node value not found"<<endl; return;}
temp2=temp1;
temp1=temp1->next;
}temp2->next=temp1->next; free(temp1);
cout<<"Specified Node Deleted"<<endl;
}
void display(){if(head==NULL){cout<<"Linked List is Empty!!"<<endl;}
else{ struct Node *temp=head;
cout<<"List elements are: \n";
while(temp->next!=NULL){cout<<temp->data<<" --> "; temp=temp->next;
}cout<<temp->data<<" --> NULL\n";}
}
int main()
{   insertAtBeginning(4);
display();
insertAtEnd(5);
display();
insertAtEnd(7);
display();
insertBetween(6,3); //1 means 1nd Node as the for loop starts with i=1
display();
insertAtEnd(8);
insertAtEnd(9);
insertAtEnd(10);
display();
removeBeginning();
display();
removeEnd();
display();
removeSpecific(6);
display();
}

Doubly Linked List

Stack

Array Implementation


#include <iostream>
using namespace std;
int SIZE=5;
int stackArr[5],top=-1;
void push(int value){
if(top==SIZE-1) cout<<"Stack Overflow"<<endl;
else{top++;
stackArr[top]=value;}
};
void pop(){
if(top==-1) cout<<"Stack Underflow"<<endl;
else{top--;}
};
void display(){
if(top==-1) cout<<"Stack is empty"<<endl;
else{for(int i=top;i>=0;i--){
cout<<"|"<<stackArr[i]<<"|"<<endl;}
}
};
int main()
{
push(40);push(50);push(70);push(80);push(90);
//display();
pop();
display();
}

Linked List Implementation

In Stack push() will be the same as Linked List insertBeginning() function. Also pop() will be the same as removeFront() function in Linked List and display() will be the same as Linked List Display() Function.

Queue

In a queue data structure, the insertion operation is performed at a position which is known as 'rear' and the deletion operation is performed at a position which is known as 'front’.

Enqueue: inserts an element at the end of the list (called the rear) Dequeue: deletes (and returns) the element at the start of the list (called the front). Peek: Get the front element

Array Implementation


//Normal Queue
#include <iostream>
using namespace std;
int SIZE=5;
int queueArr[5],rear=-1,front=-1;
void enqueue(int value){
if(rear==SIZE-1) cout<<"Queue Overflow"<<endl;
else if(rear==-1 && front==-1) { rear=front=0;
queueArr[rear]=value;}
else{rear++;
queueArr[rear]=value;}
};
int dequeue(){
int num;
if(rear==-1 && front==-1) cout<<"Queue Underflow"<<endl;
else{num=queueArr[front];
front++;}
return num;
};
void display(){
if(rear==-1 && front==-1)
cout<<"Queue is Empty"<<endl;
else{ //cout<<rear<<endl<<front<<endl;
cout<<"Rear |";
for(int i=rear;i>=front;i--) {
cout<<queueArr[i]<<" |";}
cout<<" Front"<<endl;}
};
int main(){
enqueue(50);enqueue(60);enqueue(70);enqueue(80);enqueue(90);
//display();
dequeue();
display();
}

For Circular Queue Remind: (rear+1)%SIZE

Linked List Implementation

In Queue enqueue() will be the same as Linked List insertBeginning() function. Also dequeue() will be the same as the removeEnd() function in Linked List and display() will be the same as Linked List Display() Function.

Trees

Binary Trees

Traversal:- In-Order(LVR) Pre-Order(VLR) Post-Order(LRV) where L=left , R=Right and V=Parent or root. Time Complexity: O(n)


#include <iostream>
using namespace std;
struct Node {
	int data;
	struct Node *left, *right;
};//Utility function to create a new tree node
Node* newNode(int data){
	Node* temp = new Node;
	temp->data = data;
	temp->left = temp->right = NULL;
	return temp;
}
void printPostorder(struct Node* node){ //LRV
	if (node == NULL)
		return;
	printPostorder(node->left);
	printPostorder(node->right);
	cout << node->data << " ";
}
void printInorder(struct Node* node) { //LVR
	if (node == NULL)
		return;
	printInorder(node->left);
	cout << node->data << " ";
	printInorder(node->right);
}
void printPreorder(struct Node* node){ //VLR
	if (node == NULL)
		return;
	cout << node->data << " ";
	printPreorder(node->left);
	printPreorder(node->right);
}
int main()
{
	struct Node* root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);
	cout << "\nPreorder traversal of binary tree is \n";
	printPreorder(root);
	cout << "\nInorder traversal of binary tree is \n";
	printInorder(root);
	cout << "\nPostorder traversal of binary tree is \n";
	printPostorder(root);
	return 0;
}

Time Complexity: O(n) Auxiliary Space: If we don’t consider the size of the stack for function calls then O(1) otherwise O(h) where h is the height of the tree.

Level Order Traversal :


#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node left, right;
};
void printCurrentLevel(node root, int level);
int height(node node);
node* newNode(int data);
void printLevelOrder(node* root){
int h = height(root);
int i;
for (i = 1; i <= h; i++)
printCurrentLevel(root, i);
}
void printCurrentLevel(node* root, int level){
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
printCurrentLevel(root->left, level - 1);
printCurrentLevel(root->right, level - 1);
}
}
int height(node* node){
if (node == NULL)
return 0;
else {
int lheight = height(node->left);
int rheight = height(node->right);
if (lheight > rheight) {
return (lheight + 1);
}
else {
return (rheight + 1);
}
}
}
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
int main()
{
node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "Level Order traversal of binary tree is \n";
printLevelOrder(root);
return 0;
}

Time Complexity: O(n^2) in the worst case. Takes O(n) time where n is the number of nodes. Space Complexity: O(n) in the worst case. For a Balanced tree, the call stack uses O(log n) space

Dynamic Programming

Dynamic programming is a technique that breaks the problems into sub-problems and saves the result for future purposes so that we do not need to compute the result again. The subproblems are optimized to optimize the overall solution

//Here is a normal call to find a Fibonacci number

Time Complexity=O(2^n)

//Notice how the number of steps have been drastically reduced

Time Complexity=O(n)

Memoization

memoization is an optimization technique used primarily to speed up programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again .


int fibonacci(int n)
{
map<int, int> values;
if (n==0 || n==1)//base case
return n;
map<int,int>iter = values.find(n);
if (iter == values.end())//value not stored in the map
{
return values[n] = fibonacci(n-1)+fibonacci(n-2);//insert value inside the map,and return
}
else//value found inside the map
{
return iter->second;
}
}