DSA Notes

• Primitive data structures: These are the basic data structures and are
directly operated upon by the machine instructions, which is in a
primitive level.
– Example: integers, floating point numbers, characters, string
constants, pointers
• Non-primitive data structures: It is a more sophisticated data structure
emphasizing on structuring of a group of homogeneous (same type) or
heterogeneous (different type) data items.
– Example: Array, list, files, linked list, trees and graphs
Stack
Algorithm for PUSH operation
• Step 1 − Checks if the stack is full.
• Step 2 − If the stack is full, produces an error and exit.
• Step 3 − If the stack is not full, increments top to point next empty
space.
• Step 4 − Adds data element to the stack location, where top is
pointing.
• Step 5 − Returns success.
Algorithm for POP operation
• Step 1 − Checks if the stack is empty.
• Step 2 − If the stack is empty, produces an error and exit.
• Step 3 − If the stack is not empty, accesses the data element at
which top is pointing.
• Step 4 − Decreases the value of top by 1.
• Step 5 − Returns success.
void push(int value){
• if(top == SIZE-1)
• cout<<"Stack is Full!!! Insertion is not possible!!!";
• else{
• stack[++top] = value;
• cout<<“Insertion success!!!";
• }
• }
void pop(){
• if(top == -1)
• cout<<“Stack is Empty!!! Deletion is not possible!!!";
• else{
• cout<<“Deleted :“<< stack[top--];
• }
• }
void display()
• {
• if(top == -1)
• cout<<“Stack is Empty!!!";
• else
• {
• cout<<“Stack elements are:\n";
• for(int i=top; i>=0; i--)
• cout<<stack[i];
• }
• }
Queue
Algorithm for ENQUEUE operation
• Check if the queue is full or not.
• If the queue is full, then print overflow error and exit the
program.
• If the queue is not full, then increment the rear or tail and add
the element.
Algorithm for DEQUEUE operation
• Check if the queue is empty or not.
• If the queue is empty, then print underflow error and exit the
program.
• If the queue is not empty, then print the element at the front or
head and increment the front or head.
void enQueue(int value)
• {
• if(rear == SIZE-1)
• cout<<“Queue is Full!!!
• Insertion is not possible!!!";
• else
• {
• if(front==-1)
• front=0;
• queue[++rear] = value;
• cout<<“Insertion success!!!";
• }
• }
void deQueue()
• {
• if(front == -1||front>rear)
• cout<<“Queue is Empty!!!
• Deletion is not possible!!!";
• else
• {
• cout<<“Deleted:“<<queue[front++];
• }
• cout<<“Deletion Success!!!”;
• }
void display()
• {
• if(rear == -1)
• cout<<"Queue is Empty!!!";
• else
• {
• cout<<“Queue elements are:“<<“\n”;
• for(int i=front; i<=rear; i++)
• cout<<queue[i];
• }
• }
Pointer And Array
#include<iostream.h>
void main()
{
int i;
int a[5] = {1, 2, 3, 4, 5};
int *p = a; // same as int*p = &a[0]
for (i=0; i<5; i++)
{
cout<<*p; // or cout<<*(p+i);
p++;
}
}
New Delete Operator
#include <iostream.h
void main ()
{
int n;
cout<<“Enter the number of elements:”;
cin>>n;
int *q = new int[n];
if (!p)
cout << "allocation of memory failed\n";
else
{
for (int i = 0; i < n; i++)
cin>>(q+i);
cout << "Value store in block of memory: ";
for (int i = 0; i < n; i++)
cout << *(q+i) << " ";
}
delete[] q; // freed the allocated memory
}
Linked Lists

Singly Linked List Addition

