seaching
linear search (we have to visit to each of the elements and we then have to compare
the element with searched element)
Binary search(first of all arrage all the elements in the ascending order and then
perform search that is binary search)
steps to perform binary search
1. arrange all the elements in the ascending order
2. low=0
3. high=size-1
4. mid=(low+high)/2;
5. key (element to be searched)
#include<iostream>
#include<conio.h>
using namespace std
int binarySearch(int arr[],int key, int low, int high)
{
while(low<=high)
{
int mid=(low+high)/2;
if(arr[mid]==key)
return mid;
if(arr[mid]<key)
low=mid+1;
else
high=mid-1
}
return -1
}
int main()
{
int arr[]={1,2,3,4,5,6,7,8,9};
int size=sizeof(arr);
int result=binarySearch(arr,5,0,size-1);
if(result==-1)
{
cout<<"element not found";
}
else
{
cout<<element found at<<result;
}
return 0;
}
LinkedList?
it is collection of data and the data is stored in a node form where each node
contains data and address of next node
and all the nodes are connected together
types of linked list
1. singly linkedList
2. Doubly LinkedList
3. Circular LinkedList
steps
1 create a structure
struct node
{
int data;
struct node *next;
}
Singly LinkedList
// creating members of singly LinkedList
struct node *head;
struct node *one=NULL;
struct node *two=NULL;
struct node *three=NULL;
//now I will allocate the memory to each of the nodes
one=malloc(sizeof(struct node));
two=malloc(sizeof(struct node));
three=malloc(sizeof(struct node));
one->data=1;
two->data=2;
three->data=3;
//make a connection between all the nodes
one->next=two;
two->next->three;
three->next=NULL;
//save the address of the first node in the head node;
head=one;
2. doubly linkedList----we add a pointer to the previous node in a doubly-
LinkedList. that why we can go in both the directions the backword direction or in
the forward direction.
//1. create a structure of the doubly linkedList
struct node
{
int data;
struct node *next;
struct node *prev;
}
//creating different members of doubly linkedList
struct node *head;
struct node *one=NULL;
struct node *two=NULL;
struct node *three=NULL;
// we have to allocate the memory to each of the nodes of doubly linked list;
one=malloc(sizeof(struct node));
two=malloc(sizeof(struct node));
three=malloc(sizeof(struct node));
//assign the data to nodes
one->data=1;
two->data=2;
three->data=3;
//now we have to connect all the nodes as doubly linkedList
one->next=two;
one->prev=NULL;
two->next=three;
two->prev=one;
three->next=NULL;
three->prev=two;
//now save the address of the first node in the head node;
head=one;
3. circular linkedList----- it is also a type of linkedList in which the last node
or the element is connected to the first node or first element.
it can be implemented using singly LinkedList or using Doubly LinkedList
//create a node or circular linked list using singly linkedList
struct node
{
int data;
struct node *next;
}
//create three members of the circular singly linkedList
struct node *head;
struct node *one=NULL;
struct node *two=NULL;
struct node *three=NULL;
//allocating the memory to each of the nodes in the circular singly linkedList
one=malloc(sizeof(struct node));
two=malloc(sizeof(struct node));
three=malloc(sizeof(struct node));
//assign the values to each of the nodes in the circular singly linkedList
one->data=1;
two->data=2;
three->data=3;
//connect each of the singly linkedList in a circular fashion
one->next=two;
two->next=three;
three->next=one;
//save the address of the first node in the head node.
assignment
Implement the circular LinkedList in Doubly LinkedList fashion
//create a structure
struct node
{
int data;
struct node *next;
struct node * prev;
}
//create three members of circular linkedList
struct node *head;
struct node *one=NULL;
struct node *two=NULL;
struct node *three=NULL;
//allcate the memory
one=malloc(sizeof(struct node));
two=malloc(sizeof(struct node));
three=malloc(sizeof(struct node));
//assign the values
one->data=1;
two->data=2;
three->data=3;
//connect all the nodes in a circular doubly linked list fashion
one->next=two;
one->prev=NULL;
two->next=three;
three->prev=two;
three->next=one;
//save the address of first node
head=one;
operations on LinkedList
1. traversal---we have to access each of the element from a linkedList;
2. insertion----we can add new element to the linkedList
3. deletion-----we can remove the existing element from the linkedList
4. search an element from a linkedList
1. traversal---we have to access each of the element from a linkedList;
struct node *temp=head;
while(temp!=NULL)
{
cout<<temp->data;
temp=temp->next;
}
2. insertion of elements in the linkedList
we can insert the values in the linkedList in three ways
a. we can insert element at the beginining
b. we can insert the element at the end
c. we can insert the element in the middle
a. we can insert element at the beginining
1. create a new node and allocate the memory
2. store the data
3. change the next of the new node to point to head;
4. save the address of the new node in the head node.
struct node *newNode;
newNode=malloc(sizeof(struct node));
newNode->data=4;
neeNode->next=head;
head=newNode;
b. we can insert the element at the end
1. create a new node and allocate the memory to the new node;
2. store the data
3. visit to last node
4. change the next of last node to the newly created node
struct node *newNode;
newNode=malloc(sizeof(struct node));
newNode->data-4;
newNode->next=NULL;
struct node *temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newNode;
c. we can insert the element in the middle
1. create a newNode and allocate the memory
2. store the data
3. visit to the node just before the required position of the newNode
4. change the next pointer to add new node in between
struct node *newNode;
newNode=malloc(sizeof(struct node));
newNode->data=4;
struct node *temp=head;
for(int i=2;i<position;i++)
{
if(temp->next!=NULL)
{
temp=temp->next;
}
}
newNode->next=temp->next;
temp->next=newNode;
2.deletion-----we can remove the existing element from the linkedList
a. delete from the beginning
head=head->next;
b. delete from the last
1. visit up to the node before last node
2. change the next pointer to null
struct node *temp=head;
while(temp->next->next!=NULL)
{
temp=temp->next;
}
temp->next=NULL;
assignment
c. delete the node in between
1. visit up to the second last element
2. change the pointer to discard the node from the list
sorting
type of sorting
1. bubble sort
steps
1. 12,1,3,2,5,9,4
there are 7 elements
iterations=size-1
void sortBubble(int arr[], int size)
{
for(int steps=0;step<size;step++)
{
for(int i=0;i<size-step;i++)
{
if(arr[i]>arr[i+1])
{
int temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
Selection sort---->whatever the array is, we have to select the smallest element
from the unsorted array then we have to put that element at the beginning
number of iterations will be size-1
create a function of selection sort
void sortSelection(int arr[], int size)
{
for(int step=0;step<size-1;step++)
{
int min=step;
for(int i=step+1;i<size;i++)
{
if(arr[i]<arr[min])
}
swap(&arr[min],&arr[step])
}
}
Tree-----
graph----