#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node* next;
};
struct Node *newNode(int data)
{
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = newNode(new_data);
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
struct Node* addTwoLists (struct Node* first, struct Node* second)
{
struct Node* res = NULL;
struct Node *temp, *prev = NULL;
int carry = 0, sum;
while (first != NULL || second != NULL)
{
sum = carry + (first? first->data: 0) + (second? second->data: 0);
carry = (sum >= 10)? 1 : 0;
sum = sum % 10;
temp = newNode(sum);
if(res == NULL)
res = temp;
else
prev->next = temp;
prev = temp;
if (first) first = first->next;
if (second) second = second->next;
}
if (carry > 0)
temp->next = newNode(carry);
return res;
}
void printList(struct Node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main(void)
{
struct Node* res = NULL;
struct Node* first = NULL;
struct Node* second = NULL;
push(&first, 6);
push(&first, 4);
push(&first, 9);
push(&first, 5);
push(&first, 7);
printf("First List is ");
printList(first);
push(&second, 4);
push(&second, 8);
printf("Second List is ");
printList(second);
res = addTwoLists(first, second);
printf("Resultant list is ");
printList(res);
return 0;
}
Singly Linked List Deletion
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void deleteNode(struct Node **head_ref, int key)
{
struct Node* temp = *head_ref, *prev;
if (temp != NULL && temp->data == key)
{
*head_ref = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
void printList(struct Node *node)
{
while (node != NULL)
{
printf(" %d ", node->data);
node = node->next;
}
}
int main()
{
struct Node* head = NULL;
push(&head, 7);
push(&head, 1);
push(&head, 3);
push(&head, 2);
puts("Created Linked List: ");
printList(head);
deleteNode(&head, 1);
puts("\nLinked List after Deletion of 1: ");
printList(head);
return 0;
}
Singly Linked List Selective Deletion
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void deleteNode(struct Node **head_ref, int position)
{
if (*head_ref == NULL)
return;
struct Node* temp = *head_ref;
if (position == 0)
{
*head_ref = temp->next;
free(temp);
return;
}
for (int i=0; temp!=NULL && i<position-1; i++)
temp = temp->next;
if (temp == NULL || temp->next == NULL)
return;
struct Node *next = temp->next->next;
free(temp->next);
temp->next = next;
}
void printList(struct Node *node)
{
while (node != NULL)
{
printf(" %d ", node->data);
node = node->next;
}
}
int main()
{
struct Node* head = NULL;
push(&head, 7);
push(&head, 1);
push(&head, 3);
push(&head, 2);
push(&head, 8);
puts("Created Linked List: ");
printList(head);
deleteNode(&head, 4);
puts("\nLinked List after Deletion at position 4: ");
printList(head);
return 0;
}
Singly Linked List Insertion
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void insertAfter(struct Node* prev_node, int new_data)
{
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
void append(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node *last = *head_ref; /* used in step 5*/
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
return;
}
void printList(struct Node *node)
{
while (node != NULL)
{
printf(" %d ", node->data);
node = node->next;
}
}
int main()
{
struct Node* head = NULL;
append(&head, 6);
push(&head, 7);
push(&head, 1);
append(&head, 4);
insertAfter(head->next, 8);
printf("\n Created Linked list is: ");
printList(head);
return 0;
}
Singly Linked List Iterative Search
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct Node
{
int key;
struct Node* next;
};
void push(struct Node** head_ref, int new_key)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->key = new_key;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
bool search(struct Node* head, int x)
{
struct Node* current = head;
while (current != NULL)
{
if (current->key == x)
return true;
current = current->next;
}
return false;
}
int main()
{
struct Node* head = NULL;
int x = 21;
14->21->11->30->10 */
push(&head, 10);
push(&head, 30);
push(&head, 11);
push(&head, 21);
push(&head, 14);
search(head, 21)? printf("Yes") : printf("No");
return 0;
}
Singly Linked List Recursive Search
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct Node
{
int key;
struct Node* next;
};
void push(struct Node** head_ref, int new_key)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->key = new_key;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
bool search(struct Node* head, int x)
{
if (head == NULL)
return false;
if (head->key == x)
return true;
return search(head->next, x);
}
int main()
{
struct Node* head = NULL;
int x = 21;
push(&head, 10);
push(&head, 30);
push(&head, 11);
push(&head, 21);
push(&head, 14);
search(head, 21)? printf("Yes") : printf("No");
return 0;
}
Merge And Quick Sort
Quick Sort Partition
void quicksort(int a[],int l,int r)
{
int s;
if(l<r)
{
s=partition(a,l,r);
quicksort(a,l,s-1);
quicksort(a,s+1,r);
}
}
int partition(int a[],int left,int right)
{
int p,i,j,t;
i=left+1;
j=right;
p=a[left];
while(j>=i)// i and j interchange
{
while(a[i]<=p)
i++;
while(a[j]>p)
j--;
If(i<j)//i hold grater than pivot
{ //j hold less than pivot
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
t=a[left]; a[left]=a[j]; a[j]=t; return j;
}
Sorting
Selection Sort
void selection_sort(int a[], int n)
{
int i,j,min,tmp;
for(i=0;i<=n-2;i++)
{
min=i;
for( j =i+1; j <=n-1; j++)
{
if(a[ j ]<a[min])
min = j;
}
if(min!=i)
{
tmp=a[i];
a[i]=a[min];
a[min]=tmp;
}}}
Bubble Sorting
void bubble_sort(int a[], int n) {
int i, j, temp;
for (i = 0 ; i <= ( n - 2 ); i++) {
for (j = 0 ; j<= n - 2 - i; k++) {
if (a[ j ] > a[ j + 1]){
temp = a[ j ]; a[ j ] = a[ j +1]; a[ j +1] = temp;
}}}}
Insertion Sort
void insertion_sort(int a[], int n){
int i, j, key;
for(i=1;i<n; i++){
key=a[i];
for(j=i-1;((j>=0)&&(a[j]>key));j--){
a[j+1]=a[j];
}
a[j+1]=key;
}}
Tree

Sequential Representation of Binary Trees

Advantages:
• Direct access to any node.
• Finding parent, left or right child of a node is fast
Disadvantages:
• Wastage of memory
• Depth of a tree or no. of nodes must be known in advance.
• Insertion or deletion of a node is costlier.

Advantages:
• No wastage of memory
• Prior knowledge on depth of a tree is not needed.
• Insertion or deletion can be done without moving other nodes.
Disadvantages:
• Direct access to a node is not possible.
• Needs additional space in each node for representing left and right sub
trees.
Binary Tree
Structure of Node in Binary Tree ADT
struct node{
int data;
struct node *left;
struct node *right; };
Traversal
InOrder Traversal
void inorder (struct node *temp)
{ if(temp!=NULL)
{ inorder(temp->left);
cout<<temp->data;
inorder(temp->right);
}}
PreOrder Traversal
void preorder (struct node *temp)
{ if(temp!=NULL)
{ cout<<temp->data;
preorder(temp->left);
preorder(temp->right);
}}
PostOrder Traversal
void postorder (struct node *temp)
{ if(temp!=NULL)
{ postorder(temp->left);
postorder(temp->right);
cout<<temp->data;
}}
Binary Search Tree
Binary Search Tree (BST) is a binary tree which has the following properties:
• The left sub tree of a node contains only nodes with keys less than the
root node's key.
• The right sub tree of a node contains only nodes with keys greater than
the root node's key.
• Both the left and right sub trees must also be binary search trees.
• There must be no duplicate nodes.
BST Insertion
void insert(struct node *root, struct node *temp)
{
if (temp->data < root->data)
{
if(root -> lchild == NULL)
root->lchild = temp;
else
insert(root->lchild, temp);
}
else if(temp->data > root->data)
{
if(root->rchild == NULL)
root->rchild = temp;
else
insert(root->rchild, temp);
}
else
printf("\nDuplicate entry..\n"); }
BST Searching
void search(struct node *root, int key)
{ struct node *par;
par = root, temp = root;
if(key == root->data)
printf("%d is present as the root node",key);
else
{
while((key!=temp->data)&&(temp!=NULL))
{
par = temp;
if(key < temp->data)
{ temp = temp->lchild;
if(key == temp->data)
printf("%d is present as left child of %d",key,par->data);
}
else if(key > temp->data)
{ temp = temp->rchild;
if(key == temp->data)
printf("%d is present as right child of %d",key,par->data);
}
}
if(temp==NULL) printf("%d is not present",key);
}
}
BST Deletion
void delete(struct node *root,int key) {
struct node *par=NULL,*succ=NULL;
par = root, temp = root;
while((key!=temp->data)&&(temp!=NULL)) {
par=temp;
if(key < temp->data) temp=temp->lchild;
else if(key > temp->data) temp=temp->rchild; }

if(temp==NULL) { printf("%d is not present",key); return; }

if(temp->lchild == NULL && temp->rchild == NULL) {
if(par->lchild == temp) par->lchild = NULL;
else par->rchild = NULL;
printf("%d deleted“ ,temp->data);
free(temp);
return; }
if(temp->lchild != NULL && temp->rchild == NULL) {
if(par->lchild == temp) par->lchild=temp->lchild;
else par->rchild=temp->lchild;
printf("%d deleted", temp->data);
free(temp); return; }
if(temp->lchild == NULL && temp->rchild != NULL) {
if(par->lchild == temp) par->lchild = temp->rchild;
else par->rchild = temp->rchild;
printf("%d deleted", temp->data); free(temp); return;
}
if(temp->lchild != NULL && temp->rchild != NULL)
{ par = temp;
succ = temp->rchild;
while(succ->lchild != NULL)
{ par = succ; succ = succ->lchild; }
temp->data = succ->data;
if(par->lchild == succ) par->lchild = NULL;
else par->rchild = NULL;
printf("%d deleted" , key);
free(succ); return; } }
BST Minimum/Maximum
void findmin(struct node *root)
{
temp=root;
while(temp->lchild != NULL)
temp=temp->lchild;
printf("The Minimum value node is %d", temp->data);
}
void findmax(struct node *root)
{
temp=root;
while(temp->rchild != NULL)
temp = temp->rchild;
printf("The Maximum value node is %d", temp->data);
}