All language subtitles for Data Structures and Algorithms in Python for Beginners - 2022 _ Great Learning - English

data structures and algorithms in python

is a starter friendly course where

learners can begin from very basic

concepts like introduction to data

structures types of data structures like

array stack queue and linked list with

introduction examples and implementation

using python programming language

proceeding with concepts you can also

learn regarding tree data structures

like binary tree binary search tree

creation traversal and implementation

followed by graph and hash tables are

also taught

coming to the algorithmic part we start

with finding time and space complexity

of algorithms searching and sorting

concepts like binary search linear

search incision sort and quick sort with

implementation using python programming

language are also included

towards the end of this course you will

learn and implement different

programming approaches like divide and

conquer greedy method and dynamic

programming with examples like merge

sort minimum spanning tree algorithm and

towers of hanoi concepts using python

programming language so why wait let's

start learning data structures and

algorithms in python on great learning

[Music]

if you haven't subscribed for our

channel yet i would request you to hit

the subscribe button and turn on

notification bell so that you don't miss

any new updates or video releases from

great learning if you enjoy this video

show us some love and do like this video

knowledge increases by sharing so make

sure you share this video with your

friends and colleague make sure you

comment on this video any queries or

suggestions i'll be more than happy to

respond to all of them hello everyone

welcome to this video where we'll be

learning regarding data structures and

algorithms in python so python is a very

well known programming language where

we'll be using that in various domains

so nowadays we are using python in data

science in order to visualize data and

analyze them and also various others

naming artificial intelligence machine

learning and web development also it is

used as server sides crypto so knowing

all about python so we have to know what

are the different data structures and

what are the algorithms which we

can analyze and build using python so

the agenda for this particular video

would be will be first learning what is

a data structure so introduction

incomplete for data structure in python

is given so followed by what are the

inbuilt data structures which is

available in python so python is a

very good interactive programming

language which also has its inbuilt and

own

kind of data structures in it so we'll

be learning that with a tad bit of

implementation and with simple examples

so followed by will be starting

data structures first then algorithms so

arrays will be the first element which

will be learning and then followed by

stack and

queue and again will be learning

regarding linked list followed by trees

and graphs so binary tree binary search

tree graph hashing and later part would

be algorithm analysis right so we'll be

starting with linear and binary search

and then we'll be learning sorting what

are the different shots we can do and we

also have a simple examples for all

these

topics which we are covering in this

video and we also show implementation

how can you put up into an ide with

respect to python either it can be

pycharm or it can be google collab or

various other ids available for python

so we'll be showing accordingly how can

you implement these concepts in python

so at last you have divide and conquer

approach

to programming right how do you divide

and conquer so it is one kind of

algorithm where you can just

know how does it work and then it goes

next with greedy approach and then

ending with dynamic programming so all

these topics are covered in this video

in order to give you a basic and wide

knowledge about the data structures and

algorithms

in python programming language so let's

start this video with the first topic

that is introduction to data structure

the first thing that you really have to

think about whenever the term data

structure comes into your head is what

is a data structure because it is a term

that gets thrown around the entire world

of programming and if you're a

non-technical person who's ever gone for

a technical interview either for a

programming job or something along the

lines of that data structures are

extremely important for interviews and

why is that right let's answer these

questions first of all what is a data

structure a data structure is basically

a way of how we can store data in a

structured manner in fact the answer

lies in the name itself right so data

structures not only provide a very good

and an efficient way to actually store

your data but also whenever it is

required right that is when it shows its

power that is when it brings out all the

efficiency that i just spoke about now

and then when you think about it having

a structured way of approaching things

not only in the world of programming but

works everywhere right think about

organizing your books in a bookshelf or

maybe a kitchen cabinet right but then

when you when you again think about data

structures as a whole when you come to

programming languages there's varieties

of data structures right

in your book rack you'll only have books

there's a good chance in your kitchen

cabinet you might have only stuff that's

required for your kitchen right but in a

data structure when you're thinking

about a programming language here things

will slightly change and there is a good

chance that there can be a lot more

things at play right think about not

only how to store data but how to

organize them how to access them and how

efficient is this entire process of

storing organizing and accessing going

to be right this is what makes up a data

structure to give you an example just

like the book example that i just told

you about think about organizing fruits

in a basket right because this is

exactly what uh happens in our case as

well right look at your screen right now

you'll see a couple of bananas apples

watermelons and mangoes that are

arranged in their own baskets right now

if everything was jumbled if i asked you

to put it back like that you can do it

right exactly

now in the case of a data structure in

python what happens is the data that it

sees is usually numbers or character

data right now if it's an integer it can

be one two three four five if it's a

floating point number it can be three

point one four four point nine six point

nine five point eight anything like that

right and then of course if you have any

sort of string data for example hi my

name is anirudh rao right

so uh just similar to organizing these

there also we each have baskets where if

python sees a data which happens to be

either integer floating or anything like

that it will automatically try to put it

in these baskets that we have now to

dive right into the details of it to

understand what exactly is it that we're

doing with respect to the data

structures that are present uh in python

and many other programming languages

ladies and gentlemen you have to think

about two ways of how data structures

are meant to be used and of course the

purpose of it first of all you have

built-in data structures and

user-defined data structures see enough

built-in data structures as the name

itself suggests right it comes built in

with the programming languages it talks

about something fundamental it talks

about a scaffolding structure or it

talks about an already ready syntax that

you guys have to use to just ensure that

you know your storage options are being

met and of course whatever it is that

you want to use the storage for you have

time to concentrate on those

applications rather than breaking your

head on how to store the data right so

that's built in data structures uh user

defined data structures are some of

these data structures which we require

in a case where we have

not just a lot of data but sometimes you

have a solution which will require you

to take a non-linear approach of how you

should not only store data but process

them and derive insights out of them in

those cases right user-defined data

structures are very much useful now if

you take a look at all the built-in data

structures and the user-defined data

structures especially we have in python

you'll see that the built-in data

structures of course apart from the in

float string and all those you'll see

list dictionary tuple and set and then

take a look at user-defined data

structures use user-defined data

structures i've given you four on the

screen right now but you can have any

number of user-defined data structures

for that programming language right for

example python itself has a lot more

than four but these four happen to be so

so popular that you guys have to know

about them so all right guys now we will

take a look at all the built-in data

structures that we just uh discussed

right now whenever the talk is about

building data structures the first

question you really must ask yourself is

what is a built-in data structure or why

is it even called a built-in data

structure right now a built-in data

structure basically is present natively

in the python library as well right so

when you take a look at all these

various uh

you know built-in structures that we're

discussing be it lists be tuple set

dictionary whatever it is uh all of

these are present directly uh for usage

right you really do not have to install

anything on top of python or you know

work with any sort of dependencies to

work with these as well right fantastic

now the first data structure that you

see on your screen is lists so what are

lessons

list as the name itself suggests you

know whenever you're trying to make a

list of things what are you trying to do

you are sequentially trying to organize

something in an orderly fashion or

you're trying to arrange something in a

fashion where the next time you take a

look at the list you understand what's

going on similarly right it's not the

exact analogy but similarly here as well

with respect to list we have a storage

in the form of an array-like structure

right uh with respect to list in python

the advantage here is that every single

element in the list right all of these

positions are indexed so if i wanted the

first element the second element the

last element or any element that is

present in an entire list i can actually

use its index position it's addressing

and eventually start picking that up

right in fact there's an example on your

screen right now we have a sample list

here which contains of uh you know all

the types of data that we can have right

we can have integers we can have

floating point numbers and look at this

ladies and gentlemen we can also have a

string data type right and of course all

of these are completely

valid and all of these are output as an

actual list as well so this is something

you really have to know in terms of

lists

the next thing that we're going to take

a look at and discuss is dictionaries

now think about a dictionary at your

home right before even understanding

what's present on the screen if you take

a look at a dictionary if i have to

search for a word in that dictionary

how do i go about moving around the

dictionary right if my word usually

starts from s i go to that index

position i open all the pages that start

from s and then i alphabetically start

looking for the word right

the working of dictionary in python is

also similar where we take the concept

from the actual example that i just told

you right so we have something called as

key items and we have something called

as the values that correspond to these

key items right uh think about uh

structured data right maybe your name uh

your phone number and your con and your

email address and your aadhar card

number let's just say now if you have to

list all of these for your entire family

members uh you will have it in an order

or even if it's unordered uh you will

have it let's just say there are four

people there right so you can pick up

each one of the four as and when you

require right similarly here in

dictionaries we have something called as

a key and a key is basically associated

with the value so if you have to access

the value you can just look for the key

and eventually the key is hooked up to

the value where you can find out uh the

data that is stored uh in the place

that's mapped for that key right uh so

if you're wondering about these pairings

how many pairings can we have or can

they be accessed or can they be added as

and when required of course with respect

to dictionaries all these key value

pairs can be added accessed modified and

removed as in when you choose that's a

huge advantage here right now take a

look at the example on your screen now

in fact here we have a dictionary which

contains of two items when i say two

items i'm meaning two key value pairs

the first uh the first item that we're

talking about is basically an apple but

the key associated with respect to apple

is first the second item that we're

talking about is ball but the key

associated with ball is in second right

that's the output that you can see so i

hope you're clear with dictionaries the

next interesting data structure that

we're going to take a look at in python

has to be double now ladies and

gentlemen tuple is literally the most

used data structure we have in python

now that we just took a look at list one

thing you really have to understand

about tuple is that the working is very

very similar to what the lists provide

us but then but then ladies and

gentlemen this is a very important point

but here in terms of a tuple you really

cannot change the value of that

particular tuple where it is in

execution or when it is underway so

if i have a tuple called a sample tuple

one two three and then if i want to

change it while it's executing or if i

want to change it and uh you know just

add in more details or remove elements

as such that is not possible why because

tuple is an immutable data type when i

say immutable basically it means uh that

you cannot add any more data into that

particular topic so if i have to create

a tuple called one two three four

instead of adding it to the sample tuple

here i'll create another tuple and add

that particular value and discard the

one that i have at hand right so the

working is very similar uh to that of

lists and again lists use square back

brackets for all the people who want a

shortcut to remember lists sets and

dictionaries right when you guys are

beginning a list uses a square bracket a

dictionary uses a flower bracket and a

tuple uses a round bracket right so i

hope you're clear with these three data

structures now let's take a look at the

fourth one which again uses flower

brackets and this one is called as a set

set uh the name itself should definitely

take you back to your school days where

you might have learned about these

concepts of

sets and how you should have an ordered

collection of unique elements present

right so if i have a set uh you know one

two two three three four four five five

six six the entire output of it will

actually be one two three four five six

right that's how a set works in a set

you cannot have repeated elements every

single element that is present in a set

should be 100 unique to each other right

in fact look at the example on your

screen right now first set is the name

of our set of course and again similar

to dictionaries here we use flower

braces as well but the difference here

is that we do not have key value pairs

if you had the same flower bracket

structure where you had a key value pair

immediately that would become a

dictionary but since we don't have that

and we have individual elements you can

take a look at it and you can think of

it as a set right in fact the example

that i just spoke to you about is on the

screen one two three four four and five

so four is repeated right uh but in the

output you can see that four is present

only once so no matter how many repeated

elements or you have in your set once

you try to perform operations on it or

once you try to actually store it in the

form of a set and try to access the

output of it you will only have access

to the unique elements that are present

in that particular set right fantastic

now this was about the built-in data

structures we checked out list we

checked out the dictionaries we checked

out tuples and we also checked out sets

right remember the brackets remember

what's immutable and understand that for

all of these data types you do not have

to install any sort of dependency to

work with right

now let's take a look at user defined

data structures

when the name itself suggests user

defined data structures what are we

trying to do here right

for example let's talk about these uh

the data structure that you see on your

screen right now stack right think about

a stack of books again a stack of books

is shown on your screen right there how

would you uh arrange arrange a couple of

books let's just say you have 10 books

how would you arrange it in the form of

a stack if you just have to put it on

one top of the other right i'll be there

so how would you arrange books in a

stack right you would obviously take it

and put it one on top of the other now

this actually has a principle of

approach and how you are actually

accessing and removing uh elements or in

this case books right if you've kept all

those books on the ground or maybe on

your bed or maybe on your table there's

only one way that you can have complete

access to the book that is the top book

right you can you have one two books and

you can access the top one and you can

start picking up the book from the top

to the bottom right this concept is

called as last in first out or in short

you might have already heard about it

it's called as le4 right

so if i have a stack of books or if i

have a stack of elements in python what

can i do with it well you can actually

add any sort of data you require to the

stack remove any sort of data you can

access it change it modify it work with

when you are adding an element into a

stack the operation is called as pushing

and when you're removing a data element

from a stack or in fact even a queue as

well it's called as popping the

operation that goes into it right but

one thing ladies and gentlemen you have

to think about a stack is that once

you've stacked it on the ground on your

bed uh you know beat on the table or

wherever it is you cannot start pulling

out books from the last right you have

to hold everything else and manually

yank it out forcefully so this concept

does not apply here in python so the

data access if you if you want to remove

the third book on your screen if you

have to remove this book on your screen

you basically have to remove the first

one remove the second one remove the

third book and then put these back into

its place right so it's not like you'll

just divide it into two things pull that

book out and put it back again like how

you would probably see in a cartoon or

so that's not how it works if you want a

concept that works in that way the next

uh user-defined data structure will be

pleasing to you guys because this is a

queue a cue data structure is something

that uh literally every one of you guys

watching this particular video in fact

all of us when i say including me have

seen and either been a part of a queue

or of course you know we know how it

works right so cues are again used in

real life a lot the principle here is

slightly different from the stack here

we use this concept called as fifo first

in first out right that's how an actual

queue works whoever comes first gets

priority they get served and then they

go out and the next person walks in

right uh you can see the ah you can see

the effect on the image that's shown on

your screen right now now whenever

you're taking a look at cues though uh

maybe let's just say the fourth person

in this queue forgot her car keys or

forgot her mobile for another anything

can she just walk out of the queue from

the back as well is it possible well of

course it is possible right uh the

advantage of queue compared to stack is

that here

operations can be performed both from

the front and the back when i say front

and the back what i'm trying to mean is

the head and the tail right for example

the head of the queue is the first

person who was uh who was there to be

attended to right the tail of the queue

will involve what it will involve the

last person in that queue so basically

including all of these things operations

can be performed either from the top or

you can actually take the tail section

and you can start either removing data

or adding data from there as well so

this is how a general queue works and

when you're thinking about

implementation in python as well

remember one thing people first and

first out so depending on your object

axis depending on what's actually

required you will be either thinking of

using stacks or queues in most of these

situations right now that we're clear

with stacks and queues uh i'm gonna take

a look at another interesting data

structure here another user defined data

structure here it's called as trees

right now

when we've been talking about these user

defined data structures what we're

trying to do is we're trying to use the

syntax and the logic of python to build

ourselves our own data structure that is

the reason why all of these data

structures are called user-defined data

structures i am sure you guys figured

that out by now right fantastic right so

when we're talking about a tree data

structure again think of an actual tree

right in an actual tree you find root

you find the leaves and of course you

find uh you know all the branches and

all of that now try to see if you can

take a look at the image on your left

and find any of those right let me help

you out this one uh the node this is a

top node uh basically from this

particular node we have all the other

nodes that are coming out right so this

can be considered as a root this can be

considered as the primary and from that

whenever you see every other node into

it there is a concept of uh

you know the parent relationships that

we build here for example uh 2 and 3 the

nodes 2 and 3 have their parent as 1

because from 1 you got 2 and 3 right

similarly for two now four and five

become the children of two similarly for

five

similarly for five a six seven and eight

become the children of five getting it

right now one important thing that you

really have to understand is that when

you're working from the root node all

the way to the leaf nodes now what i

mean by leaf nodes is basically all

these nodes which do not have another

connector node let's take a look at what

they are

are we having any other nodes connected

to 3 no so that's a leaf node similarly

for four similarly for six similarly for

seven and eight right so most of the

results of these computation that we

perform when using a tree data structure

usually lies in these leaf nodes aspect

of it right they are the last nodes but

hey in our case they are some really

important nodes that we are going to

have to use right so breaking up a

problem into a solution where you

require a data structure which needs to

be broken down in a compounded form

right so if you have if you have a very

complex data set and you're gonna break

it into modular chunks uh and use it as

a solution eventually one of those

modules will give you a solution the

tree data structure is exactly what you

guys should use right fantastic the next

data structure that we're going to take

a look at is the graph data structure

now again we've been using graphs and

i'm sure you guys have seen graphs you

have worked on graphs beat school be it

college or you guys might have seen the

rise in the coronavirus spread that's a

graph as well right so

we're talking about graph as a data

visualization entity there but in terms

of python what are we doing well here

graph is a data structure which

basically has a structure which is very

similar to a tree but then the working

of a graph is very different because

this sometimes is a closed loop

structure which has a collection of

nodes and edges now you already know

what are the nodes right so what are the

nodes that you see on your screen right

now 0 1 2 3 and 4. what are the edges

that you see on your screen right now

well in between 0 and 1 there is a an

edge between 0 and 4 there is an edge

between 4 and 1 there is an edge right

now even though i directly do not have

an edge from 4 to 2

we go through 3 and we still have an

edge there right

this is the concept of nodes uh you know

nodes are also called as vertices in

case that's what you might have learned

in your school of college or in fact

edges are also called as arcs right so

regarding vertices arcs nodes edges you

have to understand and you have to make

sure that you do not get confused in

these concepts so as i told you a graph

is a closed connection of all of these

uh nodes and edges so can i have an a

can have n number of nodes here if i'm

talking about a graph data structure in

python it has to consist of a finite set

of nodes and edges only then it is

called as a graph data structure right

now think about a fantastic example of

where this exact data structure is used

in fact it's facebook facebook is a

fantastic social media that all of us if

not most of us know and use how do you

think each of the individual people

present in the facebook's network get

connected to others right when there is

a connection from one person to another

think of it as an edge but then these

two people sitting in correlation with

what we're discussing right now are the

nodes right so you have nodes you have

edges and now think about all the

billions of people that are on facebook

right it just becomes an entirely uh

different uh network it comes it becomes

a very super uh complex intertwined web

but then i had to really simplify it for

you to talk to you about graph in uh in

terms of facebook right but yes this is

used in facebook and if you break it

down to its most simplest levels you

definitely will see this data structure

used there and in thousands of other

places i'm sure right guys now i have

one more bonus data structure that i

want to talk to you about this is again

the favorite of a lot of interviewers

out there so if you're a non-technical

person who's had a chance to attend a

technical interview there is a very good

chance you'll be quizzed on first of all

everything that we have learned until

now secondly there's a good chance

there's a question that's going to come

up if you're looking for a python if

you're looking for a carrier in python c

c plus plus c sharp or java 99 of the

time they're gonna ask you a question

saying what are linked lists

all right so to answer that question

link list is another user defined data

structure that we have uh here in python

of course we do not have native support

for a link list in python as in we just

saw how we can work with list how we can

work with sets and all of those right we

have a valid syntax to use that but to

implement linked list in terms of python

you actually do not have it in the

standard library so you have to use

functions you have to use other lists

and you have to use manual logic to

actually implement a linked list first

of all what is a linked list well a

linked list is basically a collection of

elements tied up in a chain structure

right it's basically linked again look

the answer lies in the name of the data

structure itself a linked list is

basically a sequence of elements that

are connected to each other in a way

where you can move around and access one

or the other element as and when

required now if i have three elements

that you can see on your screen right 5

10 and 20 how how do i even know that

the location that holds the value 5 is

able to talk to the value 10 right this

is where a simple concept of pointers

are used i am sure you guys know what

pointers are right pointers are nothing

but the simple addressing system that we

use uh the address that we attach to a

variable so that even though we do not

know the value or where the value lies

as soon as we have the address in our

hand the second part of what i just said

will negate itself we will have an

address we know where that particular

element 5 10 or 20 exists right so uh if

you just take this uh particular entity

here five and there will be another

criteria here called as next so next is

basically the name of the pointer you

would point that to where the data

element of 10 exists that is how the

linked list works again there's multiple

types of linked list there's a single

linked list there's doubly linked list

you know there's a circular linked list

so there's many many types and it can

get really complex but one thing that

we've seen a lot is that uh in terms of

python linked lists are not super

popular because you again have a lot of

other data structures uh that you can

try to use and you can try to have you

can build the same application uh using

something else uh where uh you know a

link list might have been a good fit

right so implementation has to be done

manually but then even though it has to

be done manually even though it's not in

a standard library this is a super

important data structure that again uh

is used asked and worked with by all uh

the professionals out there so make sure

you guys know your linked lists right

now let's go ahead and work with some

non-primitive data structures in python

so the main non-primitive data

structures in python are tuple list

dictionary and set so when it comes to

all of these data structures so you can

store multiple elements inside one data

structure so till now we work with only

variables and when it came to variables

we could store only one value in one

variable now let's say if you go to a

music concert and you'd have to store

the names of all the people attending

the music concert and the strength of

the audience would be around 10 000. so

to store the names you would require 10

000 variables now that's a lot of

variables and you'd have to manually

store all of these names inside 10 000

variables so that's a humongous task and

that's a tiresome task so this is where

you would need these data structures

where you can store multiple elements

inside one single data structure so

we'll start with the first data

structure which is basically tuple so

when it comes to tuple it is an ordered

collection of elements enclosed within

round braces so we have curious jason

over here and he'll be coming in between

to give us some pointers so curious

jason tells us that tuples are immutable

now what does he mean when he states

that tuples are immutable so basically

when you go ahead and create a tuple so

let's say you add five elements inside

one tuple now you can't change or modify

the tuple which you have created so that

would basically mean that let's say if

you have five elements then you can't

change the value of the second element

or the third element or you can't add

another element inside the tuple which

you have already created so this is

basically the immutability nature of

tuples and this is how you can create a

tuple so you will use these round braces

over here and inside these you will

given the values right so as you see

tuple is actually your heterogeneous

data structure so over here you are

storing a numerical value a character

value and a boolean value right so let's

go to jupyter notebook and work with

tuples

so let me create a tuple

so i'll name the tuple as up1

and i'll given the values

right so this is our tuple top1

now let's see how can we access

individual elements from this tuple so

accessing elements from tuple is the

same as axing elements from a string so

all you do is given the name of the

tuple which is top1 you're given this

square braces and then if you want to

extract the first element which is

basically present at index 0

you will type in 0 over here

and you have extracted the first element

which is 1. similarly if you want to

extract the last element you have to

type in -1

and you have extracted the last element

which is 23 and if you want to extract a

sequence of elements so let's say i want

a true and b so this would be from index

number one going on till index number

four because we'd want one two and three

so

i'll type in

1 colon 4 right so i've extracted a true

and b

right so this is how you can extract

individual elements from a tuple now as

i've told you a tuple is immutable so

let me go ahead and try to change the

value which is present inside a tuple so

i'll type in tup1 and let me change the

value which is presented zero with index

and i'll change it to let's say 100

and we get an error over here so the

error is tuple object does not support

item assignment and that is because

tuples are immutable

now let me try to add a new value inside

this so we've got one two three four

five so that would mean this is index

number four so let me try to add

something at index number five

i'll type in

harry potter

again we get the same error so tuple

object does not support item assignment

because of this immutable

now we'll head on to the next data

structure which is a list so lists and

tuples are quite similar the only

difference is less immutable while

tuples are immutable now what do i mean

when i say lists are mutable so this

means that lists can be changed once

they are created so there are five

elements in a list so the second element

or the third element can be modified and

again since i've said that there are

five elements so another five elements

can be added inside this list so this is

the basic difference between lists and

tuples and this is how you can create a

list so you'll basically given square

braces and you'll given all of the

values inside the square braces so let's

head on to jupiter notebook and work

with lists

so i'll type in l1 and i'll given some

values over here

and then i'll print it out

all right so this is our list over here

and accessing elements from the list is

same as tuple

so if i want to access the first element

i'll type in l1 i'll given square braces

and then i'll given zero so i have

extracted the first element now let's go

ahead and access our sequence of

elements so i want to access these three

elements over here true two and nb so

this is index number two and then going

on till index number five

so l one and two colon five

all right so true two and b so we have

successfully extracted these three

sequence of elements now let me go ahead

and actually change the values inside

this list so i'll change this value 1 to

100 so i'll type in l1 0 and i'll assign

the value of 100 now let me print out l1

so as you see initially the value of

this element was one and then we have

changed the value to 100. now let's say

i want to add a couple more elements

inside this list so i'll type in

l1.append and

i'll add an element and name it to be

let's say sword

and then let me print out l1

right so i've successfully added a new

element

so now i can actually add a list inside

a list so let me again use the append

function over here

and then i'll add a list inside this so

i'll type in

one two three four and five

so let me

again look at l1

right so i successfully added this new

list inside this list

now we can also go ahead and remove

these elements so to remove the last

element we've got the pop function so

i'll type in l1.pop

so as we see this last element has been

popped out now again let me type in

l1.pop and let's see what will be popped

out right so this time this element

sword has been popped out

now let me have a look at the modified

list right so we are only left with

these values because word and this list

has been popped out so this is how we

can work with lists

now let's head on to the next data

structure which is a dictionary so

dictionary is actually quite different

than a list and a tuple because it

consists of key value pairs and these

are actually unordered collection of key

value pairs which are enclosed within

curly braces and again dictionaries are

mutable so this is how you can create a

dictionary so you will put in curly

braces over here so first you'll put in

the key so over here the key is apple

and then you'll give it a colon and then

you'll given the value so for the key

apple the value is 10 and then you're

given the next key value pair so after

come up the next key value pair is

orange 20. so orange is the key and 20

is the value so let's go ahead and

create our own dictionary

so let me create the dictionary over

here i'll type in d1 and then i'll give

them these curly braces over here

so i'll just stop given some names of

fruits

so let's say the first key is mango and

the price of the fruit would be the

value so mango costs 45 bucks

and then we've got apple

so let's say apples cost us 30

and then we've got

orange and then orange costs around 77.

after that we've got guava

and then this would cost around 125

now let me print it out

so this is our dictionary

now what we have is key value pairs so

if i want to access only the keys then

we have the keys function so i'll type

in d1 dot keys so i'll given the name of

the dictionary and then i'll follow it

up with the keys function

diva.keys right so i have extracted all

of the keys which are mango apple orange

and guava similarly if i want to extract

all of the values which are basically

the price of all of these fruits i'll

type in d1 dot values

and i have extracted the prices of all

of these fruits

now let's go ahead and modify some of

these elements so i want to change the

cost of mango

so i'll type in d1 and then i'll given

the name of key

so the name of the key is mango and the

cost would be 100

and then i'll type in d1

so initially the cost of mango was 45

and then i've altered it to be 100 so

this is how we can work with

dictionaries

and then we've got the final data

structure which is a set so a set is an

unordered and unindexed collection of

elements enclosed within curly braces so

what do i mean by unindexed so when i

say unindexed this basically means that

sets don't have any index to it so we

can't really access the elements with

respect to their indexing and also

another thing to be noted is sets do not

allow duplicate values so let's say if

you add a value 10 then you cannot add

the same value again so it will take the

value only once and this is how you can

create a set so you'll have curly braces

over here and then you'll given all of

the elements inside it so let me create

my final data structure over here

so i'll type in

one

a and then i'll given a floating point

value let's say 3.78

let me print out the set

so this is our set over here now what

i'll do is i'll copy this and let me try

to add some duplicate values

so i'll add

one

all of these times and then i'll also

add a

now let me print out s1 and then see

what value do i get

so we see that duplicates are not

allowed one even though i have given

around five or six times it has been

taken only once and a half given two

times but then again it comes only once

so obviously set does not allow any

duplicates inside it now let me go ahead

and add some new values inside the set

so i'll type in s1 dot add

hello world

right so i've added this new element

and if i want to add more than one

element at a single time then we've got

this update method so i'll type in

s1.update

and i'll give it a list of values so

i'll type in

let's see

sparta and then i'll type in 123.

then i'll given let's say 3 plus

9j

then let me print out s1

all right so all of these elements have

been added again you see that the order

of these elements is not preserved it is

random right so 3 plus 9 j comes over

here and then we've got 1 123 right so

the random is not at all preserved all

right so we are done with the basic data

structures in python which were

basically tuple list dictionary and set

now let's talk about our first linear

data structure that is a

so what is an array it is a linear data

structure that means elements will be

stored in a linear fashion

right linear fashion now if you talk

about any let's take an example now

let's consider that this is how you

represent an array in the form of a row

right and let's suppose it contains

elements one two three and four right

now with every memory location there

will be some address right so let's

suppose these are the four elements

right one two three and four

and these are some addresses let's

suppose this is 100 and this is 104 this

is 108 and this is one one two now if

you talk about memory obviously these

addresses will be hexadecimal and when

you talk about this this particular

array it will be somewhere in the memory

with four uh or you can say four bytes

of memory for each

integer now if i take a if i consider

this integer and let's suppose integer

takes four bytes now these four bytes

are available for each integer now this

is an integer right now it takes four

bytes now the second address will start

from 104 right because now again this

will take four bytes then one way again

it will take four bytes then one

one one two right so in memory it will

be somewhere around but the thing that

obviously you might be thinking okay sir

let's suppose this is our memory

and now if we have four and four bytes

that means eight bytes here and eight

bytes here but they are available in

chunks right this is one chunk and this

is second chunk and rest of the memory

is occupied can we store this array in

your memory in the memory no because it

needs contiguous memory allocation that

means when this is the scenario where in

you have memory or locations or memory

locations available in a one big chunk

right that means if you talk about this

array it requires four into four that is

16 bytes are available but and they are

available in a in a continuous memory

fashion right or if they are available

in

in such a way that it is a one single

chunk of 16 bytes okay so then only you

can store the elements at that location

now obviously for simplicity i'm taking

this addresses as a num integer number

but in reality those are hexadecimal

numbers okay so it is easier for me okay

so now one more thing is that

the elements are stored in a linear

fashion right but

can we access elements randomly yes with

the help of indexes so if you talk about

this array right

one two three and four obviously this

there will be a name associated with

this array right now we have index 0 1 2

3.

now why indexing starts with 0 or why

there is a 0 and indexing always starts

with 0. now the question is that right

now let's try to demystify this fact

that why

indexing starts from 0 why not it starts

from 1. now if you remember

right i told you that there will be a

name associated with this array that is

arr now this arr is nothing but name of

the array and name of the array

represents

right it represents

its base address

right now the base address of this was

earlier we spoke about it so it is 100

this is 104 this is 108 and this is 1 1

2 right so now this is 100 now

let's talk about how you access

we will talk about in the coming slides

we will see how to declare and

initialize our array but let's suppose

if we talk about how to access this we

use array and then the subscript and

then the index okay the index is one now

i told you name of this array represents

the base address so base address is 100

now plus 1 now this one represents 4

bytes okay so the 4 bytes

then what internally happens it will be

it boils down to 100 plus 4 that means

104. now 104 is not the first location

it is the second location okay now

similarly if you talk about accessing

the second element or third element in

the array it boils down to what area of

2 which is nothing but 100 plus 2 now

this 2 is nothing but 8 right 100 108 so

you will be

accessing the third element in the array

now how can you access the first element

so

here are 0 now it boils down around 100

plus 0 because there are no bytes right

so it boils down to this that array

indexing starts from 0 and now you know

why and this is how you can access

elements randomly so with the help of

these indexes okay so now you might be

thinking okay now we have an array

can we store different elements right

can we store let's suppose that it can

be stored in this will sort integer then

we will store a floating point number

then we will can we store a character no

if you talk about any particular area

let's talk about this array now the data

type or the type of data that you can

store in this area will be homogeneous

that means you can only store similar

elements okay

so these are some facts and this is how

array works and what are the addresses

what are the indexes can you store

different elements no you can only store

similar elements in the

now let's talk about the applications of

array now you might be thinking sir why

do we need this array what is the uh

what is the reason that we are using

this array so basically when you talk

about arrays now obviously when you have

a scenario wherein you want to store

your elements in a linear fashion right

and that too you want to store them in a

contiguous memory locations right so

that you can use your cpu or you can use

your memory efficiently right

not the cpu you can use your memory and

you can utilize your memory to the

maximum right so you want to utilize

your memory efficiently at that time you

can use this but obviously it will have

some drawbacks right it will have some

drawbacks that is why we have different

different data structures right so if

you want to store your data in a linear

fashion you can use arrays okay now it

is also suitable for

for the scenarios wherein

you require frequent searching right if

you want to search an element in an area

you can directly go and access these

indexes one by one right so in a linear

fashion you will access okay is this the

element that you're looking for no it's

20th element that you're looking for no

is 30 the element that you're looking

for no as 40 the element that you're

looking for yes one by one you can

access all those elements and

try to search for the element that you

are looking for okay so it is suitable

for applications which require frequent

searching now let's talk about one

dimension

so if you talk about 1d array it is it

can be related to a rule like we saw in

the example right so that is what is a

one dimensional array it is represented

in the form of row and we have addresses

like 104 100 104 108 112 and 116 and

indexing will be obviously 0 1 2 3 4 and

then there will be a name associated

with this array which is arr and then

you can store the elements in this array

let's suppose here the it is an integer

array okay so you can store only integer

elements

and

the size of this array is five and you

have stored the elements one two three

four five so now it can be related to a

row where in elements are stored one

after the other like you see until you

have one then you have two then you have

three and there's those or all of these

numbers are in a contiguous memory are

available in a contiguous memory

location okay now when you talk about 1d

array only one index used right when you

try to declare and initialize your area

at that time you will use one subscript

okay so how you can use that let's

suppose if i if i talk about this

special array that i that i have defined

here here right you will define it a r

and then the sub or the index is and the

number of elements that are present here

which is five so only one subscript will

be there or one index will be used okay

so this is how you uh declare your array

so now let's talk about the declaration

and initialization of this area so

obviously when you talk about the array

there will be a name associated with the

array and then the data type are you

going to store integer values in that

area then the one uh that one subscript

or one index that we use and then

definitely the size of the edit so this

is how you declare your 1d array now how

can you initialize it there are

different ways you can initialize it

obviously here you are declaring it then

you might use a for loop to initialize

all the elements or you can declare or

initialize your array at once so how do

you do that so you will write

and let's suppose this is the integer

array

and you don't have to specify the size

you can directly write the elements

right and those elements let's suppose

those are one two three four and five in

this case when you're declaring and

initializing your array at once at that

time this size becomes optional you

don't have to specify explicitly the

size of the array but obviously the size

of this area will be five okay now since

you are declaring and initializing it at

once so this is optional but in the case

where wherein you are not initializing

it at that time the size becomes

very important and you have to mention

this size explicitly okay

now let's talk about two dimensional

so also it is known as 2d array so it

can be related to a table like this or

you can also say a matrix wherein you

have rows and columns right now in this

elements are stored one after the other

in such a way that you can think of it

as a 1d array now this is what when the

array right as we have already seen it

right and inside this one nd array you

have another 1d array right

now this is known as 2d array so now how

it works right

let's suppose you have numbers over here

and you have four numbers one two three

four then you have

five

six seven eight and you have nine

ten and eleven and twelve so this is the

2d area of having oh and this will be

similar to what of having

three rows

right you have you will have three rows

not four rows you will have three rows

and in that in those three rows right

you will have

what

four columns

one two and

so numbers will be like this one two

three four five six seven eight nine ten

eleven and twelve okay done so now

obviously this will have let's suppose

this is a zero based indexing and this

will have zero index here one index here

and one now internally what is happening

it will be a zero zero and it will be a

zero one and zero two zero three then 1

0 1 1 1 2 1 3 then 2 0 2 1 2 2 and 2 3

indexing right so similar to that we

will have this index would be 0 0 this

would be like this and this will be like

this so

if you want to access the element that

is present at this location what you

will do you will run two for loops right

one uh will be starting with from here

let's suppose one will start from i

equal to zero to the length of this

outer array that is

3 less than 3 right so

and the another

from 0 to the number of

rows that are there okay

so this one will be the outer loop

this one will be the outer loop and this

one will be the inner loop that means

the number of columns that are there so

this is for row and this will be for

column that will start from 0 to

less than four okay

so

this is how you iterate and it will be

similar to this and now what about the

addressing right what about the

addresses that will be there so this

will be let's suppose if this is 100

this will be 104 this will be 108 this

will be 1 1 2 this will be 1 1 6 because

internally it is treated as if they are

again in a contiguous memory location

but this time around you have a 1d array

and inside that 1d array you have

another one dna so for declaring it

you will use two subscripts right so it

will be something the name of the array

then two subscripts and now this will

represent the number of rows and this

will represent the number of columns so

in this case the number of rows will be

three and in this uh and the number of

columns is four right so this is how you

declare your

what a two d array so dimension depends

upon the number of subscripts you are

using so this time around we are using

two subscripts now let's suppose you are

using three subscripts right

so similar to like this three

three and three okay so this time around

this is the 3d array and similarly you

can have multi-dimensional array right

and you just need to keep on adding the

subscripts that's it okay

now we should learn regarding array

implementation right we are solving

three different problem statements here

the first one is we are creating one

dimensional array it is very simple and

people can understand it in very easy

way the second one we are concentrating

on creating two dimensional array that

means usually we use it for matrix which

includes rows and columns also we call

it as m and n or m cross n all these

three are the names which you can give

it for two dimensional array and also

two dimensional array is used for

different purposes at the last we are

trying to sort search and insert delete

the elements inside an array only which

is having integers so these are the

problem statements we are solving for

arrays in python so let's quickly hop

into the id and check out the first

problem statement that is how to create

one dimensional array and insert

elements inside that also put up the

output whatever the input is given by

the user on the screen so let's hop into

the ide now

here i'm using google collab in order to

put up the first program right so

we'll rename this i'm

naming this as

one

dimensional array

so

now we will come to this ide and we'll

type one dimensional array example where

you are including array size and you are

asking the user what are the different

inputs and then we are presenting the

same inputs received by the user on the

output screen so to quickly save the

time i'm just putting up the

code now

so this is the python code where we'll

be using for one dimensional array i'll

explain what is happening here the first

thing is we are asking how many elements

to store inside the array for example it

might be 5 6 10 so whatever the integer

number is the whole number we can give

it right so again we are asking

assigning a variable for input so

whatever the input is given by the user

will be assigned to the variable called

num right then we are assigning an empty

array why because whatever the size has

been defined by the user is put up here

so if it is five it can take only five

elements if it is six it can take only

six elements that's how it goes and

immediately we'll ask to enter the

elements inside the array then we'll be

pushing through a for loop and we'll be

using one

important piece of code here that is arr

dot append append in the sense will be

assigning the elements one after the

other at the back of the array we are

not putting up the elements which is

inserted by the user in middle or in the

front or somewhere right so append will

always ensure the elements which is

given by the user is put up at the back

of the array one after the other right

so next will display whatever the array

elements are so the array elements are

again you have to push through for loop

because it has to uh just print the

elements one after the other so let's

quickly run this program and check out

how does this output look

right so it is asking how many elements

do you want to insert into array so i'm

just putting up three as of now so enter

then it will ask you for the first

number i'm putting up four

and then

the second number that is 5

then let us i'm giving 7 okay

so it will display 4 5 7. also you can

modify this outputs by giving commas by

giving

spaces between those if not it can

generally display this before five and

seven so this is about one dimensional

array in python let's see the second

problem statement in arrays for python

right so we are going to create two

dimensional integer array where you can

insert row number and column number and

it will fill up the

elements inside the array accordingly so

let's quickly switch on to the ide

that's google collab and check out how

does 2d array work in python so here i

have named this particular file as

2d array and you can name it whatever

you want and i'm

putting up the code here so explaining

the code for you that we have

asked for row numbers so how much the

row should be in your matrix i'll take

it as matrix only because usually rows

and columns will be using in matrix so

number of rows should be given by the

user and we'll store that number in our

underscore num that is row number again

we'll ask the user uh input number of

columns right so whatever the number is

given integer value whole numbers is

stored in c num that means column number

you can accordingly put up the variables

as per the problem statements so here to

keep it relatable i have used arnhem and

cena

next we are going to

assign whatever the values we have right

that is given by the user that is it

might be a row number or it might be a

column number we'll assign that with the

elements so

to assign will be using for loop because

one after the other it has to be printed

right at last we will be printing the

final

array and final matrix two dimensional

array in

2d array i've just put up a abbreviation

here so it's understandable for you guys

so

t w o two d is dimension underscore

array arr i'm not put up completely

array it's just ar

so this is how we initialize and the

variables declaration and this is how we

execute the program let's quickly see

the output of this so i'm running it is

asking for the first time that is

input number of rows so the number of

rows i'm giving here is uh 2 and again

i'll enter it will ask for number of

columns so then it is three here i'm

entering that and it is giving you two

rows and three columns also if you want

you can arrange it as per matrix so one

after the other but here i'm showing it

for you guys just with see you can count

three columns you have and two rows

right the bracket defines the rows here

right the first bracket set of brackets

is for first row and second set of

brackets is second rows so this is how

2d array works in python so we are going

for the third problem statement which we

are solving for array in python so it

says implement search sort and delete

operations on array of integers right so

i'm breaking these three

operations that is search sort and

delete into three different programs to

make it simpler rather than combining

everything and making it to one huge

program so first i'm concentrating on

deleting elements inside an array of

integers in python so quickly we shall

hop into the ide and see the program

here google collab is ready and the page

is empty

i'm just pasting this particular code in

order to

use time efficiently so explaining this

code the first line it says enter the

size of an array right we are first

accessing an array size for example it

might be 10 5 8 as per the user command

and then we are inserting so many

elements in into that particular array

say for example it is 5 right so we are

inserting 5 different elements which we

have already seen by now so next it is

asking which element to delete right so

we are telling an element an integer to

delete then it will display the new

array for you so for loops are there in

order to

keep the array in sequence and it might

be printing or it might be taking input

from the user both we are using for loop

only and append is for putting up the

elements into the back of an array right

we are not inserting element in middle

or somewhere in the front abruptly the

incision should not happen so one after

the other sequentially in order to

append in order to insert the elements

we use ar dot append so let's quickly

see

what is the output of it so if you have

entered any element which is not there

in this particular array right so it

will give you element does not exist in

an array so this is how the program will

work so let's quickly see the output now

so it is asking for array size i am

giving three

i'll enter

then entering all the three numbers what

i want to give

okay it will ask you which value to be

deleted right i am giving value five

so the new array is without five that is

four and six so this is how it will work

and immediately i'll

show you if you give any element which

is out of the array bound how it will

give you an error so i am taking three

elements again

5

7

and 8

right so

it will ask you which value to be

deleted i'll say

1 1 is not there in the array it is just

5 7 and 8 right

so if you put that it will say element

does not exist in an array right so this

is how deletion will work in python

arrays

after knowing how to delete element in

an array so we have to see next how do

you sort elements inside an array in

python so let's quickly hop into the ide

and check out how you sort elements

inside an array right so here we start

coding

just putting up the code here so array

is already defined the elements are 10

22 38 27 11 so on right so we have

five elements here to be sorted in

ascending order and you can also make it

descending as well i'm showing you for

ascending order so what is happening

here i've just put up a comment for

better understanding displaying elements

of original array original array in the

sense whatever it is here is displayed

first right so next it is sorting by

using for loop right so every element it

will chuck and it will try to compare

with the next element if it is greater

it will push up

that particular element to the back and

whatever it is lesser will come in front

so this kind of exchange will happen and

it will sort in ascending order so

ascending in the sense from smaller to

higher number so quickly it will display

after sorting the elements of array

sorted in ascending order are so and so

so let's quickly see what is the output

of this particular code

right so

we have original array which we have

given that is 10 22 38 27 11 and then we

have

the sorted array so in ascending order

it is 10 11 22 27 38 so this is how it

will sort the major function where it

will be sorting is we are using this

particular lines of code which i am just

highlighting in this particular ide

where it will compare each and every

element inside the array

to the next one if it is greater it will

push it to back if it is

lesser than the compar array i mean

array element it will push it to front

so this operation will happen in this

particular lines of code right you can

also sort by using sort function

directly as well so this is a simple

example to know how sorting will happen

in python now we shall see how do you

search an element inside an array so

here i've tried to put up occurrence as

well so let's quickly search and see

elements in an array in python id okay

so this is the code in order to search

the element also find the occurrence of

it right so here this is the array set

so i'm giving number one two three one

two five so you can see

one

2 has been repeated those two integers

are repeated so first it is showing up

the created array whatever the array

which has been given is put up in the

first place and next what it is doing it

is trying to find the occurrences of it

so with the help of index right so the

element two the number two so where it

is present and how many times right so

first where it is present it will show

that the second time will not be counted

first occurrence will be counted so

let's quickly see the output of this

particular code right so here

uh the new created array is so whatever

the given array by the user has been put

up in the first line and the second line

it it is saying the first occurrence of

two at position one why this is zero one

two three four five right so

two at the first time is present in the

index value array 1 right again next it

is searching for 1 where it is the first

occurrence of 1 in array is at index

point 0 right so it is showing the

output 0. again you have 1 here that is

0 1 2 3 also you have

second to in fourth position but still

wherever it is available at the first is

being

demonstrated in this particular program

right so this is how the occurrence is

counted also the elements are searched

in python now let's talk about

advantages of arrays so obviously when

you have indexes associated with the

array right we have indexes so this it

is easy for us to access any element

right with the help of this index we

formed x is the third element you can

directly go ahead and say ar of 2 in the

1d array right so we can directly access

elements with the help of indexing

similarly it is easy for us to iterate

through it right with the help of one

for loop we can iterate through all the

elements right one by one that is there

okay that up there in the area and

similarly if you want to do the sorting

we can go ahead and easily hydrate

through one uh these elements one by one

and look for an element if we are trying

to search an element in the area let's

suppose uh

we are searching for three so one by one

we will search okay is this element

three is this element three is this

element three is this element three is

this element three right and if this

element is three we we can easily search

and also for sorting i let's suppose we

want to sort this array what would it be

it will be simply what if you have four

here three here two here one here and

let's suppose you have zero here okay so

now you want to sort this in the

ascending order so what you will do you

will use two loops one will

uh one will focus on this first element

and then the second uh the second one

will compare all the elements okay and

then at the end of this thing you will

have the largest element at the end of

the array so sorting hydration searching

it is easy and airy we just have to i

trade through all the elements one by

one

now it is a replacement of multiple

variables now what do you mean by this

thing let's suppose you have an integer

or let's suppose you want to store uh

the roll number of 10 students right so

what you have you would have done

earlier prior to what when you don't

know the arrays what you would have done

you would have said roll number one and

then it's or you can say

s1

s2

s3 s4 and one by one you can store the

roll numbers in these

integer variables right so as soon as

our students increase now let's suppose

we are talking about here 10 students

now as we talk about 100 now what

happens if we talk about 500 are you

going to uh

write 500 variables integer variables s1

starting from s1 to s500 no it is a very

inefficient way of doing so right so

instead what you can do you can create

an array and you can create an integer

array and name it student

and and then you will have the size

which which obviously represents the

number of students that are there and in

this case it will be 500 now if you want

to change it to tomorrow if you want to

change it to 600 you can go ahead and

easily change it to 600 right so

it is the replacement of multiple

variables so this is what it means

now let's clear the screen and now let's

talk about disadvantages there's one

disadvantage that can be easily noticed

is the size now obviously when you're

talking about 1d array right the size or

any area right the size is there right

so you you cannot exceed the size the

elements cannot exceed this so let's

suppose you have a the size is five you

can only store five elements right you

cannot go more than that or beyond that

now if you have a size 100 and now

you're trying to store only two elements

anyway the 100 memory allocations will

be there for this array that means you

are wasting your memory you are not

utilizing it efficiently okay so this is

what it means that size is fixed and you

cannot store more elements and if the

capacity is more than occupancy most of

the array gets wasted okay so

these are two things apart from this you

need a continuous memory allocation that

means if chunks of memory are available

here and there you cannot store an area

which is let's suppose here you have 16

bytes and here you have 16 bytes

only if you have an array which is of 16

bytes that means if you have an array of

size 4 that it can be stored here but if

you have an area of it suppose size 8

you cannot store four elements here and

four elements here that will not be

happening okay that cannot happen rather

okay because it needs continuous can be

a location so there is one more

disadvantage and the last but not the

least is that insertion and deletion is

difficult now why do you say that let's

suppose you have an array and you have

having in this array one two three four

now let's suppose you want to insert a

value zero at this location now what you

need to do you insert the zero and rest

of the elements every element will be

swapped so swapping is required right

swapping is required plus there should

be memory available so that you can

store that element else if there are

only four elements and now you want to

store zero and the size is also four and

that time around what happens you will

store one and rest of the elements will

be swapped and you will be losing this

value so it is very difficult to

insert the value now same thing will

happen when you are trying to delete but

at that time you will not be losing data

but yes swapping is required right so

let's suppose you are you want to delete

this location so what you will do or

delete this number what you will do you

will overwrite this with three you will

overwrite this with four and let's

suppose if there is six you will write

this with six so at the end you will

have one three four six right one three

four six and one memory location is

there and it will contain the same

element that is six so next time around

you will just override this so again the

swapping is required so it is very

difficult to insert and delete an

element in the area

so now moving to the agenda we will

start this course by knowing what is

stack what are the examples of stack

then we will see some functions

associated with the stack such as push

pop

top and many more and at last stack

implementation can be done through list

through collections

and through queue we will discuss these

ways in detail

now let's see the concept of stack now

coming to the stack stack is a linear

data structure which follows last in

first out order that means the element

which are inserted at last will be

removed first

that is lifo order

last in first out now

insertion and removal of the element has

done

at one end i will explain you now so

let's see an example of stack

so here if i'm having 23 45 67 89 11

and let's suppose i'm having 50 so these

are the elements that has to be inserted

in this stack

so now what i will do so this is my

empty stack let's suppose that

and inside this stack

i will insert these elements one by one

so first i will insert 23

after 23 i will insert 45

then i will insert 67

after

89

11

and 15 so this is my stack now as i told

you the element which is inserted at the

last will be removed first that means

last in first out or leaf order so you

have seen here 15 is the last element

that has been inserted here so now if

you want to remove the element then 15

will be the first element that will be

removed so for insertion we are using

push so push was used to insert the

element and pop will be using to remove

an element from the stack so 15 is the

last element that was inserted so now

i will be using pop to remove this 15 so

once 15 has been removed then i'm having

element 23

45

67

89

and then 11 right so once again if i

want to remove the element then my 11

will be removed so once again i will

write here pop so always remember that

push operation will be used for the

insertion and pop operation will be used

for the removal so whatever the elements

i was inserting here 23 45 67 89 11 15 i

was using push operation so if i'm

writing push 23 then 23 was

inserted then after that if i'm writing

push 45

then 45 was inserted and after that if

i'm writing push 67 then 67 was inserted

and in this way i can use the push

function to insert the element now

as i written here insertion and removal

of the element has done at one end why

if you see

this was my stack

right so this is my stack so whatever

the element i was inserting in an empty

stack i was inserting it through one end

right and i was doing insertion through

push operation now

if i'm doing the pop operation then also

i am doing the pop operation through one

end so that's why you can see that here

it is written that insertion and removal

of the element has done at one end so

this was the basic concept of stack now

let's see the example of stack so you

can see here this is my pile of coin

right so this can be considered as the

example of a stack why because the last

coin is removing first here so this

follows last in first out so i'll remove

one coin one coin so if i'm reviewing

step by step that means the last coin

will remove first and in this way if i

will follow then you can see that i can

remove one coin one after other one

after other and in this way this will be

the example of stack similarly the same

example goes for the dvd if i am

removing one dvd after other then this

can be example of stack so the dvd which

was inserted at last will be removed

first the same goes for the books the

book which is on the top will remove

first and after that if i am going one

by one from the top so you can see that

the last book that was kept will remove

first and in this way this can be the

example of stack so this was the basic

example of stack now let's see some

functions associated with stack so we

are having push function so as i told

you that if i'm writing here push 23 and

let's suppose this is my stack

so this is an empty stack so it will

insert 23u

so here you can see that it is used to

insert the element x at the end of stack

so

here instead of x if i'm writing 23 then

it will insert 23. similarly pop

function as i told you that power will

remove the element from the stack

so it is used to remove the topmost or

last element of the stack so if there is

only one element in the stack 23 and if

i am writing pop then it will remove 23

right and also

please remember that it will remove the

topmost or last element in case of this

stack we are having only one element so

this will be the last element so if i am

writing pop then 23 will be removed but

what if i am writing here push let's

suppose that 25 then 25 will be inserted

here and once again if i'm writing pop

so this will be the last element so 25

will be removed

so this was the basic idea about push

and pop function now coming to the size

so size function will give me the size

or you can say the length of the stack

next we are having top so it will give

the reference of the last element

present in the stack so let's suppose

that this is my stack

and i am having 23 25 and let's suppose

27 so this is my last element here

so top function will give me the

reference of this last element

now

coming to the empty function so empty

function returns true for an empty stack

so

if this is a stack

and if this stack is empty then the

empty function will return us true right

so this was the basic idea about

functions in stack and what will be the

time complexity for each function so

here the time complexity for each

functions will be big o of 1

for push pop size stop and empty so for

every function time complexity will be

big o of 1 so this was the basic idea

about the functions now let's see the

stack implementation so there are

several ways to implement stack in

python we can use list

we can use collection module from where

we can provide dq class and we can also

implement through queue module so these

are some ways from which we can

implement stack in python so now let's

see the implementation using list so in

implementation using list list in python

can be used as a stack so we can use

list as a stack in python so in python

we are having append and pop function we

don't have any push function in python

so if you want to insert the element we

need some function right so we can use

the append function which is used to

insert the element now coming to the pop

function yeah we are having power

function in python and pop removes the

element in the lifo order that means

last in first out and as we know that

our stack also follow the leaf order the

elements which are inserted at last will

be removed first so these two are the

functions that we will be using here in

list

now

let's see the logic of this as i told

you that list in python can be used as a

stack right so here i am using list as a

stack so this is my stack variable and

this is an empty list

and now as i told you that if you want

to insert the element then you can use

append so this was my empty list that is

stack and as we know that in python list

is denoted by square brackets so now

what i will do i will write here stack

dot append

[Music]

and inside this append if i'm writing x

so x will be inserted in my list

now now coming to the pop function if

i'm writing here stack dot pop and if

i'm writing print and inside that if i'm

putting it then whatever the element i'm

having it will remove so let's suppose

that this is my stack and in this if i'm

having x element so if i'm writing stack

dot pop so it will remove this x element

right because i am having only one

element here so the last element will be

removed from the stack so this is the

basic idea from where stack can be

implemented using list now let's see the

practical example

so now for practical implementation i

will be using jupyter notebook so i will

click on here new and then i will go for

python python3

and if i'm writing here

i'll give the name here stack

and let me comment it down first here i

will write here

hashtag and i will write here

implementation

using

list

so as i told you that stack can be

implemented using list so i will create

a stack variable

and this will contain list this is an

empty list and after that i will write

here stack

dot append

and

inside this if i am writing here welcome

after that once again i'm writing stack

dot append

and i will write here now 2

once again i will write stack dot append

all right great learning

so you can see that this is my append

now if i'm printing my stack

so i will click on run button so you can

see that this is my list and earlier my

list was

empty but now through append function i

have inserted welcome to great learning

so now this is my list now what i will

do here

from this stack i want to remove the

element so for that i will be using pop

function so i will write here

stack

dot pop

and i will put this stack dot pop inside

a print function so i'll write print and

now let me execute this

so on executing you can see that i am

getting great learning so that means

the element which was inserted at the

last has removed first right and as i

told you that pop will always follow the

leaf order last in first out so if i'm

printing my stack you can see that i am

getting welcome to because great

learning has been removed through for

function if once again i am writing here

let me copy and paste this

ctrl c

ctrl v

so once again i am performing here stack

dot pop and if i'm printing stack

then you can see that i will be getting

welcome only

so you can see that welcome i am getting

and here stack dot pop if i am doing

then 2 has been removed

right so clearly we can see that we can

implement stack using list through

append and pop function so this was the

basic idea about stack implementation

using list so the another way the stack

can be implementation using dq so we'll

see the concept of implementation using

correction dot dq so here stacks in

python are created by the collection

module which provides dq class so now

let's understand this is a collection

module so in python i will write here

from

collections

so from collections module i will import

my dq class

right so i will write from collections

and then i will write here import

dq

so dq here is double ended queue and

here append and pop operations are

faster as compared to list why because

the time complexity of dq is big o of 1

whereas the time complexity of list is

big o of n and also in list if you are

inserting more element then the list

will grow and it will go out of a block

of memory so python have to allocate

some memory so that's why on inserting

more element in a list the list will

become slow so that's why we come with

another way from the collection module

we import dq and then so i will create

my stack variable and inside that i will

assign my

dq

right so now i will perform the same

operation that i was performing in list

i will write here append

and pop

so always remember that dq will be

preferred more as compared to list

because the append and pop operations

are faster here right and rest all the

concept is same so let me execute it so

now let's see the implementation with dq

so let me comment it down here i will

write here implementation

using

dq

now after this as i told you that if i

want to implement dq then is the class

right so i have to import it from the

collection module so for that i am

writing here from

collections

import

dequeue

and i will write stack variable and

inside this i will assign the dq

now after this i will write here stack

dot append

and let me write the value as xu

and if i'm printing my stack

so on execution

you can see that i'm getting my dq as x

now let me append some more values so i

will write here stack

dot append

y

and after that i will write here stack

dot append

let's suppose that

and once again if i'm executing so i

will write here print

stack

and on execution

you can see that i am getting xyz now

let's perform pop operation so i'll

write here

stack

dot

pop and let me

put inside this into the paint function

so as we know that if i'm writing here

stack dot pop so the last element which

was inserted will remove first so that

will be removed here

so you can see that it's z has been

removed now if i'm printing my stack

so i'm getting here only x and y so you

can see that list and dq are the same

the only difference is that dq is faster

because the append and operations are

faster in dq so this was the basic idea

about the stack implementation using dq

now let's see the stack implementation

using queue so here in implementation

using queue queue module contains the

lifo q that means last in first out so

here basically what happens here it

works same as the stack but it is having

some additional functions so it is

having some additional functions and

works same as a stack

right now we have seen that in list as

well as in dq we were using pop as well

as append operation right but here to

insert the element we will be using put

operation so if i am writing here put of

3 then that means it will insert 3 in my

stack so similarly if i am writing here

get function so it will remove the

element and as i told you that it works

same as the stack so the last element

will be removed first here now we are

having some functions available in the

queue module so the first function that

is get so as i already told you in get

function it is used to remove the

element now coming to the max size so

here max size means the number of

maximum elements that are present in the

queue

coming to the next function we are

having empty function so if a queue is

empty then it will return true or else

in other case it will return false

next full so whenever the queue is full

it will give us true

similarly put i have already discussed

about the put that if you are inserting

any element so you can write the put and

suppose if i am inserting here 2 so it

will insert 2 in a queue now cue size so

queue size will give me the size of a

queue so let's suppose that if you are

having a 3 elements that are inserted in

queue 3 2 4 so what will the size of the

queue

queue size will be three now coming to

the logic so how can i import lifo cue

through the queue module so i will write

here from q

and then i will write here import

and i will write here lifo

and then i will write here q

after that as i told you that stack can

be implemented through the queue module

so i will create a stack variable here

and

i will assign here leave for q

so i write here leave for q

and now if i'm writing here stack

dot put

and if i'm writing 2 so this means i am

inserting the value 2 in a stack

similarly if i am writing here stack

dot get

so that means i am removing the value

from the stack so this is the basic idea

now we will see all these functions in

the practical coding example so let's

start with the coding part i will write

here

comment

and inside this comment i will write

here implementation

using

queue

now after this what i have to do i have

to import lifo cube from the queue

module so what i will write here i will

write from

q

import

before queue

and i will create a variable stack

and i will write now leave for q

so after creating stack variable as i

told you that if i want to insert the

element in a queue then i have to use

the put function right so i will write

here stack

dot put and i will insert here let's

suppose 2 so you have seen that i've

already inserted a 2 element now let me

insert some more elements so i will

write stack dot put and i will insert

three here

and after this i will write stack dot

put

four so this is all about the put

function right so we have seen several

functions in queue so let me write here

function so here i will write print and

if i'm writing here stack

dot cue size

so as i told you that queue size will

give you the number of elements that are

present in the queue and i have inserted

three elements so the queue size must

come as three so on execution you can

see that i am getting the queue size is

three

right now i've also told you about the

max size function right so

inside this if i'm writing here max

size

max size is equal to 3

and

if i'm writing here once again print

and if i'm writing stack

dot full

so as i told you that full function will

return true if my stack is full so here

i've allocated the max size as 3 and

i've inserted 3 elements that means my

stack is full so on execution

you can see that i am getting true right

because my stack is full now if i want

to remove the element from the stack

then which function i can use i can use

here stack

dot

get

and now if i am once again writing print

stack

dot full

will i get true value no because i have

removed one element so if i am running

it so on execution you can see that i'm

getting a false value so here you can

see that we have used the put function

get function full function cue size

function max size so this is the basic

idea about the stack implementation

using queue now let's talk about the

advantages and disadvantages of stack if

you talk about advantages it maintains

data in a leaf order right the data is

maintained in a leaf order that means

the last element that is there in the

stack is readily available for us to use

so one of the

readily available right so one of the uh

applications of using stack is it can be

used to evaluate

expressions

right

then we require this feature that is

lifo

right and all the operations that are

performed in stack like push

pop

and then is

empty and then

all these operations take constant

amount of time

which is very important while you are

playing around with computer programming

or while you're doing competitive

programming at that time these are very

important that you

program in the most efficient way

programming in most efficient way is

important and it is very crucial for

your selection right in computative

programming so

all the since all the operations are

performed in a constant amount of time

so these the stack is used oftenly when

you are doing competitive programming

now what are the disadvantages since we

are restricted right there's a

restriction that we can only add

and remove elements from top of the

stack so this is one restriction that is

there thus it is not very much flexible

right it's not flexible

if you talk about the flexibility of how

we are storing data in the stack it's

not very much flexible so these are the

disadvantages of using stack now let's

try to understand q linear data

structure

what is q

q is a linear data structure

that means all the elements in the queue

are stored in linear

fashion now it follows a principle of

fifo that means there's a restriction

that whatever is the first item in

is the first item that is to be out okay

so now let's try to make a queue it's

suppose you are in a queue

and you're waiting for a movie

you're waiting for a movie ticket to buy

okay so there is one person then there

is another person right so these are few

persons here right and you're waiting in

a queue so now the first person who is

in the queue will be the first person

who will get his ticket right makes

sense right

so he will be the guy who will get his

movie ticket first and he will be out of

the queue then the next person who is in

the queue is the next person who will

get his tickets right

and let's suppose a new person comes in

he's not going to go ahead from this

person rather he is going to go behind

this person then the next person comes

he will go after this person and in the

same same way so this is nothing but a

people

principle okay the first person in is

the first person out okay now insertion

will always take place from the rear end

okay and if you talk about deletion it

will always take place from the front

end okay so this is our front end and

this is our

rear

cool so for examples buying the tickets

from the counter or it can be a movie

ticket or it can be a bus station you

are in front of a bus station trying to

get tickets for your uh bus right

these are some examples now there are

four major operations when you talk

about queue what are those major

operations

let me clear my screen so enqueue so you

are going to insert an element in the

queue this is what you mean by enqueue

thank you you are going to delete an

element okay from the queue then peak

first that you're going to peak the

first element that is in there in the

queue and p class means that you're

going to pick the last element that is

in the queue so you will have two

pointers one is front and another is

real and with the help of these pointers

you're going to enqueue dq peak first

peak last you're going to perform these

operations now one major

advantage of these operations these four

operations is that all of these

operations are performed in a constant

amount of time that means the time

complexity of performing these

operations is because one so that is why

when you talk about computative

programming q is

most commonly used data structure

because of these things right because of

its time complexity right you are able

to perform your uh operations in a

constant amount of time

now let's talk about applications of q

so it is used in scheduling algorithms

of the operating system like first in

first out scheduling algorithm is there

round robin is there

and we have multi-level

queue

that is there in all these algorithms q

is used

okay

for storing the data or the processes

it's also used in maintaining playlists

like when you have a playlist let's

suppose you have 10 songs in a queue

right and after one song the next song

which is in the queue will be played and

it goes on uh for like this right so for

maintaining a playlist again a queue is

used it's also used in interrupt

handling

uh let me take an example here you know

the process state diagram of operating

system so it is also used at that time

so uh when you have an interrupt and

they're in if your process is it is

being executed at that time that process

is printed out and it is stored in a

queue now the next time when this

priority or this interrupt is handled

once it is done then it starts picking

up the process which was in the queue

and starts executing that in the

meanwhile if there are some other

processes that those processes will also

be in the queue so a queue is maintained

and once the interrupt is handled they

will start taking out that process that

is that was being executed earlier and

executes it and completes its execution

and terminates the process so it is also

used in interrupt handling

after learning what is q in python

theoretically let's know how to

implement that into practicality so q

will be having two different basic

operations that is nq and dq so these

things will be shown in with a simple

example in python so let's quickly hop

on to python id that is google collab

for the reason i'm using it is visible

for everybody to access because it's

online availability and it is open

source so let's quickly start the simple

program for queue displaying two

different functions that is enqueue and

dq

so here is the google collab environment

where you'll be working so i'm just

pasting

the code here which is already

done by me so in order to avoid time and

uh i'll explain each and every line of

code here now what we are doing in this

particular code is

we are creating a class called q right

we are also giving different functions

for nq and dq and q is nothing but

entering or inserting values to the

queue and dq is deleting values from the

queue right as you all know q will

follow fifo that is first and first out

so whenever you want to buy a ticket for

example in your railway stations or

anywhere you will stand in a queue right

so whoever in the first will get the

ticket first and he or she will move out

of the queue it's same in here as well

but the elements are not humans it's all

integer numbers so whatever the number

you put in first is the first number to

get out right so let's quickly see

here we have two different functions as

i mentioned that is enqueue and dq and

later you will display we are seeing

three different functions displaying

enqueue and dq so what happens here is

we are using self dot q dot append so

here whatever the item whatever the uh

number you give right it will be

inserted to the back of the queue right

it is maintaining the sequential process

of inserting the numbers or the integers

or the values you give in order to

insert into the queue and while deleting

you can use pop right is it append for

insert and pop for deleting and display

is nothing but a normal print statement

you will display whatever the queue it

is accordingly so let's quickly run this

program here i've just used certain

numbers one two three four five five

numbers and though after dequeuing right

what it should display it should remove

one first and two three four five should

be displayed so let's quickly see how it

is

right

okay so as you can see whatever the

queue is given is printed at the first

place that is one two three four five

and then after removing the first

element right so the first person will

be removed because it is fif4 so 2 3 4 5

is there so this is how a simple basic

queue will work in python

so after knowing a basic q

implementation right let's see one of

the type of queue that is circular queue

implementation there are many types of

queues but still i'm taking

circular queue as an example and showing

you the same operations of inserting and

deleting elements from the queue

so let's quickly hop into the google

collab ide and check out the program how

can we build

a circular queue in python

here is the program for circular queue

and what are the different elements we

have inside this program let me tell you

the first part is class declaration so

here my circular queue is the class

right so

class can be named accordingly or

whatever you feel right so keep it very

program oriented rather than keeping

which is off topic so here it is my

circular queue and then again we have

two different initialization that is for

nq as well as dq so whatever the

elements we use here right whatever the

items we try to insert in the queue we

have to ensure whether the queue is full

or the queue is

empty and there is still space or not so

all the conditions should be checked so

let's hop into enqueue and check out

what are the different conditions you

have to check so the first thing is the

queue is full or not so before inserting

something say for example the queue size

is 5 and the element 6 has been inserted

then it has to show an error message

that is

there are only five spaces they are

inserting sixth element it is not

allowed hence the queue is filled so in

order to print that we use this the

circular queues filled

statement so the next part is

you have to

know how when it is empty right in order

to have the dq the main condition is

whenever the uh

elements are out of the queue then it

has to be declared as the queue is empty

so nothing to delete from the queue it's

every all the elements or items are

deleted already so the error message or

the statement to the user will be the

circular queue is empty now there is

nothing to

pop out or delete or dequeue so

apart from that also you can also

find if you are trying to print

something right if it is mtq it does not

have anything then you have to show up

though

no element in the circular queue found

statement why because if there is no

elements there is nothing to show or

display the display function does not

work the print does not happen so this

is a basic idea of this particular code

and accordingly we have used the

iterations and the declarations so next

you have to look at the

inputs what we are giving i'm trying to

give 12 22 31 44 and 57 right so the

five elements for the queue has been

given and what you have to do is you

have to check the initial values first

you have to display the initial values

what is the exact queue which you have

given with the elements to the user and

then which is deleted so the first

element is deleted obviously but yes how

the circular queue is different from the

basic queue right so let's quickly run

the program in order to see the output

okay if you could see the output here

right so initial q values

so is whatever we have given here that

is 12 22 31 44 and 57 so after removing

an element so obviously the first in

first hour process the first element

will be removed so it is 22 31 44 and 57

what is difference between a normal q

and a circular queue if you could see

here right in the last space after 57

you have a space allocated so

in normal queue it is not connected here

the front and rear is being connected

forming a circle right if one

the first element for example 12 goes

out

the 22 will take the first place and 31

followed by 44 followed by 57 the last

place will be empty

right so it is in circular motion so

whatever you want to insert again right

so that will for example if you want to

insert six right six will sit in the

fifth position that is after 57 right

this is this will be connected circular

motion that is front will be connected

to the rear part so this is the

difference between the normal basic q

and the circular queue now let's talk

about advantages and disadvantages of q

first we are talking about advantages so

it follows a principle of fifo or the

elements are stored in the fifo manner

that means let's suppose this is a queue

and in this queue you have elements

so the deletion will take place from the

friend right and

the insertion will take place from the

rear side

so this is known as dq

the deletion

and insertion is known as enqueue

operation and both these operations are

performed in a constant amount of time

so that is one of the advantages right

and the insertion from beginning and

deletion from end takes a constant

amount of time plus if we want to do

peak first peak plus all these

operations are performed in a constant

amount of time and this is most widely

used data structure when we talk about

cp that is computative programming when

we talk about computative programming

this data structure is most commonly

used because of these features that all

the operations that are performed like

insertion deletion peak first p class

and qdq all these operations are

performed in a constant amount of time

now let's talk about disadvantages

since we are only able to delete or

insert from the front and the rear that

means deletion from fret and insertion

from the rear so the restriction of

insertion

or any manipulation right we have a

restriction over these right what these

operations insertion and deletion

so this restriction is always there and

so this data structure that is the queue

is not

is not much flexible

right we are fixed we can delete and

insert element in a fixed pattern or

in the fifo manner thus it's not much

flexible so now let's start with the

link list

so link list is a collection of group of

nodes now what is node here so here you

can see that this is a node so a node

will contain a data

as well as reference

so each node contains data and reference

which contains the address of the next

node so this is a node and as i told you

that node will contain a data as well as

reference so let's suppose i am

inserting the data here 20 and this is

nothing but a reference or you can say

that pointer so

this pointer will contain the address of

the next node right so as i told you

that linked list is a collection of

nodes so this is nothing but a single

node so let's suppose if i am having

more than one node

and if i am connecting them

then it will form a linked list so we

will see the linked list representation

in the next slide now

so link list is a linear data structure

now coming to the last point we know

that in array as well as in list

elements are stored at the contiguous

memory whereas in linked list elements

are stored randomly now let's see the

representation of linked list

so as i told you that ling list is a

collection of nodes so let's suppose

that this is my n1 node this is my n2

node and this is my n3 node so each node

will contain data as well as reference

or you can say pointer so this is data

and this is reference so now i will give

the address of this n1 node so let me

write the address of this n1 nose at

2010

i will give the address of this as 2020

and i will give the address of n3 node

as 2030 so these are the addresses

so as i told you that each node will

contain a data

so let me assign here data let's suppose

10 is here and a reference or you can

say a pointer so i told you about

pointer that pointer will contain the

address of the next node so what's the

address of next node the address of next

node is 2020 so i will write here 2020

so this pointer or this reference or you

can say this link will contain the

address of my next node and what's the

address of my next node is 2020 now

again this will be a data

and this will be a reference

of my

n2 node so let me assign here data as 20

and what will be the reference the

reference will contain the address of

the next node so here it will be 20 30.

now again this n3 will also contain data

so i will assign here 30 so now you

might have a question that what should

be reference here

so now

are you seeing any node after this n3

node do we have node n4 or n5 not right

so

this reference will be assigned to null

so i can write here phi

because there is no next node is present

there right now coming to head what is

head so head will contain the address of

my n1 node that means 2010

right

so this is my linked list representation

now the question arises that why link

list so now why do we need link list

because ling list is having more

efficiency for performing the operations

as compared to list so what are the

operations that we are performing in

linked list we can perform the

operations like insertion deletion as

well as traversal so it is having more

efficiency in performing the operation

so moving to the next point as i already

told you that in linked list elements

are stored randomly whereas in list or

you can say in array elements are stored

at contiguous memory now moving next

accessing the elements in linked list

will be slower as compared to list so if

you want to access the element in linked

list it will be slower as compared to

list why i will tell you the reason

now let's see this slide link list

representation so here this is my n3

node right and if i

want to access the data elements of this

n3 node then i have to go from n1 n2

and n3 then only i can access the

elements whereas in case of list we can

access the element through indexing but

in linked list it's not possible so you

have to go traversely

right

here traversal means that you have to go

through each node so if you want to

access the elements of n3 then you have

to start with n1 then you will go to n2

then you can go to n3 so that's why

accessing the elements in linked list

will be slower as compared to list now

coming to the last point here in linked

list utilization of memory will be more

as compared to list

so let's start with the singly linked

list

so i've already showed you the

representation of linked list which is

same as the singly linked list so in

single linked list i am having here a

data and reference in a node so

let's suppose that this is my n1 node

this is my n2 node and this is my n3

node so as i told you that each node

will contain data as well as reference

so i will give here data let's suppose

10

in node 2 i will give as 20 and here i

will give as 30

and each node is having an address so

let's suppose the address of this n1

node is 1000

it's having 1100

and it's having 1200

so this reference or you can say that

link or pointer this will contain the

address of the next node so this will

contain 1100 similarly my this reference

or this link will contain the address of

n3 node so i'll write here

1200

and here after n3 node do you see any

node we are not having any node so here

this link or this reference will null

now coming to here what is head here so

head will contain the address of my

first node that is 1000 so in single

linked list the traversal is done only

in one direction so what do you mean by

traversal troublesome means that you are

going through each node so let's suppose

that if you want to go to the n3 node

first go to n1 then n2 then only you

come to n3 you can't directly jump to n3

you have to go through n1 and n2 then

only you come to n3 now let's see some

operations in singly linked list so we

are having several operations in linked

list we are having insertion deletion

traversal so insertion as well as

deletion can be done at beginning at any

specified node as well as end

now coming to the traversal i have

already told you that traversal means

you have to go through each node

so going through each node of the linked

list is a traversal now let's see the

pseudo code of singling link list so if

you want to create a node in a singly

linked list then what should be the code

here so i will write first here class

node

so here i have created a class whose

name is node so this class node will

also be having an object right i will

create object later on but

let's see

let's suppose this is my n1 node as i

told you that a node will contain data

as well as

reference

right so instead of reference i am

writing here next i am taking a small

word here so that it will be easy for

coding now so this is my node creation

now what i will do here so in this class

node you have seen that i am creating a

init method or you can say a constructor

so to create it first i will write a

reserved word that is def and then i

will write init method so

i will write first def

and then underscore underscore init

and then i will write underscore

underscore then i will write self

and then comma comma data

so why i have written here self i will

tell you later on and i've also passed

data as a parameter here so inside this

i have written self dot data is equal to

data and self dot reference is equal to

none so why i have written this because

my node will contain data as well as

reference so i will write here in this

method self

dot data

is equal to data

and self dot reference i've written here

next so i will take here next

is equal to none

so when you are creating a node let's

see this is a node n1

so initially it will be having a data

and because i am just creating a node as

of now i am not linking this node so the

link or you can say the reference

will be none

right so this is my initial load i have

written here self.data is equal to data

and self.next is equal to none

right

now

this is a class was name is node i can

create the object so how to create an

object i will write here n1 and then i

will write here class name

node

and inside this class i will pass the

parameter 7 so here now what will happen

instead of self my object will pass here

so my n1 will pass here instead of self

so now it will be n1 dot data

is equal to and what's my data data is

seven

now the next step we are having the self

dot reference is equal to none right

let's see here self dot next is equal to

none so instead of self my n1 is there

so n1 will be pass here and n1 dot next

i will be having a none

so this is nothing but a creation of my

node now if you want to check then we

can write print function and when you

will write here node 1 data inside a

print function you will see that you are

getting the value s7 similarly if you

are writing node 1 dot reference inside

a print method then you will be getting

none so now this is the idea about how

to create a node now let's see this into

a coding

so i will be using here jupyter

notebooks so i will go on here new

and then i will click on python 3

and here you can see that i am getting a

name untitled 21 let me change it i will

write here linked list

linked list

and i will write here python

now

let's create a node so i will comment it

down creating a node

so first i will create a class

and i will give the name as node

and inside this

class node i will create my edit method

so i will write here def which is a

reserved word and then i will write here

init

but before that i will write underscore

underscore

then again i will write underscore

underscore and then i will write here

self

comma

data so so why i have written here self

so when i'm creating a class object that

is n1 i've already showed you in the

example so instead of self and one is

fast

so as we know that we can create a

multiple object of a class so if i'm

writing here n2 or n3 then instead of

self i can pass n2 and n3 also

so now let's create a node

so i will write here self

dot data is equal to data

and i will write here self

dot

next

i will write here none so this is my

node creation so whenever i am having a

node it will contain a data and it will

be having a reference so initially it is

not linked so the reference is none

so this is my class now i will create an

object of node so i'll write here n1

and i will write class name

and i will pass data as let's suppose 8

value here

so if i'm executing it so on executing

this n1 will go to the self and this 8

will go into the data so my n1 dot data

is equal to 8 and my n1 dot next is

equal to none let me print it so if i'm

writing here print

and inside that if i'm writing my n1 dot

data

once again if i'm writing print function

and inside that if i'm writing n1 dot

next

then you can see that i'm getting the

data as 8 and the next that is a

reference i'm getting as none because i

didn't link this node to any other node

so this is the basic idea how to create

a node now let's see how to create a

class of singly linked list so

when will my singly link list will be

empty so as i told you that

if this is a node

let's suppose n1 this is another node n2

so n1 and n2 are connected with each

other so we are having a head pointer

which always points to the first node

right so if there is no head if head is

none then my linked list will be empty

so now what i will do here so i will

create a class and i will give the class

name as let's say singly link list

and inside this class once again i will

write init method so i'll write here def

underscore underscore init

underscore and i will write here self

now here i will write self

dot

head

is equal to none

so this is my condition to create a

class so if the head is pointing to none

that means it is not pointing to any

node and

it shows that linked list is empty

so now let's see the creation of single

link list

yeah so let me remove this

now i will create a class so

creating a linked list

so if i want to create a linked list i

will create a class of linked lists so i

will write here class

singly

linked list so this is my class and

inside this class i will once again

write init method

inside the single linked list i will

create a init method so i'll write def

underscore underscore init underscore

underscore and then i will write here

self

and when my link list will be empty so

when self

dot

head

is equal to none

so this is the simple way to create a

single english class

now

so after creating a class now let's

create a object of this linked list so

i'll write here sll singly link list

this object name

and

now i will write the class name so class

name is singly

and then capital ll is there right

so

on execution always remember whenever

you are creating an object and if you

are executing it so inside this class

init method will always run i will show

you the example if inside this init

method let's suppose if i'm writing here

print gaurav

so i've created the object here sll

and right now if i'm executing then you

can see that gaurav is executing here

right so always remember whenever i'm

creating an object of class and whenever

i'm executing it so whatever the

statements are inside the init method it

will execute

so on execution what will happen here

i will get here

sll

dot head

is equal to none

right so sll is my object so instead of

self sll will assign here so sll dot

head is equal to none

right so this is my basic concept of

creating a node and creating a linked

list

so after creating a node and then

creating a class of singling link list

now let's see the traversal in ling list

so what is traversal as i already told

you that traversal means going through

each node

so now let's see when we can do the

traversal in a linked list so this is my

singly linked list

so this is n1 node

this is n2 node this is n3 node and this

is n4 node and each node will contain a

data

as well as next

right

so this will contain a data next

similarly n3 and n4 will contain a data

in next so as of now these nodes are not

linked with each other and if i want to

do the traversal then i have to go

through each node that is from n1 then i

will go to n2 then n3 and then n4 so

now let's see the case scenario so the

first case will be if self dot head is

none

so in that case my linked list is empty

right so when my english is empty i

can't do the traversal so in this case i

will write here print

linked list is empty

if condition this is if condition and

then i will write one more condition

else and inside else if my self.head is

not none

then what i will do see as we know that

head will be always pointing to the

first node so this is my head here

so i will create a temporary variable a

is equal to self.head

now if i want to traverse then i have to

develop a logic so that i can go from n1

to n2 to n3 to n4 so i will use a while

loop

let me write here

this was else

and inside that i'm writing a is equal

to self

dot head

now i'll write a while loop so i'll

write here while

a is not none

i'll give a condition a is not none

because if my a is none and here a is

self dot head so if self dot head is

none then it's an empty linguist so

traversal can't be done so inside this i

will write a logic a is equal to a dot

next now what is a dot next here let's

suppose that this is a n

if i'm writing here n1 dot next

is equal to n2

so that means i am linking this node and

one node to n2 the link has been

generated now if i am writing here n2

dot next

is equal to n3 then again

the link has been generated and this

next will contain the address of n2 so

let's suppose the address of n2 is 1200

so this next will contain 1200

now if i'm writing here n3 dot next

so we know that this is next here right

so n3 dot next

will be n4

so you can see that i am writing here a

is equal to a dot next inside a while

condition so initially this will be my a

the loop will run and my a will shift to

n2 similarly my a will be is equal to n3

then similarly my a is equal to n4 so in

this way the traversing will be done

so i have given you the basic idea now

let's see the coding to understand in a

better way

so let's see the coding of traversal in

linked list so let me write here in

comment

traversal

and linked list

so first i will create a class

of a node and i will give the name as

node

and inside that i will create

my init method

so i'll write def underscore underscore

init

underscore underscore and then self

and i will write data also

because i will pass the data element

value

so i'll write here self dot data is

equal to data

and then i will write your cell dot

next

is equal to none

so this is my node in which i'm having a

data and i'm having my reference or link

you can say that as none

now after creating my node i will create

a class of single linked list

so this is a class of my single link

list

and inside this class once again i will

create a init method

now so as i know that my single link

list will be empty when my head is

pointing to none so if head is pointing

to none then ling list is empty so you

can't traverse right because traversal

can't be possible in the empty link list

so

this is my linked list so inside this

linked list first i'm giving the

condition self dot head is equal to none

now

inside the same class sll what i will do

i will create a function

def and i will write here traversal

and then i will write here self

now i will get the condition so the

first condition is that if your linked

list is empty so when your linked list

will be empty when self dot head is none

then you can't do the traversing

so i'll write here if

self dot head

is none

a right print

singly linguist

is empty

and i give the another condition else

so the first condition was that if self

dot head is none the ling list is empty

now coming to the next condition when

myself dot head is pointing to the first

node then only i can do the traversal

right

so so i will create a temporary variable

where a is equal to self dot head so why

am creating a temporary variable a

because i want my head value to be fixed

i don't want to change my head value but

i am using while loop here so a value

will be changed so that's why i've

created a temporary variable in which i

have assigned self.head so that head

value is not changed now after this what

i will do i'll write here while

while a is not none

i like simple print

a dot data

and then i will write here

and

is equal to then i will write codes and

i will give a space so that whatever the

data elements are printing there is a

space between them and then after that i

will write my logic a is equal to a dot

next

so a dot next why i am writing here to

connect one node with to the another

so this is my main logic that i have

written inside a traversal function

now let's see how to execute this

program so first i will create a node so

let me write here n1 is equal to node

and let me insert the values five

so i'll create four nodes in this so

i'll write here n2

is equal to node

i'll give the data element value 10 here

end to node and n3

i'll give the value as 15

and i will give the value for n4 let's

say 20

so these are the nodes right after

creating node what i will do here since

this is the sll class i have to create

the object of this also so i'll create a

object here so let me create the object

i'll create here sll is equal to

sll

so just write any variable name so i've

written here small sll then i've written

equal to then i've written the class

name capital s

small l small l then i've written

open and close parentheses right so this

is a way of creating a object of sll

class so as soon as i have created this

sll object this init method will run

automatically right so my sll.head is

equal to none initially now what i will

do here after this i will write here sll

dot head and i will assign to n1

now i have to connect the node so what i

will do here once i have created n2 node

so for connecting i will write here n1

dot next

is equal to n2

similarly after creating n3 node i will

write here n2 dot next

is equal to n3

and after creating n4 node i will write

here n3 dot next

is equal to n4

now what i will do here i want to call

this function so how to call this

function so what's the object of this

class this is right small sll so i'll

write here sll dot was the function name

traversal

so i'll write here traversal

so now what will happen here once you

are calling this function so instead of

self this

object will go sll will go here right

now let's execute this and then i will

explain you the logic how this is

working

so on execution you can see that

sll.head is equal to

n1

so here n1 is not defined yeah because

once i have to create n1 after that i

have to assign it right so let me

write here control x

and then ctrl v

now if i'm running it

you can see that i am getting 5 10 15 20

right because here first i have assigned

sll dot head is equal to n1 so here what

was the mistake i didn't create the n1

node first and i have assigned the sl

dot head is equal to n1 so first you

have to create the node then only you

can assign right

now let's understand the logic so here

n1 is the object of class node right so

n one is equal to node five and five is

the data element value so when i'm

writing this so what i will get here so

instead of self n1 will pass and instead

of data 5 will pass so i will get here

n1.data is equal to 5 and i will get

here n1.next

is equal to none

so after this i have created the object

of my singly linked list so what will

happen as soon as i am creating the

object this init method will run so

instead of self sll will pass so i will

be getting here

sll dot

head

is equal to none

so as of now you can see that my sl dot

head is equal to none so still my

list is empty

right

so i have to assign this sll dot head to

n1 so that my head is pointing to n1 so

here i've written sl dot head is equal

to n1 so now my head is pointing to n1

now after that once again i have created

the node

n2

so

what will happen here i will get here

n2.data

is equal to 10

let me write comma u

and enter.next

i will be getting as none

now as soon as i have created my n2 node

what i will do i will connect n1 node

with n2 so i have written here n1 dot

next is equal to n2 so initially my n1

dot next is equal to none but now my n1

dot next is equal to n2 so as of now

i've created the node n1 and n2 and the

head is pointing to n1 and i've also

linked the nmr node with n2

similarly once again i'm creating a n3

node so

n3 dot data

n3 dot data is equal to 15

and after at n3

dot next

is equal to

none

now after creating this

what will happen once i have created my

n3 node then i will connect n2 with n3

so i've written here n2 dot next is

equal to n3 similarly once again i will

create my n4 node so again the same

logic will perform n4 is equal to node

20. so again i've written here n4 so n4

is my object of class node and n4 will

pass into self and my data will be 20.

so let me write here n4.data

is equal to 20

and the same thing

and 4

dot next

is equal to none

so after creating n4

now i will connect n3 to n4 right so i'm

having only four node here you can see

that i've created n1 n2 n3 and n4

so after n4 i don't have any node so

what will be n4.next is equal to none so

that's why i didn't write anything after

this

so

now it's time for calling this function

so how to call this function so i have

already created the object of sll class

so the object was a small sll so i've

write small sll dot traversal which is

the name of this function so inside this

cell sll will pass here right

so what will happen here

sll dot head so sll dot head is what

initially sl dot head is equal to none

but i have a sign here sl dot head is

equal to n1 right so this is not none so

it will jump into this condition so now

what will happen here let's see the

logic so here a is equal to self dot

head and what's my self dot head

myself dot head is sll dot head

so my a is equal to sl dot head so now

after this i have created a while loop

so here

i will write here while and then instead

of a i i'll write sll dot head is not

none so

after this what will happen this is my

while loop so here i have written while

a is not named so my a value is sll dot

head so

is my sll dot head is none no why

because my sll dot head is pointing to

n1 you can see that my sll dot head is

pointing to n1 so it's not none

right

so what will happen here

initially my

is

let me write here

is

sll dot head

so now it will print me

the value a dot data so what is a dot

data

so slr dot head is nothing but pointing

to n1 so i will write here n1

so a dot data is nothing but it is equal

to n1 dot data

and what's n1 dot data n1.data is 5 so

it will print 5 right so you can see

that i'm getting 5 as the output now if

you see here

a is equal to a dot next so what is my a

a is nothing but my n1 right

so i'm writing here n1 dot next

so here you can see that i'm getting a

is equal to n1 dot next so again it's a

while loop right so once again it will

jump here now a value is equal to n1 dot

next so n1 dot next is pointing to none

no n1 dot next is pointing to n2 so it's

not none so this condition is still

satisfying

right and once again it will print the

data that is

here the a value will be

n1 dot

next

so now once again if i'm moving to this

print statement so a dot data so let me

write here a dot data so what will be

the a dot data

this time n1 dot next so what is n1 dot

next n1 dot next is nothing but n2 right

so n2 dot data

it will give so n2 dot data is what

n2 dot data i am getting as 10

right so it will print 10. similarly

once again

you can see that my a is equal to i will

be getting here

a is equal to n2 dot next

so once again it is going into dot next

so n2 dot next is containing the address

of n3 so it's not none so once again it

will print here n2 dot next dot data so

what is n2 dot next n2 dot next is

nothing but n3 so n3 dot data will give

me

15

right

now what will be a a is equal to a dot

next so my a value is here n3 so n3 dot

next right so my a value will be here

entry dot next so once again it will go

here so a is equal to n3 dot next so n3

dot next is none no it's again pointing

to

n4 that means entry dot next contains

the address of n4 right so it's not none

so a is equal to n3 dot next so what is

n3 dot next so n3 dot next is nothing

but n4 so n4 dot data will give me 20

right so after giving me 20 once again

i'm getting here

n4 now what will happen here a is equal

to a dot next and my a value is n4 right

so a is equal to n4 dot next so if i'm

getting here n4 dot next so what is n4

dot next and four dot next i am getting

here none right

so yeah this condition is not satisfying

and hence the loop will end

because n4 dot next is equal to none and

my condition is while a is not none so

this is the basic logic so in this way

we'll get the values 5 10 15 20 and the

traversal will be done in linked list

now after traversal we will see the

insertion in singly linked list so

insertion can be done in three ways we

can do the insertion at the beginning of

the node we can also do the insertion at

the end of the node and we can do the

insertion at specified node now let's

see the insertion first at the beginning

so in the previous coding example i was

having four nodes

so let me write here the name of node n1

n2

n3

and n4

and i've also shown you the traversal in

linked list so here i've assigned the

data as 5

10

15

and 20

right

and this n1 was connected to n2

similarly n2 was connected to n3 n3 to

n4 so we have seen the traversal like

this head was pointing to my n1 node

right so this is nothing but my link so

link will contain the address of this n2

road

similarly this is again the link of end

to node so this will contain the address

of n3 node so up to here we have seen

right now i will insert a node at

beginning so

let me create a node nb so how i will

create a new node i will write here nb

is equal to node

and i'll write here data so nb is

nothing but it is an object of a class

node right so here instead of data if

i'm passing to so my data will be here

too and this next value or you can say

the reference will be none

right now i didn't link this nb node to

anyone so this is my nb node here

and let's suppose the data is here too

and it's not connected so initially it

will be none

now i have to find the link between nb

node to n1 right so what will be the

step nb dot next

is equal to self dot head

so this is a simple logic so when i'm

writing nb dot next is equal to

self.head that means i'm creating a link

from nb dot next because this is my next

right and i'm creating a link from nb to

n1 now if i am creating a np node

then this is my first node

so you can see here nb is now my first

node so head must point to nb right

because head will point to the first

node so here i have to remove this head

and point to here so for that which

logic should i write i will write here

self dot head

is equal to nb

so now my head will be pointing to this

nb so let me remove this

so i will write here now let's see it in

coding

so this is my traversal code so what i

will do here inside this class singly

linked list i will create one more

function and let me create the function

and i will give the function name let's

suppose def and the function name insert

at the beginning so i'll write here

insert

at beginning

so i have to insert here so which

parameter cell i gave you i have to

write self

first so after self i have to give data

because i want to put the data value

inside a node

so inside this function i will first

create a node so nb is equal to

node

and v is equal to node and then inside

this node i will write here data

now

after this i will perform my logic so

what my logic is my logic is nb.next

is equal to self

dot head

so nb dot next is equal to self.head

will create a link between nv and n1

node and after that i want to change my

head from n1 to nb so i'll write here

self dot head

is equal to

nb

so this is my function so how to call a

function so here you can see that this

is a class sll so the object of this

class is sll

so i can

call it through

i'll write here

sll

dot

and after that i will write here insert

at

beginning

and let me put the value here too

so i will call this function and

instead of data i have given the value

as 2 so all the statements inside this

function will execute

now i want to print this function right

so here you can see that the traversal

logic is written here so i'll write here

sll dot traversal

and now if i'm executing it

so you can see that i'm getting my

output but let me write here print so if

i'm writing here print then i will get

my output in the next line right because

here inside this print i didn't write

anything so it will give a

space so now if you see i'm getting 2 5

10 15 20 so the nb node was having a

data element as 2 right here you can see

that my envy node has been inserted so

this is my first node so the new link

list will be having the elements 2 5 10

15 20. now let's understand the logic

how this thing is working so here i've

given the data as 2

so data is equal to 2 here

and now after this

and b is equal to

node

instead of data two will be here so now

if you see this this is my object of nb

right and this is a class so here what i

will get here i'll be getting here

let me write comma

i'll be getting here nb.data

is equal to what's the data value 2

and now

i'll getting here nb dot

next

is equal to

none

so this is the creation of an node which

is having a data element as 2 and its

next that is the reference is none so

this means this node is not connected

with any other node now i have to

connect this node so i have written the

logic here nb dot next

so here you can see that nb dot next

is equal to self dot head so what is my

self self is nothing but i am calling

through the object sll right

so instead of self it will be sll so

sll.head is what

sll.head is myanman

here you can see that

so it will be n1 so here sll dot head is

nothing but my n1 now what will happen

here nb dot next and this is the n1 node

so i have created a link between these

two nodes so nb and n1 node are now

connected now after connection i have to

change my head position so my initially

my head position was assigning to n1 but

i have to change it so how to change it

so here instead of self my sll will be

here so sll dot head is equal to nv

so you can see that i have changed my

head position so this is the basic logic

for the insertion at the beginning so

what i've done here i've created a node

then i connected the nv node with n1 and

then i've changed the head position from

n1 to nb this is the basic logic for

insertion at beginning

now we will see the logic of insertion

at end so this was my node

initially i was having

four nodes n1

n2

n3

and n4

but i've created a new node right

insertion at beginning so this will my

head

and it was containing a data s2

and the link of this nb node contains

the address of n1 node

so n1 node data was 5 here 10

for n3 it was 15 and 20

and n1 was connected to n2 and 2 was n3

and 32 n4

and here next value was none

so this is the singly linked list up to

insertion at the beginning now we will

see the insertion at end

so for the end insertion i have to

create a node

so let me give the node name here any

and once again this node will contain a

data

as well as

next or you can say the link but this is

the last node insertion at last so this

will contain the value as none

so initially when you are creating any

node then its link is pointing to none

so this is the any node and here the

link is pointing to none but this is the

last node so i want the link to be none

itself

right

now i'll give the data here

so let me write here n e is equal to

node

and then data

so this is my basic creation of node now

what i will do

i want to

create a link

of this any node with n4 right so this

is my any node and i have to connect any

with n4 so as we know that in linked

list you have to

go through each node that means you have

to do the traversal right you can't

directly jump to any you have to first

start from nb then n1 n2 n3 n4 and then

you can go to any you can't directly

jump so now what will happen we know

that we have to go from nb to n1 n1 to

n2 n2 to n3 and n3 to n4 and then we can

come to n4 to any so we have to develop

a logic so this is my head my head is

pointing to nb so i don't want to change

my head so i'll create a temporary

variable a is equal to self.head

now you might have a doubt that why i'm

creating a temporary variable because i

will use this temporary variable

in a while loop so that if i am using a

while loop then the value of a will be

changed right so that's why i have

created this temporary variable so that

my head is fixed now i'll create a while

loop i will write here while a dot next

is not none

so here i will give a condition while a

dot next is not none so why i am giving

this condition because here you can see

that inside this while loop i will write

here a is equal to a dot next so what

will happen here my a is equal to this

one self dot head initially my a is here

right and here it will check a dot next

is not none so this is my a right so a

dot next is pointing to n1 so is it none

no it's not done why because a dot next

will contain the address of n1

right so here

it will execute the statement inside

this while loop and i am having the

statement a equal to a dot next so my a

value will be

here

so my new a value will be here at n1

node similarly once again this while

loop will work and again a dot next so a

dot next is pointing to n2 so it is none

no it's not none so once again a is

equal to a dot next so my a value will

be coming here similarly once again this

loop will work and my a value will shift

here here so up to n4 my a value be here

now i have to create a link between n4

and any so how can i create a link i can

simply write here a dot next

is equal to any

so if i'm writing a dot next is equal to

any so this none will be removed and i

will create a link from n4 to any node

so this is my logic here and here this a

dot next is equal to any is not inside

this while loop it's it is outside the

while loop right so indentation is here

up to a equal to a dot next this is

outside

this while loop

now let's see the coding part

so i've zoom it so that you can see it

clearly now after insertion at beginning

i will create a function

inside the class node itself i'll write

here

def and write here insertion or insert

at end

so insert at end

and once again i will write yourself

comma data

so now if i want to insert the element

at end also then i have to create a node

so let me write here node any is equal

to node

and then i will write here data

now after creating a node i want to

traverse because this is my last node so

if i want to reach to the last node i

have to go through the each node so

that's why i will create a temporary

variable here a is equal to self dot

head

so once i'm creating a temporary

variable i'll create a loop so i'll

write here while

so while a dot next is not none

then a is equal to

a dot next

and now after this i will simply assign

a dot next

is equal to

n e

so this is the connection of my last

node that is n4 node to any right and

here i have created this while loop so

that i can

go through each node now let me print

out this so what i will do now

i will simply write here

sll

dot

insert

attend

and

let's take the value as 25

attend

and now i will display so i'll write

simple here sll.traversal

so let me do the execution here

and on execution i'm getting the output

but it's confusing so i'll write here

once again print

so that i can get space

between the outputs so here you can see

that i have inserted a node which is

having a data element as 25 and which is

inserted at the end so this is the

execution part now let's understand the

logic how this thing is working exactly

so here

i've given the data as 25

so data is equal to 25 here

now

what will be here any

if you see here

then my any

dot data is equal to 25

and here my any

dot next

is equal to none

right

so this is my creation of a node

now

after this

what will happen here so here you can

see that a is equal to self dot head so

instead of self sll will pass right so

sll dot head

why sll will be passed here because i am

calling this function

with my object sll right so sll dot

insert at end so instead of self sll

will pass here

so here sll dot head was my nb

right

so it will assign to nb so as we know

that nb was my first node so head will

be the pointing to nb itself up to this

this was the logic now coming to here

here you can see that a dot next so what

is a dot next

so here a dot next is equal to nb dot

next why because my a value is nb so nb

dot next is my none no it's not none

because nb dot next contains the address

of n1 so that means

it's not none so once again inside this

loop what will happen

my a will assign to a dot next that is

nb dot next

now you might have a doubt what is nb

dot next nb dot is next is nothing but

n1 right here you can see that

so nb dot next is equal to n n1 that

means my nb is connected to n1 similarly

once again what will happen here this is

a loop once again it will go here

so

if you see here a dot next so what is a

dot next my

a is equal to n1 now so i will be

getting here n1.next

right so once again a is equal to n1 dot

next so what is n1.next

so my a value will be here

n2

because n1 dot next is n2 right so once

again it will go n2 dot next so n2 dot

next is nothing but n3 so inside this

once again a value will be assigned is

n3 then once again n3 dot next will go

so in this way you can see that we are

going through each node and we are

connecting them now what will happen

here once i reach to n4 right so i have

to create a link from n4 to any so i

will write here n4 dot next is equal to

any right so here you see this is my

while loop so inside this at last what i

will be getting here i will getting here

and four dot next

because n4 dot next is none right so

this loop will end

if you see here

you can see that n4 dot next is none so

my loop will end here and

what is my a dot next value so instead

of a i was getting n4 so n4 dot next was

my none but i have assigned here n4 dot

next

to any

right so that means now n4 is connected

to any now what will be the any dot next

it's none because this is last node so

here you can see that while creating the

node itself i got any dot next is equal

to none so this is my basic logic of

insertion at end

so we have seen the insertion at the

beginning of the node we have also seen

the insertion at the end of the node now

we will see the insertion in between so

that means we will see the insertion at

any specified node so initially i was

having four nodes n1

n2

n3

and n4

then i've done the insertion at

beginning

so this was my node nb and then i've

done the insertion at end so this was my

node any and these were the four nodes

n1 n2 n3 n4 and we were having the data

right 5

10

15

20

and 25 for any and for this we were

having the data s2

right now what i will do i have to

insert the node

at specified position so the process

will be the same i have to create the

node first so for creating node what i

will do here let's suppose this is my nb

node so initially

i'll create a node nb is equal to node

data

so when i'm creating a node then this

will contain a data

and this next will contain none

so let's suppose that these are the

positions let me give the position at

one two

three

four

five

six so let's suppose that at position

three

i want to insert this nb node that means

in this position

so initially if you see this linked list

this linked list is connected like this

right

nv is connected to n1 n1 is connected to

n2 n2 to n3 n3 to n4 and 4 to ne and any

is connected to none right because we

don't have any note after any and

initially my head will be pointing to my

first node that is nb

now what will happen here

so let's say at position 3 i want to

insert my node so what will happen here

so this will be my position 3 and after

that this will be my position 4 5 6 7

right

so what will happen here as we know that

our head will be always pointing to the

first note so i will create a temporary

variable a is equal to self.head

now you might have a question that why i

am creating a temporary variable a

because i will be using this temporary

variable in a loop so in a loop i will

do the iteration so a value will be

changed but i don't want to change my a

value right and a value is self dot head

because head will be fixed so that's why

i have created a temporary variable here

a is equal to self.head now what i will

do i will create a loop which look for

loop

so let's suppose that if you want to

insert this nb node at position 3 then

in a linked list you have to go through

each node right so first you have to go

to position one position two then only

you can come to position three so that's

why i'm using here for loop so i'll

write here for i in range

and then i will give the value here one

and position

then i will give the value here one and

position minus one now you might have a

diode why i am giving here position

minus one so see this is my node right

one two three

i want to insert this node at third

position so i have to traverse here from

one

and then two then only i can go to three

that's why i have written here position

minus one so let me correct here it will

be position minus one

so here you can see that my position is

three so i'll write here for

i in range

range starts from 1

and what is position minus 1 3 minus 1

will be 2 so as i know that if i'm

writing here for i in range 1 comma 2

then this 2 will be excluded so that

means for i is equal to 1 my iteration

will be done right so here what do you

mean by a equal to a dot next my a is

equal to self dot head so if i am doing

here a dot next that means my temporary

variable a is now shifting to here and

one node right a dot next is nothing but

it will contain the address of n1 node

so this will be my new a so you can see

that through iteration the a value was

moving from nb to n1 right and after n1

i want to connect this nb node right so

after this loop what i will do this is

my nb so initially my nb dot next is

none right

when you will create a node then we will

assign the data right nb dot data is

equal to data and nb dot next is equal

to none so i want to connect this nb dot

next with this n2 so i have to write a

logic so what i will write here i'll

write here nb

dot next

is equal to i will write here a dot next

because my a value is assigning to n1

right so if i'm writing a dot next then

a dot next will contain the address of

n2 right so that's why i have written

here nb dot next is equal to a dot next

so that means nb dot next will contain

the address of n2

right

and after that i have to link this node

also

so for linking this node i will write

here a dot next

is equal to what's the name of this node

nb

so if you see here what will happen here

let me remove this

so this connection

so when i'm writing here nb dot next is

equal to a dot next so this is my nb dot

next so nb dot next will be connecting

to this n2

right

and here i've written a dot next is

equal to nb so a dot next will connect

here

right so in this way we can insert a

node at any specified position now let's

see the coding example so that we can

understand in a better way

yeah so this was our program and here we

have already done the insertion at

beginning and insertion at end so once

again i will create a function and for

creating a function i will write def and

then function name let's suppose i will

write here

insert at specified node

i'm writing this large name so that you

can understand easily

or else you can also give the sorter

name too

so insert add specified node so first

alright yourself and what are the

parameter i have to pass here i have to

give the position for this

and then data

so if i want to insert a node at any

specified position then again i have to

create the nodes so i will create here

nib

so node in between i've given the name

an ib shortcut

so i'll write here

node

and then data

so i've created my node in which

node.data is equal to data and then node

dot next is equal to none so i will give

the data value then data value will be

assigned here

so what will happen here after that once

again i will create a temporary variable

a is equal to self dot head

and then i will create a loop for i in

range

one comma

position minus one

and after this

i will write here a is equal to a dot

next

this is a logic for traversing through

each node so if i'm giving here position

3 then i will go through the n1 node

then n2 node then only i can reach to

the n3 node right

so

after traversing from the n1 node n2

node i'm having n3 node so i have to

connect it right so how to connect that

n3 node so for connection i will write

here niv dot

next

is equal to

a dot next

so that means at position three five

created an ib node so nb node was there

and one node was there and ib node is

there so that means i am connecting an

ib dot next is equal to n2

right now

what i will do i have to connect an ib

node with n1 also so i'll write here

logic a dot next

is equal to nib

so a dot next is what my ember node

which will contain the address of niv

node so this is my logic now if i want

to call this function

let me again

copy and paste this

was the name of the function insert at

insert at specified node

so i will write here insert at specified

node

and then i have given here position and

then data so i will here pass the

position at three position

i want to insert a node

and let's say data is seven

and once again i am calling it through

sll dot reversal

so if i'm executing it then you can see

that i am getting the output so for

getting the output in the next line let

me write here print

so you can clearly see in the output

that at position 3 a new node has been

inserted whose data is 7 so now let's

understand the logic

so the logic is simple here here my

position was 3 right

so let me write here position 3 and my

data was seven

so when i'm creating here nib is equal

to node data so what will happen here

once again

here

and ib

dot data

will be equal to 7

and here

and ib dot next

is equal to none

so after creating the node

here a is equal to self dot head

so a is equal to self dot head so

instead of self my sll will be there

right

here you can see that i am passing sll

so instead of self sll will be passed

so sll.head is what sll.head is nothing

but is nb

so sll dot head is equal to nb

so my head is pointing to the first node

that is nb

now coming to the loop logic here you

can see that position is 3 so 3 minus 1

will be 2 so if i in range 1 comma 2 is

there then for i is equal to 1 only this

loop will run

so i is equal to 1 here

what will be the a dot next

a is equal to a dot next so what is my a

here a is nothing but nb so nb dot next

right so nb dot next is what

nb dot next is nothing but its n1

so here if i am writing here

nib

dot next

is equal to a dot next so what is my a

dot next a dot next is n1 dot next

so you can clearly see that an ib dot

next is n1 dot next and what is n1 dot

next n1 dot next is nothing but n2

right so you can see that i have created

the node and initially and an ib dot

next was none but here

an ib dot next is n2 so that means the

node i've created at a specified

position i've connected to the n2 node

now after this

once again a dot next

so what will be a dot next

a dot next is equal to nib

and what was my a was my n1 right so n1

dot next will be an ib

it's simple so what is my a dot next a

dot next is n1 dot next and now here you

can see that i am assigning an ib into a

dot next so here n1 dot next is equal to

nib that means an ib is assigned to

n1.net so here you can see that with

these two logic the node i have created

that is an ib node i have done the

connection with n1 and n2 so this is the

basic program

of insertion in single linked list

so now after seeing the insertion

operation now let's jump into the

deletion operation so even deletion

operation will be of three types we will

see the deletion at beginning deletion

at end and we can also delete a

particular node at any specified

position so now let's see deletion at

beginning so

i was having a node here

nb

and then i was having n1 and at position

3 i've inserted a new node right nib

then i was having a n2

n3

and n4

and at last i was having any node

so if you see now i'm having a total

seven node one two three four five six

seven right so now nb is connected to n1

n1 is connected to nib so what does that

mean that nv is connected to n1 so that

means the link or you can say the

reference of nb will contain the address

of n1 similarly nib is connected to n2

n2 to n3 and 32 n4 and 4 to n e so the

link of any will be none because it is

not connected to any other node so

initially my head will be pointing to

right

and let me write the data here so nb i

was having a data 2 and when i was

having five and i be seven end to 10

15 20 and 25

now in deletion what i have to do i have

to delete the first node at the

beginning so what will be the logic if i

want to delete this node then my head

will shift here right so let me create

the logic so initially what i will do

i'll write here a is equal to self dot

head

so i have created a temporary variable a

and inside that i have assigned self dot

head now after creating a temporary

variable a is equal to self dot head

what will happen here

since i will delete this node so i want

that my head must be pointing to n1

right so what will the logic so i'll

write here self.head and i will assign

here a dot next

so my a is equal to self dot head right

this is my a initially so a dot next

will be n1 right so i've written here

self.head is equal to a dot next that

means self.head is equal to n1 so now my

head will be shift from nb to n1 so let

me remove this head

so my head will be here

so this is my head now

since i want to delete this nb node so

since i have to delete this nv node so i

want to disconnect this link from nb to

n1 so how to disconnect this link so

what i will write here i will write here

a dot next is equal to none

so this is my a so if i am writing here

a dot next is equal to none that means

that nb is not connected to n1 right so

let me remove this link

so i will remove this link so once this

link has been removed that means this

node has been deleted so this is the

basic simple program

for the deletion at the beginning

initially you have to create a temporary

variable in which you are assigning self

dot head now i will change myself dot

head so i'll write here self dot head is

equal to a dot next and then i have to

disconnect the link so for that i will

write a dot next is equal to none that

means nb dot next is none so a dot next

is equal to none means it doesn't

contain the address of the next node

so now let's see the coding example

so this was my coding part so i will

create a function so

i'll write here def and let me write the

function name deletion at the beginning

deletion

at

beginning

and inside that i will write yourself

so what will be the logic so first i

will create a temporary variable i will

write here a is equal to self dot head

as we know that we gonna delete the

first node so my head will be changed so

i'll write here self dot head

is equal to

a dot next

so that means now my head will be

changed now after that i have to

disconnect the link so for that i will

write here a dot next

is equal to none

and let me call this function

so i will copy this thing

ctrl c

and let me

ctrl b

and then i will also copy this

so deletion at beginning is the function

name so how to call a function i will

write here sl

so this is the object of a class

sll.deletion

at the beginning

and now if i am running it

then you can see that i am getting the

output but let me right here once again

print

so that i can see

the output in the next line

so now you can see that the new singly

linked list is from 5 7 10 15 20 25 so

that means my nb note that i was created

has been deleted right so this is the

basic logic for deletion at the

beginning

so we have seen the deletion at the

beginning now we will see the deletion

at end so

let me first create my linked list so we

have done the deletion at beginning so

now my new single english will start

from n1 so my single english will start

from n1 then nib

then i was having n2

then n3

n4

and then at last i was having any so n1

i was having the value as

5

and ib i was having the value as 7

here 10

15

20 and then 25

and

any dot next was none so let me connect

all these nodes

so now as we know that head will be

always pointing to this n1

so this is my singly linked list now

what will happen here i want to delete

this node so how to delete this node so

in a linked list if you want to delete

any node then you have to go through

each node you can't directly jump to the

last node so once again i have to go

from n1 and ib n2 n3 n4 and at last any

then only i can delete it so now let's

see the logic here

so now coming to the logic here

you can see that i have created here two

variable now you might have a doubt that

why i have created two variable i will

tell you the logic so here i've written

here previous is equal to self.head

so previous is nothing but it is

assigning to n1 and this is my head so

i'll write here previous

and i have created here a is equal to

self

dot head

dot next

so what is a equal to self.head.next

self.head is nothing but its previous

right and previous dot next is an ib so

this is my a

now what i will do i will create a loop

and right here inside this loop while

a dot next

is not none

then i will write here a is equal to a

dot next

and previous equal to previous dot

next now you will see the logic here so

is a dot next this is my a dot next is

it none no it's not then a dot next

contains the address of n2 so what will

happen here a is equal to a dot next and

previous equal to previous dot next so

my new a will be this and then previous

will be this

similarly once again

this is a while loop so once again a dot

next is not none so it will see oh a dot

next is not none so once again the a

will be here and then previous will be

here once again the loop will run it

will see a dot next is not none once

again the a value will be changed here

and the previous will be here similarly

it will see here a dot next is not none

so a will be

here at any node and here previous will

be here now it will check a dot next is

none so this while loop will be end so

here you can see that

my a is here at the last node and my

previous is at the end for node now what

i will do here i have to delete the last

node so i have to disconnect this link

right so this is my previous so if i'm

writing here previous

dot next is equal to none

so my link has been disconnected and

hence this is a deletion of the last

node and that's what we want because if

you see here any dot next is already

none and if i disconnect this link then

i've already deleted this note so this

is the basic logic so here i've done

nothing but i have just created a two

variable and then i have used the while

loop so this is the basic logic of the

deletion at the end position now let's

see the coding part of it

now what i will do here i will once

again create a function so i'll write

here def and i will write here deletion

at end

and i will write yourself

now initially i will write my previous

is equal to self.head

and then i will write here a is equal to

self dot head

dot next

then i will create a while loop so i'll

write here while

a dot next

is not none

then i will change the value so i will

write here a is equal to a dot next

and previous is equal to

previous dot next

and once i have done the traversal

through each node so what i will do here

i will write here previous

dot

next

is equal to none so if i'm writing here

previous dot next is equal to none so

that means the link was disconnected

from the last node now let me execute

this

so

let me copy and paste

and i have to call it so i'll write here

sll dot deletion at end

so this is the program and not running

so on executing you can see that i am

getting the error so why i'm getting

here because

i have to write here self

so now if i'm executing it you can see

that i'm getting the output

once again i have to write here print

so here you can see that the last node

has been deleted so if you want to

understand the logic for deletion and

end then follow the similar approach

that i have showed you earlier right so

now we will see the deletion of a

particular node at any specified

position

so after deleting the node at beginning

as well as end we will see how to delete

a node at a specified position so

the singly linked list

that i'm having as of now

looks like this

this is my n1 then after n1 i am having

niv then n2

and n3

and n4

so n1 is connected to niv that means the

link or the reference of n1 will contain

the address of nib

and ib2 n2 n2 n3 n3 to n4

so after n4 we don't have any other

nodes so n4 link will contain the

address none

so in n1 i'm having the data element as

five and ibs seven

then ten and here i'm having 15 here i'm

having 20 and if i want to delete let's

suppose n2 node so this is my position

three right so let me write the position

one two three four and five this is the

position three

so at position three i want to delete

this end to node so what i will do here

once again this is my head so as usual

this is my head so i've created a

variable previous in which i have

assigned self dot head then i have

created one more variable like the last

time a is equal to self dot head dot

next so self dot head is here previous

right so self dot head dot next will be

assigning to nib so this will be a

right so previous is equal to

self dot head

this is my head and a will be

self dot

head dot next

so now i want to delete this node so i

will be using this time for loop so i

will write here for i in range and then

one comma position minus one so let's

suppose that if i want to delete

the node at position three so what will

be happening here one

and then three minus one i will be

getting two so two will be excluded so

iteration will be done only for i is

equal to one so for i is equal to 1 a is

equal to a dot next and previous is

equal to previous dot next so what does

that mean that means simple

iteration i is equal to 1

my a value will be here now and my

previous will be here

right now

let's see this logic so i've written

here previous dot next is equal to a dot

next so this is my previous now so if

i'm writing here previous dot next

is equal to a dot next

so if you see this is the previous dot

next and this is the a dot next so that

means i am connecting previous dot next

with n3

right

and after that i have written a dot next

is equal to none so this is my a dot

next so i have disconnected this link

so you can see that this node has been

deleted so this is a basic logic just

simple i have done the iteration using

for loop and then after that i have

written previous dot next so this is the

previous dot next

which is equal to a dot next so in

previous dot next now i'm assigning the

value a dot next that is the entry value

so that means

here this link has been disconnected now

i want to disconnect this link so i'll

write here a dot next is equal to none

now let's see in the coding part

so let me create the function i will

write here def deletion

at particular node

so i will give the function name here

deletion at particular node so here

i'll give one more parameter other than

self i'll give you a position because i

want to delete a node at particular

position so i'll write here position

and inside this i'll write once again

previous is equal to self.head

and then i will write here a is equal to

self

dot head

dot next

now i will create a loop for i

in range

one comma position minus 1

and inside the slope

i'll write here a is equal to a dot next

and previous is equal to

previous dot next

now after this

what i will do here i'll write here

previous dot next

is equal to a dot next

so after writing this logic there will

be a disconnection of the link and then

i will write here a dot next

is equal to none

now let me call this function

so i will write here

let me copy and paste this

and what's the name of this function

deletion at particular node

at particular

node

and let's suppose that position 3 i want

to delete so i'll write here

3

so you will see the data element 10 will

be removed from here so now if i'm

running it

again i have to write print

to get the output in the next line

so if i'm running it you can see that

the 10 data element has been removed

because the node has been deleted so we

have seen here the insertion at

beginning and at particular node same

for the deletion and we have also seen

the traversal so this was all about

singly linked list

so now we will be seeing double english

concept

so what is the difference between singly

linked list and doubly linked list so

here let's see the node

of doubling list so in doubly linked

list

we are having two pointers so this

pointer

will contain the address of the previous

node

and the another pointer will contain the

address of next node

and here

this node will contain a data

so let me give the node name as n1 right

so this is the way to create a node in

doubly linked list now w english is a

collection of nodes in which each node

contains a data field and having two

pointers as i already explained you that

we are having two pointers and data

field

so one pointer is for previous node and

other for the next node

again the difference between singly

linked list and doubly linguist is that

in singly linked list we can traverse

only in the forward direction whereas in

doubling list we can traverse forward

direction as well as backward direction

so here

let me create the node

so these are the three nodes let's

suppose

i will give the name here n1

here as n2

here is n3

okay

so n1 and 2n3 are the node so this will

contain the address of previous node

right so do we have previous node here

no

so i will write here none

right

similarly n1 to n2 let's suppose n1

address is 1000

and 2 address is 2000

and 3 address is 3 000

so now coming to the end to node this

pointer will contain the address of

previous node so what's the address of

previous one thousand

so it will write here one thousand

now coming to the n1 node so this will

contain the address of the previous node

but we don't have any previous node here

so it will contain the address as null

or none

similarly now if we see the pointer of

this n1 node this will contain the

address of next node so here it will

contain the address

2000

similarly this will contain the address

of

next node that is 3000

similarly n3 node

this will contain the address of

previous node that is 2 000

and here do we have any node no

so as we know that this

pointer will contain the address of the

next node so we don't have any next node

present here so it will contain the

address as null

so this is a basic representation of

doubly linked list

and here we can write the data elements

let's suppose 5

10

15

and obviously my head will be always

pointing to the first node so this will

be my head

so this is the basic representation of

doubly linked list here the traversal

can be done in both the directions

now let's see the operation in doubly

linked list so like singly linked list

in doubly linked list also we are having

three operations insertion deletion and

traversal so in insertion we are having

beginning at specified note at end that

means we can insert the node at

beginning at a specified node or at the

end position similarly for the deletion

also

now coming to the traversal here we can

go to the forward direction as well as

backward direction so we have already

seen the logic of forward direction so

here i will explain you the logic of

backward direction also

now let's see the pseudo code of doubly

linked list now coming to the pseudo

code the first thing is that you have to

create a node so how to create a node of

doubly linked list so doubly link list

if i want to create a node

first i will write a class and the class

name is node then i will create init

method and we know that in a node let me

give the node name is n1 we are having

data

and two pointers

so here i will give the name as previous

and here i will give the name as next so

how to create a node i will write here

n1 and then node

and i will write here data

so my node will create here right so if

you will see here instead of self n1

will go so my n1 dot data

is equal to data

n1 dot previous

is equal to none

and my n1 dot next is equal to none

so next will assign to none here

and previous will assign here

to none so this is my initial condition

how to create a node here you can see

that self dot data is equal to data that

means n1 dot data is equal to data n1

dot previous is equal to none

so n1 dot previous is equal to none i am

getting here and then n1 dot next is

equal to none

so this is the way to create a node now

coming to how to create a class of

double english so initially when your

head is empty so we don't have any

doubly linked list because head is not

pointing to any node then it will be

empty right so here i will create a

class whose name is doubly linked list

and then i will create a init method and

then i will write self.head is equal to

none so that means my head is pointing

to none so my linked list is empty as of

now

now we will see the traversal operation

in doubly linked list

so here this is a code for the forward

traversal that we have already seen in

the singly linked list

right

so let me create the node of w link list

let's say it's a doubly linked list

this is the nbn node

this is the n2 node this is the n3 node

so here it will contain data as d1

d2

d3

then it is connected like this

it will be none

and here it will be also none

and the head will be pointing to the

end

node

now if i want to go for the forward

direction then as we know that my head

is fixed so i will create a temporary

variable a is equal to self dot head

then i will create a loop right because

i don't want to change my a value that's

why i have created a temporary variable

so when i'm using a loop here here a

value will be change right

so if you see here i have written here

while a is not none

so initially my a is assigning to here a

is equal to self dot head that means it

is assigning to n1 node now what i will

do here while a is not none so this is

my a

and a is self dot head right it is not

none then what i will do i will traverse

it so i am writing here the logic while

a is not none so what is my a a is equal

to self dot head so initially

i have assigned my head value inside a

so now what i will do i will write here

print a dot data

so it will print the value of

d1 right

now after that i have a sign here a is

equal to a dot next

so what is a dot next a dot next will

contain the address of n2 node right so

my a will shift here right and this is a

loop so this loop will run till my a is

not end then again the a value will be

go up to here so in this way whatever

the data elements are there i will write

here inside this while loop and i will

print it out so now after forward

traversal we will see the logic of

backward traversal so let me write here

backward

traversal

let me create a waiting list so this is

my doubly linked list

which will be having two pointers

let me write here the name n1 n2 and n3

so this will be pointing to none

this will contain the address of the

next node this will also contain the

address of next node

n2 will contain the address of previous

node

n3 will also contain the address of

previous node

so what does it mean that n3 will

contain the address of previous node

that means n3 this pointer

will contain the address of previous

node

now

after this p node head will be pointing

to here and we don't have any previous

node so the pointer of this n1 node will

contain the address as none

now i want to go for the backward

traversal so we know that in linked list

if you want to go to n3 node then you

have to go to n1 n2 then only you can go

to n3 right so we have to traverse

basically from n1 to n2 then only we can

get to n3

so here first what i will do once again

i will create a temporary variable a

and i will assign self dot head into

this because i don't want to change my

head value and i will be using iteration

so what i will do here while a dot next

is not none my a is equal to self dot

head right a dot next is this right a

dot next is pointing to n2 that means a

dot next will contain the address of n2

node

so here a dot next is not none that

means a is equal to a dot next so my

value will be a here similarly once

again this while loop will run a dot

next is not none right so once again a

value will be here so you can see that

we have traverse

from n1 to n2 and now n2 to n3 right

so we know that backward traversal is

possible only when we are traversing

from n1 to n2 n2 to n3 right so now what

will happen here now my a value is here

now i can do the backward traversal so

what will be the logic the logic will be

the same i will write here print

a dot data

and this time i will assign here a is

equal to a dot previous

so we know that

this pointer is my previous pointer and

this pointer is my next pointer

so this is my a value here if i'm

writing a dot previous

right then i can go backward so what i

will do i will put this condition inside

a while loop so i'll write here while a

is not none

so if you will see here a is not none

then i'm assigning a dot previous into a

since this is a while loop so once again

my a value will change from here to here

so a is equal to a dot previous and then

i will go here a is equal to a dot

previous

if you see here the condition while a is

not none so after coming here

if i'm writing here a dot previous then

it is pointing to none right so it will

end here so in this way i can do the

backward traversal so this was the logic

for backward traversal

so now let's see the program of doubly

linked list so let me write here doubly

linked list

so now what i will do here since we know

that forward traversal will be same as

in single english so i will copy the

code from single link list

so let me copy

the code up to here

and i will also copy

and i will also copy the object of class

node that is n1 n2 n3 and n4 and i have

linked here so i will copy it

okay

let me remove all this thing

so i am not writing once again code just

to save the time

because i have already explained you in

singly linked list

so

let me remove this thing also

okay so now let's see the w language so

first i want to create a node so this is

my class whose class name is node and

inside this class node i have created a

init method so

what will happen in doubly linked list i

will be having two pointers

one pointer name is next another pointer

name is previous so i will create here

one more pointer

self dot

previous

is equal to none

and inside this class of doubly linked

list once again i will create a init

method and inside this init method i

will write self dot head is equal to

none so that means initially if my head

is none then my doubly linked list is

empty

so let me remove this thing also

and here i will write forward traversal

right

so we have already seen the logic of

forward reversal right so let me copy

this

so inside this class i will create a

backward traversal function name so i'll

write here backward reversal

and here also the same thing will be

here if self.head is none then i will

write here w lingus is empty

let me change the name here also

right so initially now coming to the

else condition yeah a is equal to

self.head right initially this condition

must be there because i don't want to

change my head now i'll give a condition

while

a

dot next

is

not none

i'll write here a is equal to a dot next

so as we know that for backward

traversal first you have to go through

each node right so let's suppose if

there are n4 nodes then you have to go

from n1 to n2 n3 to n4 so this is the

logic to go at the last node and after

that we can perform the backward

traversal so here i will write instead

of a dot next i will write here a dot

previous

right

let me change the object name here

this is a doubly linked list

and then dll.head

will be is equal to n1

and then again the same thing is there

here it will be dll.traversal

so what here the name is forward

traversal and backward traversal right

so i will write here forward

and once again i will write here dll dot

backward

traversal

so now if i'm executing it

you can see that i'm getting error

why i'm getting error here because i

have to put here underscore

and underscore

but before that we have connected the

node but it's only for the forward

traversal right i have to connect the

node for the previous one also so if

here i am created n2 node let's suppose

here i have created the n2 node so after

that i will write here

n2 dot previous

is equal to n1

and after creating n3 node i will also

write you

three dot previous

is equal to

n2 now you can see that n2 will be

having two pointers right so n2 dot

previous is connected with n1 and n2 dot

next is connected with n3

now

after creating n4 i'll write here

n4 dot previous

is connected to n3

right

now if i'm executing it on executing you

can see that i am getting the output but

in the same line so let me write here

print and inside print i will not write

anything and now if i'm executing you

can see that i am getting backward

reversal through now let's understand

the logic how does this backward

reversal is working so if i'm creating a

node here

let's suppose n1 is equal to node 5

if you see here

instead of self and 1 will go and the

data that i have given to n1 node is 5

right

so instead of data i will get 5 here

so what will happen here

n1.data i will getting s5

similarly n1 dot

next i will be getting none

and then

n1 dot previous

i will getting as none

so this is my node creation right if i'm

creating an initial node then i'm having

the data s5 and the next pointer is

pointing to none and previous pointer is

also pointing to none

right and after that you can see that i

have created an object of doubly linked

list that is a small dll so what will

happen here as soon as you are creating

the object the init method inside a

class will run so here

instead of self dll will go so i will

getting here dll.head

is equal to none

so when my dll.head is equal to none

that means my doubly linked list is

empty right so what i will do here i

will assign here

dll.head is equal to n1 so now my head

is assigning to n1 right

so after this

once again i have created a node n2 you

can see that so here once again the node

n2 will be created and n2 dot data will

be is equal to 10 because i have given

the data here 10

and then i have written here n2 dot

previous is equal to n1 so after taking

the data s10 what will happen here

let me show you

n2 will be here and then

instead of data 10 will be here

and now my n2 dot data

will be is equal to

10

my n2 dot

next will be also equal to

none

because as of now i didn't connect this

node i have just created this node right

n2 dot previous will be also is equal to

none

so as soon as i have created n2 node

what i will do here

i will write here n2 dot previous is

equal to

n1 so if you see here n2 dot previous

was none but right now i will write here

n2 dot previous is equal to n1 so that

means i am connecting n1 node to n2

right

so the previous pointer of the n2 node

will be connected with n1 similarly n1

dot next is equal to n2

so initially if you see my n1 dot next

is equal to none right but my next

pointer will be connected to the n2 that

means my next pointer of n1 will contain

the address of n2 so this is the logic i

hope you understand

now i've already shown you the forward

traversal now coming to the

backward reversal what will happen here

let me show you

so initially my dll.head

will be

assigned as

n1 right initially if you see dll.head

was none but i have written here

dll.head is equal to n1 so it will be

the dll.head is equal to n1 because in

python the statement will be executed

line by line so whatever the statement

you have written here it will execute

first then it will execute then it will

execute so that's why so if you'll see

here dll.head is equal to n1 so the

value will be n1 now let's see the

condition while a dot next is not none

so what is a here so if you see a here

so a is nothing but n1 so i'll write

here n1 dot next

so is my n1 dot next is equal to none no

n1 dot next is pointing to the n2 right

because n1.next will contain the address

of the

n2 node so what will happen here

my new a value will be

a is equal to n2

so here you can see that i am going

through each node right

so what will happen here at last my a

value is equal to n4 so now n4 will go

here and n4 dot data is what if you see

here

n4

i have given the data as 20 right so

n4.data

so n4.data i will be getting as 20 so it

will print the data as 20 right and now

after that what will happen after

printing 20

here

a is equal to a dot previous so n4 dot

previous is what

and 4 dot previous is nothing but n3

here you can see that

so once again now a value is n3 so

n3.data it will print and three dot data

is 15 after printing the data of n3 it

will go a is equal to a dot previous

that is n3 dot previous if you see here

n3 dot previous it's n2

so once again it will go n2 so n2 dot

data is 10 so it will print 10

so once again a will take the value as

n2 dot previous so n2 dot previous is

nothing but n1 so while n1 is not none

it will print a dot data so n1 dot data

is

5

and after printing the data 5 if you see

a is equal to n1 dot previous what is my

n1 dot previous if you will see here

my n1 dot previous is none

so

my a value is none so this while loop

will end so it will display

me

20 15 10 and 5. so this is the basic

logic of traversal in a doubly linked

list now let's see the insertion at

doubly linked list so we will see the

insertion at beginning first so this is

my doubly linked list so doubly linked

list is having two pointers right

so let's suppose that

i'm having three nodes here n1

n2

and n3

so n1 next pointer will contain the

address of n2 node

similarly end to previous pointer will

contain the address of

and one node

the same goes for n2 and n3

and here n3 next pointer will contain

the address as none because there is no

node available after n3 similarly here

n1 previous will be none

so this is my doubly linked list

now if i want to insert a node at

beginning so let's suppose this is my

node

so how to create a node we have already

seen it so if i am writing let's suppose

here nb node at beginning and if i'm

writing a node

and inside that i am passing the

parameter data so this will contain here

a data

and

this pointer will be

nb dot next right and this pointer will

be

nb dot previous so nb dot next is equal

to none and nb dot previous is equal to

none initially now what will happen here

as we know that initially

my head will be pointing to the n1 right

because this is my doubly linked list so

if i want to insert this node then my

head will be changed right because head

will always point to the first node so

what i will do here

so let me connect this node i will keep

the name here as nb so let's suppose

this is my nb here

this is by nb and initially it is not

linked so

if it is not linked then n1 dot previous

is initially none right

now i want to link it so let's see first

what i will do i will create a temporary

variable a is equal to self dot head

and i know that my head is pointing to

n1 as of now but i want to change this

head and i want a link established

between nv and n1 so what i will do here

after creating a temporary variable a i

will assign self.head into this and now

this is my a right so my a is equal to

self.head so i will write here a dot

previous

so if i'm writing here a dot previous is

equal to nb so what is a

a is nothing but head so if i'm writing

a dot previous this is the previous

right initially previous is equal to

none so a dot previous

is equal to nb that means now this

previous will contain the address of nb

so now it it will not be none so i will

establish a link here right

now after this

i will write here nb dot next so this is

my nv

this is my next

and this is my previous

right so here if i'm writing nb dot next

is equal to a that means

again i have created a link so here you

can see that nb dot next is equal to a

that means my link has been

created so it means that nb dot next

will contain the address of my n1 node

now after this this is my head right so

once the link has been established my

head will change so for that what i will

write here i will write here self

dot head

self dot head will be equal to

nb

so this head will be changing here and

this head will come here

so you can see that now head is pointing

to nb and b dot next contains the

address of n1 n1 dot previous will

contain the address of nb

and we know that nb dot previous is

already done so this will be done right

while creating the node so this is the

basic idea about insertion of node at

beginning now let's see it in coding

example

so this is my doubly linked list and

in the double english class itself i

create a function def and i will write

here insertion

at beginning

insertion at beginning

so what i will do here i'll pass the

parameter data right

because data value will be given by

me

so after this creating function first i

have to create a node so let me write

the node name that suppose node at

starting ns

is equal to

node

and here i am giving

data and after creating a node

i will create a temporary variable a

inside that i will assign self.head

so initially myself.head is pointing to

n1 so after creating a temporary

variable a and assigning the self.head

value inside a temporary variable i will

write here

a dot previous

so what will a dot previous will give me

a dot previous will give me here an s

right

so that means i am linking the n node

with the ns node node at starting

and then i will write here ns dot next

so node that i've created right its next

pointer will assign to a

and after that i have to change the head

so i'll write here self dot head

is equal to

ns right because ns will be my first

node so head must assign to ns

now after this once again i will write

here the function name

so i will write here dll

dot insertion at beginning

and let's suppose i'm inserting a value

here too

and if i want to do the forward

traversal then i will just copy and

paste this

so on running

you can see that i am getting the output

but once again i have to write the print

to see

the output into the next line

so if you see here you can see that a

creation of new node has been done and

the data element is two now what if i

want to do the backward traversal you

will see that my logic will work for

backward traversal also

so if i'm writing here then you can see

that i can do the backward traversal

also so you can see that i can also do

the backward traversal with this logic

so this is the basic idea about

insertion at the beginning

now let's see the insertion at end so

let's suppose

this is my n1 node

this is my n2 node

and this is my n3 node

and this is the node that i will create

let me give the name as any here

so how to create a node so when i'm

writing here any is equal to node

and

i'm passing data inside this node so

what will happen here any node will be

created

and any dot next will be none

and any dot previous will be none

initially when i am creating this node i

am not linking this node to any other

node now after this let's see understand

the logic so before understanding the

logic

let me connect these nodes

so initially my n1 dot previous will be

none and n3 dot previous will be also

none

and this is my any node right i am not

connecting this any node with this

doubly linked list as of now so let's

see the logic here so initially once

again i will create a temporary variable

a and inside that i will assign

self.head

once again the same logic because i will

use this a for the iteration so i don't

want to change the head value now

i will use a while loop so i will write

here a dot next is not none so a dot

next is what this is my head right a is

equal to self dot head this is my head

so a dot next is pointing to n2 so it's

not none so this is my a dot next so a

dot next is not none right so my a is

equal to a dot next so my a will

jump here

similarly once again this is a while

loop again a dot next is not none right

because a dot next is

containing the address of n3 node so

once again this while loop will run a is

equal to a dot next so my new a will be

coming here now once again if you see a

dot next is not none but here a dot next

is none right because as of now this is

not linked with any node

so this while loop will end here

so after that what i will do here a dot

next is none my here right i will assign

any into a dot next so here instead of

none any will be connected right this is

my any right

now any now coming to the any any dot

previous is none right so what i will do

here once again i will here write any

dot previous is equal to a when i'm

writing here any dot previous is equal

to a that means any dot previous this is

the previous pointer of any so it is

connecting with n3 that means any dot

previous will contain the address of n3

node so this is the basic logic for

insertion at end now let's see the

coding example so let's see the coding

part so

here just like i have created insertion

at the beginning function once again i

will create a function

df

and i will write here insertion

at end

and i will pass the parameter here data

now what will happen here

i will create a node any is equal to

node

and i will pass data here right inside a

node

now after creating node once again i

have to create a temporary variable so i

will create temporary variable a is

equal to

self.head

now

since i have to insert at the end that

means i have to traverse through each

node right so for that i will using a

while loop so i'll write here while a

dot next

is not none

i will assign a value is equal to a dot

next

now after this once i'm traversing

through each node what i will do i have

to connect the last node so after this

how to connect the last node so i'll

write here a dot next

is equal to

n of e

right and i will also write here any dot

previous

is equal to

a so the connection has been done now

now let me execute this

so for executing

what i will do here

let me copy this

and i will paste here

and what's the name here insertion at

end

so

instead of beginning i will write here

end

and instead of two value let's suppose

at end i want to do the insertion right

so let me give the value as 25 here

if i'm executing it

then you can see that i'm getting the

output

since

i have to give the space here to get the

output in the next line so i'll use

print function

so you can see that a node has been

inserted whose data is 25 so this is the

logic for insertion at end now let's see

the insertion at any specified node so

this is my node n1

this is my node n2

and

this is my node n3

and this is my node n4

right so if you see here then

n1 dot previous will be pointing to none

and then n1 dot next will be equal to n2

similarly n2 dot previous will be equal

to n1 so in this way there will be a

connection

and here n4 dot next will be equal to

none so here i want to insert the node

so let's suppose this is the position

one

two

three

and four so what i will do here i will

insert a node at position three so my

position is equal to three

so for inserting a node at particular

position first i have to create a node

so how to create a node so i'll write

here nib is equal to node

and then i will pass

data inside this

so my node has been created this is my

node which will be having a data

and

here an ib dot previous will be equal to

none

and an ib dot next will be also equal to

none initially right

so this is my creation of node now my

head will be always

pointing to the first node so this is my

head so i write here a is equal to self

dot head

which will be pointing to n1 initially

so after this what i have to do so if i

want to insert a node at any particular

position so this is a linked list i have

to traverse right if i want to insert a

node at position three so i have to go

through position one two two then only i

can jump to two to three right so that's

why i've used a for loop here and i've

written here position minus one so

position is here 3 so 3 minus 1 will be

2 so for i in range 1 comma 2 so as we

know that in python this 2 will be

excluded that means for i is equal to 1

my value will be a is equal to a dot

next

that means iteration will be done only

for one time

so what will happen here so a dot next

is this right

so what will happen here

for i is equal to 1

my a is equal to a dot next so this will

be my a

now after this if you see here i have

written here nib dot previous is equal

to a

so this is my nib

dot previous

which is equal to none initially when i

am creating a node because i didn't link

at that time right so if you see here

i have written an ib dot previous is

equal to

a so that means i will connect this

nib.previous with this

n2 so after this i will create a

connection between the nodes so how will

we connect

so this is my node

whose name is nib

and nib.next

is

none

and an dot tvs

is also known initially right but here

if i'm writing and ib dot previous is

equal to

a

so an ib dot previous was none initially

but if i'm writing an ib dot previous is

equal to a that means what will happen

here

this link will

be like this

so the link will be

generated like this right and ib dot

previous

and ib dot previous

is equal to a so now this link has been

generated with

n2 right

so that means an ib dot previous will

contain the address of n2 node let's

suppose that address of n2 is 1000 so it

will contain the address of 1000

now coming to the next and ib dot next

is equal to a dot next so my nib.next is

equal to none right what is a dot next

my a is here right so a dot next is

nothing but it contains the address of

n3 right so if i'm writing here an ib

dot next is equal to a dot next that

means i am creating the link here

so let's suppose this n3 is containing a

address of 2000

then an ib dot next will contain address

now 2000 year

what it now after this what will happen

here if i'm writing here a dot next dot

previous so this is my a dot next so if

i'm writing here a dot next dot previous

is equal to nib so that means another

link has been generated

let me remove this

so another link will be generated from

here and it will contain the address of

this node so let's suppose the address

of this node is 1500 so this will

contain 1500 here

now if i'm writing here a dot next is

equal to nib so this is my a right a dot

next will be here so now what will

happen here if i'm writing here a dot

next is equal to nib so that means

so that means a dot next will contain

the address of nib that is 1500 so 1500

will be here so in this way you can see

that i've inserted a specified node in

doubly linked list so this is the basic

logic now let's see in the practical

example

so now we'll see the logic encoding so i

will create one more function here def

and let's say insertion

at specified node i will give the name

here

and here i will give two parameters i

will also give position because at which

particular position i want to insert the

node so i'll write here self

position

and then data

now what will happen here first i will

create a node so i'll write an ib that

means node in between

you can take any node name

so i'll write here node data

now after creating node what i will do

once again i will create a temporary

variable a is equal to self.head

so that my head value shouldn't be

changed because i don't want to change

my head value but i will use it in the

iteration

so after creating a i'll create a loop

so i'll write here for i in range

and then i will write here one

comma position minus one

and inside that i will write a is equal

to a dot next

so what does this mean so let's suppose

that if i want to insert a node at any

specified position so before that i have

to traverse through each node right so

this is the logic that i've used using

for loop so after that what i will do

here i'll write here an ib

dot previous is equal to a so i am

writing this because i want a link

connection between the nodes and after

writing this i will write here an ib dot

next

is equal to

a dot next

then i will write here a dot next

dot previous

is equal to nib

since this is a doubly linked list so we

have to connect the previous pointer

also and the next pointer also

now i will write after this a dot next

is equal to

nib so this is my connection

now once the connection has been done

let me

print it out so what's the name of this

function

insertion at specified node

so i'll write here at specie

fight

node

and let's suppose that at position 3 i

want to insert right

so at position 3 what value i want to

give let's suppose at position 3 i want

to give the value as 7 so i'll write

here 7

and i'll write here print so that i can

get the output this time

in the next line

so let me execute it

so on execution you can see that at

position three

my new node has been created fourth data

element is seven so this is the basic

logic for the instruction at different

positions in doubly linked list

so now let's see the deletion in w link

list

so my doubly linked list

let's suppose look like this

and here i'm having three nodes

n1

n2

n3

and each node will contain a data and

two pointers

so this pointer that is n1 dot previous

will be pointing to none because i don't

have any node before this right

similarly for n3.next this will be also

none

now this pointer that is n1.next

will contain the address of n2

right similarly n2.previous will contain

the address of n1 so we know all these

things and we have already discussed it

now let's see the logic if you want to

delete this node at beginning then what

will be the logic so this is my n1 and

this is my first node so head will be

assigned you so what i will write here i

will write here a is equal to self dot

head first i will create a temporary

variable a

and inside that i will assign self dot

head now what will happen here

after that i will write self dot head is

equal to a dot next i know this is my a

so a dot next i am assigning into self

dot head right so that means now my self

dot head

will be this

because i am assigning a dot next into

self dot head and my self dot head was

initially at here right but inside self

dot head i am assigning a dot next and

this is my a dot next so my new self dot

head will be here

so i will remove this

now after this i will write here a dot

next is equal to none so if i'm writing

here a dot next is equal to none

so this is my a dot next right so if i'm

writing my a dot next is equal to none

then this link will disconnect yeah so i

will remove this link

now if you see here i have written self

dot head dot previous is equal to none

so now what is my self dot head self dot

head is here right so if i am writing

here self

dot head

dot previous that means i'm talking

about this one right so self dot head

dot previous if i'm assigning here none

that means there is a disconnection

between n1 and n2

so this link will be disconnected

so let me disconnect it so once the link

has been disconnected so you can see

that this is the deletion of a n1 node

that is deletion at the beginning and

here this is my head position this is my

n2 node and

this is pointing to none

right so this is the basic logic of

deletion at the beginning now let's see

it into the coding part

so now let's start with the deletion at

the beginning so i'll write here

def and then i will write here deletion

at

beginning

and then i will write here self

i don't have to pass the parameter here

as data because i have to delete the

node right

so inside this i'll write first

a is equal to

self.head

right so here i've created a temporary

variable in which i have assigned head

right as self.head now i'll write here

self dot head

is equal to a dot next

so i'm changing my head value from the

first node to the second node because

first node i have to remove it then i

will write here a dot next

is equal to none

that means i am disconnecting the link

between nodes and then i'll write here

self

dot head

dot previous

is equal to

none

so let me execute this

i'll copy this thing

so i'll paste here and then after that i

will write here dll

dot

deletion at beginning and

after this

i'll write dll

dot

forward

traversal

and i want the output to be in the next

line so let me write before itself print

so on executing you can see that the

first node was deleted and in the first

node i was having a data element s2 so

it has already been deleted now what if

i want to do the backward traversal so

once again i can do it i'll just copy

here

and paste here

let me write here backward

and after running you can see that i am

doing my backward traversal so this is

the basic idea for the deletion at the

beginning

now after deletion at beginning we will

see the deletion at end so let me create

my doubly linked list

so let's say i'm creating a doubly

linked list of four nodes

so each node will be having two pointers

that is previous and the next so i'm

having four nodes starting from n1 n2 n3

and n4

and

let me connect

with the link

so as we know that n1 dot previous will

be none initially

and n4 dot next will be none

so here i want to delete the last node

so one thing is clear if you want to

delete the last node then you have to go

through each node so i have to create a

logic so for that i will be using a loop

now

if you want to delete the last node then

we need two variables also so i will

create here two variables

so the first variable i will create here

is previous is equal to self dot head

as we know that head will always point

to the first node so this will be my

previous variable

now i will create one more variable a is

equal to self

dot head dot

next

so self.head is this right if i'm

writing self.head.next that means

i'm coming to here

so this will be my a

right now as i told you that if i want

to delete the end node then i have to go

through the each node that means

traversing through each node so for that

i will be using a loop while loop

and i will write while a dot next is not

none

so my a is this right so a dot next is

it none no it's not none a dot next

contains the address of n3 node so it's

not none right let's suppose the address

of n3 node is one thousand so it will

contain the address 1000 here so it's

not none

so if it's not none then a is equal to a

dot next then my new a will be here

similarly previous equal to previous dot

next so my previous will come here so

once again this loop will work it will

say a dot next is not none so here a dot

next is not none right so once again

my new a will be here and the previous

will be here

now why i have created two variables you

will get to know now if you see here i

have written here previous

dot next is equal to none

this is my previous right if i am

writing here previous dot next is equal

to none that means i am disconnecting

this link right

and this is my a here right so if i am

writing here a dot previous is equal to

none

once again the link has been

disconnected that means this node has

been deleted so this is the basic logic

of deletion at end in doubly linked list

so let's see the coding part so once

again i will create a here function and

i will write here function name deletion

at

end

and

after this what i will do let me write

print here first so that i can get the

output in the next line now i will

create two variable here

first let me create the variable as head

so i'll write here previous is equal to

self.head

and then i locate a is equal to

self

dot head

dot next

now what i will do since i have to

delete the last node then i have to go

through the each node so i'll create a

while loop here and i will write while a

dot next

is

not none

i'll assign a is equal to a dot next

and i will also write previous

is equal to previous dot

next

after this once the loop is over what i

will do my previous dot next is none if

i'm writing here

that means the link has been

disconnected now if i'm writing a dot

previous that means the last node if i'm

writing a dot previous

is equal to none

then my the node has been deleted now if

i want to execute it

then

let me execute this

i will copy this

ctrl c

and then ctrl v

and here i will write instead of

beginning i'll write here deletion at

end

let me check the function name is it

correct yeah now if i'm executing it so

on executing if you see that i was

having earlier six nodes but now i am

having 5 node and this 25 data element

has been deleted why because if node has

been deleted then data also inside that

node will be deleted now here once again

i have done the backward traversal

so

so while backward traversal i am getting

the data values from the last that is 20

15 10 7 and 5 so this is the logic for

deletion at end now we will see the

logic if you want to delete any

specified node then how can you delete

so after seeing the deletion at

beginning as well as end we will see the

relation of a node at a specified

position so let me create here a doubly

linked list

n1

this is n2

this is

n3 and this is n4

so we know that each node is having two

pointers that is previous as well as

next

so let's suppose 1000 is the address of

this node 2000 of n2

and for n3 i'm having 3000 address

4000 is the address of n4 node so we

know that n3 dot next will contain the

address of n4 that is 4000 right

similarly n4 dot previous it will

contain the address of n3 node that is

3000

that's already understandable

none so n4.next will be none and n1 dot

previous will be also none

so like the previous case we have seen

deletion at end

here also we will take two variables the

first variable name is

a and another variable here name will be

b so what i will do here this will be my

b which is nothing but a head self dot

head

right and my a will be self

dot head

dot next

so what is self dot head dot next self

dot head dot next is nothing but this

one right so that means this is my

a

right and this is my b so what i will do

here i will use for loop but previously

we have seen the while loop for the

deletion at the end right but why here

we are using for loop because let's see

the position this is the position one

this is the position two this is the

position three and this is the position

four so if i want to delete the node at

third position right

so i will write here for i in range

and this will be one comma position

minus one

so my position is three three minus one

will be two so here i will getting one

comma two so as we know that in python

if one comma two is there then two will

be excluded that means for i is equal to

1

my loop will run a is equal to a dot

next and b is equal to b dot next so a

is here right so a dot next is nothing

but a dot next will contain the address

of 3000 right

so this will be my a

similarly b dot next is nothing

it will contain the address of

and to know that is 2 000 so this will

be my b

so for i is equal to 1

my a will be here my b will be here

right now what's the point of doing the

iteration here

if you see here i have written b dot

next

is equal to a dot next

b dot next is this right and inside b

dot next i am assigning a dot next and

this is my a dot next

right so what i will do so i will remove

this

and i will connect this b dot next

with

a dot next so there is a connection

after that i have written here a dot

next

dot previous

is equal to b so what will happen so a

dot next is this right so i'm coming

here now if i'm writing a dot next dot

previous so i am going backward so if i

am writing a dot next dot previous and

in that if i am assigning b then you

will see so this will be removed

and this will be connected to here

right to n2 node now what will happen

here after this if i'm writing here a

dot next

is equal to none

so this is my a dot next right so if i'm

writing a dot next is equal to none that

means inside a dot next i'm assigning

none so this link will be disconnected

so i will erase this link similarly if

i'm writing here a dot previous is equal

to none this is a a dot previous is this

right

so i will remove this so here you can

see that this is a deletion of a node at

the position three so this is the basic

idea about deletion now we will see the

concept in coding

so now we will see the deletion at any

particular node so what i will write

here i will create a function and i will

write function name deletion

at

particular node

and i will give here a parameter as

position because i want to delete a node

at particular position

so now what i will do here once again i

will write here print so that i can get

the output in the next line after that i

will create a variable let's suppose

here i'm creating a variable a is equal

to self

dot head

dot next

then i'm creating a variable b which is

equal to self

dot

head

so if i'm creating a variable a so that

means i'm assigning self dot head dot

next into the variable a similarly if

i'm creating a variable b so that means

i'm assigning self.head into this now

after creating this i'll create a loop

so i'll write here for

i in range

and then i will write here one comma

position minus one

and after this what i will do i will

write here a is equal to a dot next

and my b is equal to b dot next

now

i'll write here b

dot

next

is equal to a

dot

next after that i will write a dot next

dot previous

and in which i will assign here b

then i will write here a dot next

is equal to none

and then i will write here a dot

previous

is equal to none

and now

i will call this function with function

name

so let me write here dll dot

i will paste this function so let's

suppose that if i want to delete at

position three right so i'll write here

position three so we'll see that this

node will be deleted and the data

elements will be also deleted so my new

doubly linked list will be 5 7 15 20. so

now let me call here

so for calling it i will copy this

dll.forward traversal let me copy and

paste here

and now if i'm running it you can see

that

i am getting 5 7 15 20 this 10 has been

deleted similarly if you want it for the

backward traversal you can do it

i will just copy this

and then i will paste

so you can see that

we are getting the node value from

backward so this was the logic of

deletion so next we will see what is

circular linked list

so circular linked list is a linked list

where last node contains the address of

first node so let's suppose this is a n1

node this is the endo node this is the

n3 node right this will contain a data

10 let's suppose and this will contain

20 this is 30

and

let me give the address here so let's

suppose the address of this node is 1000

here is 2 000 and then here is 3000

so we know that n1 will contain the

address of end to node that is 2000 here

similarly n2 will contain the address of

n3

that is

3000

now this is the last node n3 is the last

node now this will contain the address

of first node what is the address of

first node 1000

so this is a basic idea of circular

linked list now circular linked list can

be of two types

let me write here circular

linked list

so in circular linked list i can have

singly

circular linked list

and then i can have also doubly

circular

linked list

now we have seen the operations like

insertion deletion as well as traversal

in singly linked list the same will go

for singly circular linked list

similarly the same goes for doubly

circular linked list so at insertion we

have seen that we have done the

insertion at beginning then we have done

the insertion at end then we have done

the insertion and specified node so the

same goes for the singly circular linked

list as well as for doubly circular

linked list right so this was all about

circular linked list now let's talk

about the advantages and disadvantages

of linked lists first let's talk about

the advantages so obviously as compared

to array

right when we talked about arrays they

were fixed

in size right we need to specify the

size in the subscript so fixed in size

which is not in the case of arrays it is

dynamic in nature and you can add as

many nodes as you want depending upon

your requirement right so obviously when

you have that

uh

independency over the size

you will never there's no chance of

wasting any memory right so if you

require four nodes you will use four

nodes if you require three nodes you

will require you will add three nodes

only so in this way the size of the

linked list is entirely dependent upon

your application what are the things

that you require you make them that's it

so you will not be wasting your memory

and you will be

utilizing your memory very efficiently

so this is the reason why this is

written over here the efficient memory

allocation how you are doing efficient

memory allocation let's suppose you have

chunks of memory available here and

there you can link them together and

allocate

the memory and use that use those uh

memory location for storing the data

right so memory can be used efficiently

memory is not wasted it is dynamic in

size and it is very easy to insert and

delete

a

node in a linked list just by

manipulating a single link as we have

seen earlier just if you want to delete

this you just manipulate this link and

just point this link to the next node

which is after this node that's it you

are done with the deletion operation

just by manipulating a single link

similarly when you're talking about

insertion at that point you just you if

you want to insert at this location you

remove this link point it to this and

then remove and point this new node to

this

node that is there that was already

there again we are manipulating a single

link okay just a manipulation of single

link here that is required for insertion

and a single link here that is required

for deletion

now when we talk about disadvantages one

of the major disadvantage is that you

cannot lose your head right the head

node that is pointing always to the

first node either in the singly linked

list or a doubly linked list or a

circular linked list this head node

cannot be lost if this head node is lost

or if it is manipulated right if the

head node is lost or manipulated the

whole linked list will be lost right

let's suppose this is your linked list

and

somehow right if this is the head node

and somehow you

you made it travels to this particular

point right now here node is pointing to

this in a singly linked list now there

is no way you can access these nodes and

you will get undesired results another

disadvantage is that you cannot access

randomly so random access is not

possible because

if you want to go at this particular

node you can you have to traverse

through the first three nodes first why

because this node nodes the address of

this node this node knows the address of

this node this node knows the address of

this node there is no way you can

directly go to this particular node

random access that was there in the

arrays with the help of indexing you can

randomly access the elements that is not

possible in terms of linked list and the

address of the first node is

known to the

head of the linked list or the root of

the linked list okay

so that head is pointing to this first

so you cannot

change or manipulate or loss or you

cannot lose your head because the whole

linked list will be lost okay and the

random access is not possible in linked

list

binary tree now let's talk about what is

binary tree so it is a hierarchical data

structure as we have seen in earlier

data structures like arrays linked lists

stacks and queues all of these data

structures were linear data structures

but when you talk about tree

it is a hierarchical data structure that

means it can have one or more than one

children's doesn't have to be explicitly

two children

but when you talk about binary tree

therein you can have

at most two children that means

if this is the node and then it can have

at most two children's or if this is a

node it can have either left child or

the right child or it can have

no children's at all okay so this is a

binary tree and now this is known as the

root of the tree that means the first

node is known as the root of the tree

and you cannot access elements or these

nodes directly okay

so

now uh this is the structure whole

structure of a binary tree now there are

some common traversals right how we can

traverse through all these nodes so one

of the common traversal is preorder

wherein you always whenever you are on

this note you always print this node

first what is the value of this node

then you go on to the left side and do

the same

then again you go on to the left side

then do the same print go on the left

side print go on the left side and so on

unless and until there is no left then

what you do is print that

thing okay

then after that you will go on right

side

so pre-order follows print first then go

on to the left then go on to the right

similarly post thread post is saying

that whatever is you

have print it at the last so go on the

left go on the right print at last and

in order to say

left print and right so these are all

traversals we will also see one by one

how we can implement it and how we will

also see examples based on these

traversals

now let's talk about the applications it

if you have seen the find hierarchy

system wherein

we have different we have the root

folder and inside that root folder we

have subfolders like

music

and we have bin

we have files we have program files and

all those things right so it is a it is

a kind of a hierarchical data structures

right and explicitly here we are not

talking about binary tree but generalize

now if you have binary tree it has

multiple variations right if you talk

about this binary tree so here you

always have either or the left child or

the right child when you talk about bst

the childs are

inserted in the tree in such a way that

on the left side it will be always

less than the root and on the right side

it will be always greater than the root

so this is a variation it is known as

bst so you have av entry wherein you

don't exceed the height more than two so

that is one more variation then we have

red black trees so these are all

variations of binary tree

so after knowing what is binary tree in

theoretical part let's quickly implement

the binary tree in practicality on

google collab in python

so before doing that process so let's

learn what are the different functions

we are going to perform in a binary tree

concept it's generally by default

everyone will start learning with

inorder traversal pre-order traversal

and post order traffic so i'll quickly

brief you what is in order pre-order and

post order and then we shall go to

implementation part right so

let me give you a brief explanation over

this

first we'll start with what is binary

tree right i'm taking a simple example

not nothing related to coding or

anything just a simple example so binary

tree in the sense it should have at

least one node and two different

sub nodes i call it as left and right

side right it should have one data item

i am putting it to 1 here and it should

also have left child and it should have

the right child

so again i'm trying to put 2 here

i'm putting 3 here

and extending with four so we'll be

working on understanding with this

simple example how does

binary tree will work so the first thing

you have to know

i'm talking about in order

so what is in order here there is a

simple basic rule that you can remember

when you traverse throughout the nodes

which you have in a binary tree you have

to start from the left

visit root and then right

so i'm writing it here for you so left

first root next and then the right node

right side node

okay

then

we have the next one pre-order how does

this pre-order will work it has the same

rule but in a shuffled manner first you

are visiting the root

then you are visiting

left side of the

tree and then you are going towards the

right side hope that's clear right and

the last one which is left is post order

so what is post order again you have a

shuffled way of this three combination

only the first thing is it will go to

left

that means left side of the

particular

diagram or the binary tree which you

have taken and then it will go to the

right after that it will go to root

so this is the basic

things you have to know on

these three functions or operations

which you do it generally in binary tree

so in order pre-order and post order so

let's quickly start with in order right

so in order

it says we have to visit to the left

first then go towards the root and then

come back to right so i'm implementing

the same so here what is the left most

node we have for this particular example

simple example we have taken so that is

4 if you could see right so this is the

most and this is the right most and this

is the root just for reference

right

so at the left what do you have

for so for in order i'm writing it here

as well

so in order you will put up

4 as the first element because the rule

says you have to go towards the left of

the binary tree then after 4 what do you

have

this direction

you have 2 you have to first complete

the

left side part then you have to go to

the root and next

on the way what do you find you find

root so what is the number in the root

is one and then after coming back

towards right side so what is the number

we have we have 3

so

this is how in order will work so hope

that's clear we are starting from left

we are going towards the root and we are

coming back

towards the right side

so again

how do you do it for pre-order the next

one

so what does preorder say you have to

first visit root then go to the left and

then go to right

so

i'm going to root here in the same

diagram i'm drawing one more here for

your reference so this is 2 again this

will be 4 and this is 3. hope that's

clear so we are working for pre-order

here

it says we have to go for root first so

what is the element the node that is

1

okay so next it says you have to go

towards the left so what is there in the

left

you the side you have two first and then

four so what i'm writing it's two here

and four next

then

you have to visit right side so

at writing you have three

so this is how pre-order traversal will

work in binary tree

so quickly we shall see the last one

that is post order

right

post order as per the rules what does it

say we have to go towards the left first

then right and then root at the last so

writing down a simple diagram again here

for

avoiding the confusion

for

this is 3 okay so we are doing that

left side what do you have now we have 4

again continuing

you have

towards the right side

3

right after having 3 what do you have

you have to go to root so what does it

say

you have to first complete whatever

there in the left so what we have left

out here we have left the two because it

is also on the left side so what we'll

do here right we'll try to put up this

two here finish it off that is four two

three and then you have to go to one so

first what did i do i went to the left

path that is four so

after that

you have two and then you have to go to

right and then root

so

this is the root we can't go there until

unless we finish towards the right side

towards the right we had 3 and then we

went to root back so that makes 4

2 3 1 as a post order hope this was

clear for you and now let's quickly hop

into the coding part and check out the

same elements the same functions how

does that work

so what is happening here is the same

example i've taken in a coding format

that is where i'm taking the four

different notes that is one two three

four and applying all the three

functions we have that is inorder post

order and pre-order with the same

way of working but in a coding manner so

what has happened here the first if you

could see they have put up a class that

is node right so

after creating a class node we have to

initialize the values value is v l is

nothing but root right and left so we

have to have one single root node and we

have to have left and right for the same

root so then we will create some

functions for

traversing towards pre-order traverse it

towards inorder traverse it towards post

order to make it clear and precise

enough i have kept related name to the

functions and classes here

so what happens here is we'll be using

the functions called preorder post order

and

in order so

first it will visit the nodes

accordingly as i told you so first for

pre-order it will go to root left right

and for in order it will go for left

root right and again for post order it

will go for left

right and root so let's check out how

does this program work in the manner so

here you could see i've used the left

and right accordingly so as per the

rules i've told you that has been used

here as well so let me quickly run the

program for you and check out what is

the output we get

right if you could see here pre-order we

got it as one two four three the reason

is because it is going from root left

and right and for in order we are going

with left root and right so left side we

had 4 2 and again

1 was the root node and 3 was at the

right so left root and right if you go

for post order traversal then it will

start from left right and root so left

most was 4 2 and it went to right right

side was 3 and root is 1 so this is how

the traversal will work in binary tree

in python now let's talk about advantage

and disadvantage of binary tree if you

talk about advantages we can represent

data with some relationship right so

this is the root node or this is the

parent node and this is the child node

so that relationship parent chat

relationship is always there and while

you are inserting or searching an

element or a node in a

by imagery it is much more efficient as

compared to other data structures which

we have seen

now if you talk about disadvantage if

you want to sort this binary tree it is

much more difficult right because we can

obviously we can either go on the left

side

this can be a tree that means this is

the left skew tree or this can be the

scenario where we have all the elements

on the right side of the node so this

can be another scenario wherein we have

this right skewed binary tree so sorting

is difficult and it is not much more

much flexible right if you talk about

this binary tree we always have either

the two children or one children or no

children there is no flexibility in

terms of how you want to store it can we

store another node on the

with this root node no that is not the

case right and we don't follow any

restrictions like okay we always find

this node that is if this is a root note

we always find uh an element which is

less than this node on the left side or

on the right side that is of the greater

element so that is that flexibility is

not there

binary surgery

now what is binary search tree so binary

tree is an additional restriction right

this bst is nothing but the additional

restriction on binary tree like we have

already seen the evaluatory where at

most we can have two children's right it

can be on the left side or it can be on

the right side now what are the

restrictions on this tree so the

restrictions are that data that is let's

suppose this is five and this is these

are another two nodes now the

restriction is that if this is a root

node then you always will have the

element that is less than your root node

so you can have four three two one

on these sides but you cannot have six

on the left side similarly you can have

six seven eight nine and so on on the

right hand side you cannot have one two

three on the right hand side so these

are the two restrictions that are there

in binary search tree now if you talk

about insertion deletion and while you

are searching the element in the binary

search tree it is much more efficient as

compared to binary tree because we can

obviously when we are trying to search

for an element we can obviously let's

suppose we are searching for eight so

will it make sense to go on the left

hand side no we can easily neglect this

part similarly we can do it on the rest

of the element this is one scenario

wherein searching is much more efficient

than binary tree because in binary tree

we cannot neglect any elements or we

cannot say okay now we cannot find an

element on this portion on that portion

similarly when we are inserting now if

the element is greater than 8 so we can

easily

in this scenario right we can easily go

on the right hand side rather than

searching where we want to insert

and similarly when we are deleting a

little bit of ordering is

done

in order to get the exact same situation

wherein your root is less than

the right hand side elements and wherein

your root is greater than the left hand

side elements so that scenario is there

in the binary search tree now let's talk

about the application it is suitable for

applications which require sorted

hierarchical data let's suppose you have

some data and you want to store them in

such a way that always you want your

elements that are greater than the root

on the left on the right hand side

right you want them on the right hand

side and

for the elements which are less than

this root you want them on the right

hand side okay so that you can easily

neglect okay you can now let's suppose

not if you want don't want this scenario

where you are just dealing with the

greater than or the less than you can

have a similar kind of a situation

wherein you are saying that okay on this

side i will always have some files that

are related to coding okay let's say an

example and in this we i will always

have files which are related to

entertainment so you can do that so that

you can easily neglect these files

because these are always going to be

your coding files and these are always

going to be name what your entertainment

files so wherever you require sorting

right or you want your help you want

your data to be in such a manner that it

is easy for you to find insert and

delete

so there in your binary search tree

comes into picture after learning what

is binary search tree right we have to

implement that particular topic here in

python on google collab so before that

let's understand what are the different

function you'll see in binary search

tree so it is very basic function that

is insert

search and delete so before going to

these functions i need to let you know

that

how do you draw a binary search tree you

have a specific condition to be followed

in order to have a binary search tree so

number one you have to have the root

node should be always greater whatever

the sub nodes which is lesser than the

root node will be towards the left side

and if it is greater than the root node

it will be on the right side you have to

consider

these two conditions before writing

binary search tree right so i'll just

give you a simple example of a binary

search tree keeping these conditions in

point the first condition i told you is

the root

node should be taken into consideration

whatever the root node is for example

the root node is 10

okay anything below 10 it should come

towards the

left side of the root node anything

about 10 11 12 13 and so on it should

come towards the right side so whatever

it is greater should come here towards

the right what is lesser should come

towards the

left side so keeping this into

consideration 10 is the root note i'm

taking and anything you want to add on

right so i'm adding 5 when you're adding

lesser than the root node that should be

towards the left side and if you are

adding anything greater than to the root

node that should be towards the

right side so i'm adding 12 here then

after that what you have to do is

if you want to continue to the next

level right you have to follow the same

condition

for now just for reference 5 is the root

node anything lesser than 5

should be towards the left side anything

greater than 5 should be

towards the

right side right again if you take

7 into consideration right as a root

node anything towards the

left side will be having the lesser

value

you can keep it as six

anything towards the right side will be

having the greater value you can keep it

as eight

so

this is how

particular bst tree will work so this is

a simple example for binary search tree

so let's understand how does the

searching will happen with the help of

pseudocode and proceeding with

insert and then delete right

so let's see search operation first

so what happens in search

the first thing is

root node should be considered if

root node

is equal to null

it is not having any value

then we will be returning

null

okay

if the same thing again

number or the value or the data i'm

taking number here whatever the user

input is right if the number which is

given is equal to root the values of

root and the input number is same then

you have to return

root only okay the next condition if

number

is less than root as i told you

whatever it is less than root value the

number

should go to the left side of the tree

so what do you write and you can write

it as

return

search

i mean search will traverse towards the

left side any element you are finding

over a tree right you are finding uh for

example for number four right so in our

tree here like this anything like this

say you have different

values

here i am not writing values as of now

so the 4 is situated here so what does

it say it it goes in comparison first it

will search for root value is it equal

is it null no then it will search

whether it is lesser then the next thing

which it has to search is whether it is

greater if the number is greater than

the root value right then it has to go

to

the right side of the tree here it is

left side and it has to go to right side

if you want to search anything so that

is how a simple pseudo code presents

here how do you search an element inside

a binary search tree so the next part

which you have to keep in consideration

is

how do you insert element again the

searching follows the same manner

likewise the incision will also follow

some

similar manner so in order to insert

anything inside to bst that is binary

search tree what do you do first you

have to check for the condition again if

node is equal to is equal to null

right if node is equal to null and then

it will return whatever the data it is

as it is

if

again

whatever the data which is given right

by the user is

lesser than node

then it will go towards the left side of

it

if there's one more condition the data

or the value which is given by the

user is

greater than the node value

then what it will do it goes towards the

right side and we

insert element accordingly as per the

conditions it is satisfying right so

this is about search and incision so

coming back to deletion right

let's see how do you delete an element

from the binary search tree

deleting has three different cases to be

considered case one

okay say for example you have a tree

here

which is having certain value right

i'm just giving a simple example

this is 8 again it has to be less

whatever it is less will be here

whatever it is greater than will be here

so if you are taking this as an example

right the case one if you want to delete

nine okay

what it is the case one states that

directly

delete

need not do anything go to that node if

you want to delete nine get it back and

delete it right

case two

you have one more condition to consider

so we have to replace something

we have to replace

the

node

with

its child

we have to replace the node with this

child whatever it is there accordingly

say for example if you want to delete 8

you have to replace 8 with

9 or 6 i think you have to

use

in order method in order to find which

one you have to replace because 8 has 2

children

coming up to the third case

particularly

we have to follow in order method

right so in order traversal should be

followed and we have to check

accordingly which one to replace and

what to delete

right without replacement we cannot

delete and leave that particular node

empty so these are the three cases you

have in order to delete an element from

a binary search tree so let's quickly

see

how do you implement this particular

code on google

now let's implement the same bsd

functions in python on google collab so

the first thing which you have to do is

you have to initialize a class so i'm

initializing a class called node here

and i'm considering three different

elements one is key key is nothing but

root and left and right

for the particular tree

and next i'm considering one function

because i told you we'll be using in

order in order to delete something or

insert an element right so

inorder function will be used what is

the rules of in order it should be left

root and right side so first it has to

consider the left side then it has to go

to the root and then it has to go to the

right side of the tree and then again in

order to insert a node inside the tree

what are the different things you have

to consider you have to consider whether

it is null or is it equal to the root

node and you should also consider if the

node which you have taken or the value

which you have taken is greater than or

lesser than as well if it is greater

than it is going to the left side of the

tree if it is lesser than obviously it

is going to right side which is not

mentioned here only one particular

condition is taken that is which is

lesser than if it is lesser than and it

is going for left side if it is greater

than it is going for right side

so then you have again in order

successor define that means what happens

if you want to

replace something right you have to know

the successor of it you have to know the

child node of that particular node so in

order to find that we'll be using this

particular function and next in order to

know the left most node we'll be using

this particular function that is

current whatever the position is for the

node how it is traveling towards the

left side so current position from there

will be considering the left side of the

node if not will not if it is not having

any no towards the left side of that

particular

node right so will not consider that as

well then deleting a node is done so

what do you do deletion i just told you

you had three different types of cases

of deletion so here we are considering

uh with the help of inorder how do you

delete and node right so it will be

compared first it will be seen whether

it is

null or not null if it is not then it

will go inside the next condition

whether it is checking if the key is

that is the value root is lesser than

the

node which you have given so if it is

lesser than then deletion 2 takes place

to the left side if it is greater than

it will go towards the right side so

likewise it will follow the rules until

unless it will delete an element by

using in order so these are the

different inputs we have for it so this

is the pre generally so it starts from 9

4 2 and so on and ends with 5. so

considering the

image of what i taught you right how do

you write it considering the root node

anything towards

lesser than the root node towards the

left side anything towards greater than

the root note towards the right so this

considering this uh factor we will keep

give the input to the program so quickly

if we run this program let's check out

how does it display so in order to

traversal how it happens it will go from

2 to 4 again 5 7 8 and so on up to 15.

if you want to delete something what do

you want to delete after delete 11 so

where is 11 11 is

like 11 is having a successor of 15 so

what does it do 11 eliminates in the

place of 11 15 will be there so will

replace with the help of in order method

or what is the flow of uh in order that

is

left

root and right so considering this

factor it will give you the deletion

process and replacement for that

particular deleted node as well so

that's about binary search tree

now let's talk about advantage and

disadvantage of binary tree if you talk

about advantages we can represent data

with some relationship right so this is

the root node or this is the parent node

and this is the child node so that

relationship parent chat relationship is

always there and while you are inserting

or searching an element or a node in a

binary it is much more efficient as

compared to other data structures which

we have seen

now if you talk about disadvantages if

you want to sort this binary tree it is

much more difficult right because we can

obviously we can either go on the left

side

this can be a tree that means this is

the left skew tree or this can be the

scenario where we have all the elements

on the right side of the node so this

can be another scenario where and we

have this right skewed binary tree so

sorting is difficult and it is not much

more much flexible right if you talk

about this binary tree we always have

either the two children or one children

or no children there is no flexibility

in terms of how you want to store it can

we store another node on the

with this root node no that is not the

case right and we don't follow any

restrictions like okay we always find

this node that is if this is root node

we always find uh an element which is

less than this node on the left side or

on the right side that is of the greater

element so that is that flexibility is

not there

so the next concept is graphs so graphs

are very familiar for us since uh school

days and we used to do uh any bar graph

or histograms a pie chart or something

like that but here in data structure

also we have graphs which is

mathematically oriented right it is one

of the kind of data structure so which

is always derived from the mathematics

concepts so graph is always a collection

of vertizes and edges so vertizes will

be represented with the help of v

capital v or small v and edges will be

represented with the help of capital e

or small e and it will always define the

relationship we will be having certain

connections between the edges or the

vertices or the node to node connections

so

there are different types of graphs for

different types of projects or computer

science concepts so here i'm just giving

you a simple example of a graph in order

to teach you what is vertices and what

is edges right so i'll write down a

simple graph

which is having

certain connections

right so here what you can consider

vertizes are

a

b

d

and c

so whatever the nodes you have those are

the vertices how do you count the edges

so here i have just connected it

together so it is forming a loop kind of

element so if you consider some other

graph also you can have a clarity on

edges right i am cutting down this so if

you want to know what is an edge so edge

forms between a and b

again you have an edge from

a and d

right if you want to implement that in

this graph as well you can take it as a

to b as one edge

and b to c as one more edge and c to d

as another h

right so

edges are calculated between the

connection between the two different

vertices this is the basic introduction

towards the graph data structure and

we'll be seeing implementation in python

as well

so there is a graph class and you have

to have a constructor in order to know

the edges in order to store the vertices

and you have to store the graph weight

as well so we have to allocate certain

memory in the format of list in python

for that and then we are adding edges to

the dietetic graph so i told you there

are different types of graphs it is

directed weighted graphs and it is graph

in loop so everything will be considered

but here i am considering for directed

graph

and then you have the edges where you

have sources and destination that is if

it is a and b a is a source and b is a

destination so that is how edges are

calculated it is a combination of two

different vertices so then you have a

function in order to print the

list whatever the list is then graph we

cannot draw as it is as we draw to

understand the graph but we have to put

that in a sequential order or in the

form of list so that particular

representation is taken care with the

help of print graph function and then we

have

the input so input is already given here

so the edges is being directed so zero

to one one to two and two to zero two to

one three to two and four to five and

five to four so the edges are being

connected it has been directed from

which vertex to another vertex it has

been

told here with the help of edges and

then what are the different vertices we

have we have the labeling from zero to

five that means we have six different

vertices and then we have to construct

the graph how do you construct a graph

with the help of this particular

statement that is graph is combination

of edges and the number of vertices we

have and we are finally printing the

graph and it goes like this so first it

will go from 0 to 1 and then 1 to 2 2 to

again 0 again 3 to 2

4 to 5 5 to 4 you have one more

extension here that is 2 to 1 so this is

how the

graph looks like in python

after knowing what does breadth first

search right we'll implement that

particular bfs algorithm in python as

well so before that let's quickly see

what is this algorithm all about in

general breadth first search will always

traverse the nodes which is from level 1

to level 2 to level 3 it will not leave

any single level so for example if you

have a node

right a root node followed by sub nodes

so you will traverse level wise not node

wise so for example

say you have 10 here and you have

8

9 this is

level 1 sometimes it is also called as

level 0 as well right again you have

one more level

11

this is 12

again here this is 13 and this is 14

right you have this graph and it goes

level wise this is level two or it can

also be level one if you start with zero

it comes with one if if you start with

one it will go to two so

first it will start with ten it will

finish 8 it will finish 9 again it will

come back to 11 and then 12 again here

it will come back to 3 and then 4 so

level wise it will try to

finish the

traversing in bfs algorithm so

as it is written here that is

neighboring nodes in a single level are

traversed first and then the

next node or next level will be

put up into consideration else it will

not go to the next level until unless it

is travels for

every node in that particular level so

let's quickly see how does this bfs

algorithm will work in python

so here you have

bfs graph and root so root is the main

thing where it will start traversal at

least once it will visit each and every

node according to the level wise is the

thing you have to consider so visited

how many times it is visited and where

it is visited in the queue actually you

can't define a graph as we write it as

an example so we put up with the help of

numbers you could see here zero is the

level one

again you have next level two and three

right so it will traverse all the

nodes that is one two three there are

only three nodes here that is three

vertices it will travel to all the

vertex and it will finish so let me

quickly run this program and see how

does it yeah that is how it is starts

from zero it will go to one then it will

go to two and then it will reach out 3

so it will traverse accordingly one

after the other and visits each node one

at a time so

breadth first search will visit

according to the level of the graph and

it will always have the nodes visited

before

finishing the traversal right so that's

about breadth first search in python

after learning what is depth first such

we have to implement the same algorithm

in python as well so let's quickly see

what is depth first search

before implementing the same right so

this algorithm will always traverse

between nodes towards the depth of the

tree that means first node if it is

having two three and four levels first

it will complete the levels according to

the depth wise it will not go towards

horizontal manner it will just work in

the vertical manner for example i'll

just

write a

tree

or a graph

to show you how does this work it is a

very general example

so here it has

the value 10 and again

it has two different

subtrees some nodes that is eight

and seven

so again what it will happen anything it

is there

towards the depth for example here this

manner first we will go to 10 then 7

then 6 it will backtrack and come back

to 8. so it will first always consider

the nodes which is towards the vertical

side which is towards the depth of the

particular tree or graph

so hope that was clear and let's quickly

hop into ide to see how does dfs

algorithm will work in python so here is

the program for dfs

in python so as i told you it will visit

each and every node towards the depth of

the particular graph or tree so it will

not go towards neighboring nodes or it

will not go parallely it will not

traverse it is only the vertical travels

that will happen so again you have a

starting position you have a graph which

is declared you also have to have a

count of visiting nodes so you should

not repeatedly visit that particular

vertex or the node again and again right

so visited is none as of now because

we'll be starting to visit the graph and

then

visiting nodes has been set to

0 initially then we'll start and then it

will proceed one vertex to another

vertex in horizontal manner say for

example giving graphs in coding is

different than we write it is very easy

for us to just write it down accordingly

with levels mentioning and also how was

the flow of the tree or the graph but

here you have to mention the notes right

in zero

where it is having that particular

connection from zero you have connection

to one and two again from one you have

connection to zero three and four then

two has connection to zero three has

connection to one and four has

connection to two and three that means

it is telling you the flow of the graph

how it is connected rather than

rewriting it's very pictorial and

representation which is understandable

by everyone but here you have to give it

node wise all these numbers are the

nodes or the vertices so let me quickly

run this

and check

yes it is going

towards the depth of the graph that is 0

first and then it is it is going to 2

then 1 3 and 4. so the graph is 0 1 2 3

4. so it is having the vertex which is

starting from 0 ending from 4 but the

traversal will happen from 0 to 2 then 1

then 3 and then it will go to 4. so this

is about depth first search in python

hash tables is a next concept so what is

hash table before learning that let's

see what is hashing right so hashing

plays a very important role generally in

order to compress data in order to have

a

encrypted it's not exact encryption it

is just changing the values into its

relevant keys okay so cryptology we see

so that is also there and database

indexing can also be made with the help

of hash tables so let's quickly see what

is hashing function and what is hash

table and so on right

coming up to the first point here so

what they define as hashing is a black

box that takes a key as input and

provides hash value as output i'll give

you a simple real-time example you're an

employee in an organization right so

when it is an organization there are

more than 50 people as well there are

more than 500 people as well there are

more than thousands people as well

what is the guarantee that your name is

not repeated with initial

they might be other person who is having

name exactly like you for example there

is a person called sham r okay there are

two different people or three different

people in the same name same initial

everything

so how do you define them the only key

that will

give them the unique identity is the

employee id right

you agree with me employee id is

different for different individual on

the basis of that employee key itself

people will recognize

in case if they want to do any

communication or it is necessary for any

documentation so if they use employee id

so employee id acts as a real-time

example for

keying and this is a hashing technique

for example the first person sham

r is assigned with the employee id 2. so

anywhere anytime if they ask for

employee 2 that is always sham r right

people might be confused listening to

the name but this will be clear employee

id will be clear

so

it will be

one way function generally so there is

no reverse right we are creating an

employee id for one single employee then

employee is not doing anything back to

us so it is a one-way function generally

a value is converted to its relevant

number or integers or a key that's it so

then a good hashing function has

minimalistic collision so the word

collision what is collision having

two different

numbers with same hash key is called

collision right so i'll let you know

what is collision further

so

a hash table is a data structure that

uses pair of keys and values i've

already told you every

value for example sham is a value an

employee id is a key right it is stored

in a

hash table just like database table we

also have hash table it has the key and

value pair that's it say for example it

can be represented this way so the key

is employee id

and the value is the name of the

employee so this forms a hash table so

it will also have a

hash key which is hash indexing the

indexing will also be present i'll show

you with a simple example later so

it will be always one of it its kind

that means it is having a unique key i

told you one of its kind is nothing but

unique key

which is created by hash function now

the question is what is hash function

if you can see the formula here

h of k is equal to k1 modulo m so what

is it h k represents the

function of

hash that is hash function

and there is this mathematical formula

for us in order to solve to get a hash

function to get a hash key generated

that is k1 modulo m so here m is the

size of the list i'll let you know with

an example

k1 is the value we want to store what we

want to store that is k1 and value we

want to calculate the key for is this

particular k inside the hash function so

this is a brief introduction towards

hashing and hash tables and also hash

functions let's quickly jump on to the

real time example where i can show you

how to implement this particular

formula

now let's implement hashing technique

with a simple example

so here i'm taking a

list

okay

it is having it indexes

0

1

2

and you want to store

it is a size of

3 obviously you want to store certain

values inside that right say for example

you want to store 1 2 3 okay by using

the

formula h of k

is equal to

k1 modulo m this is the standard formula

which we are using let's see how do we

calculate the

hash table contents so let's quickly

have

the first one for the value 1 you want

to store 1 comma 2 comma 3 inside this

particular list which is indexed as 0 1

2 okay so

h of 1 the value which you want to store

then you have to take the value

and then modulo by what is the total

number we have the size 3 right if you

do this modulation then you will get the

answer 1

so it says the value 1 to be stored in

index 1 right

then repeating for the value 2 right 2

modulo 3 the answer is 2 it says

2 should be stored in the index 2.

coming up to the next one right so 3

modulo 3 is equal to 0 indexing 0 the

value 3 should be stored so we have got

value 3 the index hash table index 3 and

value one as hashtag index one value two

has hashtable index two so this is how

you implement

hashing function with the help of

particular mathematical formula right so

this is the table which is formed

let's implement this particular example

in python programming with the same

concept it's very simple let's quickly

switch on to the id now

here you can find this particular

program whatever i thought as an example

is put up into a program there is no

other difference okay so first we have

creating a function that is called

hashing underscore key it is having two

different parameters that is key comma m

okay the same formula what we used has

been implemented here no change so next

written key modulo m right so modulus

operation is performed on the

value which you want to store

then the size of the hash table the size

of the hash table there in the example

was 3 here i am taking it as 8 so if you

apply that formula you will get an

answer where it is stored for let's

quickly

check the output for the same now

here you can see the hash value 4 is 4

and 3 is 3 10 is 2 12 is 4 8 is 0. so

this is how we try to give the

values and the key pairs in hashing

technique hope this was clear

algorithms

let's try to understand what is an

algorithm it is a step-by-step approach

to solve a particular problem

if there is a problem what is the things

that you are going to take care of so

the solution that you give should be

crisp right it should be exactly what is

required right if a problem is about

uh swapping two numbers you should be

able to swap two numbers and with the

most efficient approach and

when you define an algorithm or you when

you are writing an algorithm it should

be understood by a non-technical person

right there should be no such uh

language dependency

in your algorithm right so

this is what an algorithm is as a

step-by-step approach to solve a

particular problem your problem can be

complex or it can be an easy problem it

is free from programming language there

are multiple possible algorithms to

solve a given problem let's suppose i

told you to swap two numbers right now

one algorithm is wherein you can go

ahead and create one temporary variable

and then swap them

the another approach is that you're

going to use addition and subtraction

operators to solve the same

you're going to use these operators and

you can solve this problem of swapping

two numbers right which one do you think

is the efficient approach obviously here

you're using an extra variable and here

you're not using any extra variable so

this seems to be a better approach and

obviously it should be understood by a

non-technical person you should not be

using

language dependency code like you should

not use any language agnostic code right

so it should be language independent so

let's see what is an algorithm analysis

this is again a step-by-step approach to

solve a particular problem it helps us

identify which algorithm is optimal okay

this is the analysis part of algorithm

right here in let's suppose i told you

to swap it helps us to understand the

trade-off between time and space

complexity right

so there should be always you should be

able to understand the difference

between time complexity and space

complexity and depending on that you

should be able to do a trade-off as well

now when i mean trade-off you should be

able to

depict that are you going to keep your

time complexity efficient or are you

going to use your time efficiently or

are you going to save your space so

let's suppose you are given an example

right

let me give you an example

so you are giving an example you are

given an array and in that area you want

to search

an element now the first approach is

that you will go and search one by one

right you will go here you will iterate

through here and here and here you try

to search an element right let's suppose

you are searching for four

in the worst case you are traversing

a big o of n time right and in the best

case you are traversing because one time

this is the best case and this is the

worst case right so these are the two

cases

but

this code in itself whenever you are

traversing in a linear fashion is

inefficient right

and if you try if you're trying to

search for an element using different

approach let's suppose you are using a

binary search and then you are trying to

search an element obviously your time

complexity will reduce

the best case will again remain bigger

one but it will reduce to big o of

logging

now there are certain parameters or

depending on these parameters you can

define the best worst and average case

of a given problem so now there are

different types of algorithmic analysis

that those are best case average case

and worst case okay so the best case is

obviously when you are searching for an

element in an array or let's suppose 100

in size right or thousand size the best

case is that the first element that you

look if you if you're talking about what

linear search okay best

case scenario is that the element that

you're trying to search is the first

element right done this is your best

case and it requires constant amount of

time now if you talk about average case

it will be somewhere around the middle

right about 1000 divided by 2 or you can

say big o of n divided by 2 since we are

neglecting we do not take care of these

constant terms or we can negotiate or we

can neglect these

constant terms because as soon as our

input is increased right let's suppose

right now we are talking about

million uh thousand elements we are

talking about 10 billion elements at

that time dividing it by two still is

same okay not same but it is

it can be ignored because as soon as i

as we are increasing our end let's

suppose to 10 crore or more than 10

billion okay 10 100 billion is the input

size right at that time dividing by 2

still it is greater than what we can do

if we have something around log n okay

so obviously the average case is still

big o of n now when you talk about worst

case the element is found at the end or

it is not even found in the array you

are traversing

each and every element in the array and

still you were not able to find the

element so this is the worst case okay

now the worst case is always taken into

consideration because this is the

maximum resource that you require okay

when you talk about time complexity or

space complexity right

so time and space right so you always

talk about worst case scenario

right

and you always deduce your time and

space complexities based on worst case

it is computed because the analysis as

it dictates the maximum resource

requirements so worst case

helps us to find what are the maximum

risk resources that this is going to

take okay so we keep track of those

things and we allocate resources in such

manner so we always talk about worst

case now let me give you an example of

linear and binary search so in linear

search right we always talk about it and

in binary search

the space complexity of both these

algorithms is constant in worst case

right and if you talk about the best

cases of linear and binary research it

is again constant

right and it is again same okay

now when you talk about

we go off on now when you talk about the

worst case scenario right

and this is this is what helps us to

uh differentiate between binary and

linear so it's the worst case scenario

the worst case scenario for linear

searches because n wherein for binary

research is it is because of login now

now suppose there are eight inputs

you're going to traverse eight times in

it in this linear search but if you have

this log eight to the base two value

it it deduces or you can reduce it to

three into log two to the base two which

is three times so in this you are only

iterating three times in this you are

iterating eight times now as you can see

that input is very

low or very less that means there are

only eight elements as soon as our

what

our input our n or the number of

elements in the array

grows

this size of this i these iterations

become substantial and that is for the

same reason we always talk about worst

case scenario

okay

now let's talk about time complexity

it determines the total number of unit

operations to be undertaken to solve a

particular problem right let's suppose

uh let me take an example of

number of iterations like

so if you are able to search an element

in a single unit of operation then it is

termed to be a constant operation and if

you're doing the same for number of

inputs that let's suppose there are n

elements and you're traversing to find a

particular element you are traversing n

times so it's termed to be a big o of n

so to solve a particular problem you

determine the number of unit operations

now unit operation is an operation that

is independent and it can be broken down

into similar operations it is

independent of architecture it is

computed on the basis of algorithm

itself you have an algorithm in place

and based on that you compute

the time complexity of each and every

step right if there is a loop what will

happen if there's a condition what will

happen if there's a while look what will

happen

it's high priority critical in optimal

algorithm selection now depending on

this time complexity you can determine

whether you want to go with a particular

algorithm or not because let's suppose

you're trying to search in algorithm

right you can have two options right you

can use a bind research or you can use a

linear search now depending upon the

time complexity binary search works much

more faster as compared to in your

search

it works in order and and it works in

big offend so time complexity plays a

major role and there is always a

trade-off between the time and space

and in this session we will be covering

both of these things okay

so

now let's take an example and let's try

to determine the time complexity of that

particular example now let's suppose you

are given a for loop and in that for

loop you are iterating from zero to n

right

where n is i is less than n and then

you're doing the plus plus

now

you're doing some work in it okay now

since you're traversing from 0 to n now

this is a scenario wherein this will be

operated or this will work

the number of unit operations that are

present in this for loop is big of n

now similarly there is another for loop

in the same program which is operating

from 0 to n okay

and then the same thing there's a

nested for loop in it and

then what you are doing

you are traversing from 0 to

what

let's suppose this is traveled n is 8

right n is equal to add eight and in

this for loop you are traversing eight

times and in this while loop you are

traversing three times right

let's suppose you are multiplying every

every time by two okay

so now

in this for loop the nested for loop the

time complexity of the same is n log n

now why it is n log n because if you

observe carefully number of operations

that i told you is eight so outer loop

is working eight times and the inner

loop is working log 2 to the base 8 that

is 3 times so

now what is the scenario what will be

the total time complexity it will be big

of n

plus big o of n log n okay this will be

the time complexity

now since

now what is happening over here this is

the scenario wherein

what is happening it is happening m into

n that means you are multiplying big o

of n that is the nest for the nested one

okay

into big o of

log n so you are multiplying it whenever

you have a situation wherein you have a

for loop inside a for loop therein you

will multiply the time complexities

now you have a for loop outside and then

you have this nested for loop for this

nested for loop you have n into login

right

and for this you have

what we go of n

now this is a scenario wherein what

happens

m plus n

and in this you will always take

into the consideration the maximum

number of resources that are there so

that one for loop will take so in this

you're taking only n resources or this

is the

time complexity of this is n and in this

you are taking n log and so obviously

this is greater right so you always say

that the time complexity of that

particular problem will be n log n

because you are neglecting these smaller

terms as soon as our input is increased

these terms will be neglected and they

will not be

that much significant while you are

allocating resources

now what about the space complexity it

determines the total space to be

allocated in order to solve a particular

problem now whenever you are using any

extra space in the algorithm

while you are implementing it that is

termed to be as space complexity it can

be in the form of arrays that extra

array that you have used to solve a

problem or an extra linked list that you

have used to solve a problem or a stack

or a cue

right it involves memory of the computer

right you are in your involving memory

right your d you're taking something

extra right solve a particular problem

let's talk about merge sort then you

take extra memory and in worst case you

can take people an extra memory that

means the number of elements that are

present in the array you're taking the

same array

as an auxiliary memory that extra memory

right it's low priority critical in

optimal algorithm selection when you

talk about space complexity we try to

avoid any extra space we try to solve it

with minimal space right so the we don't

use any of these auxiliary memories okay

now let me take an example of a merge

sort wherein in that merge sort every

time you create a left array for the

left side and the right side every time

you create these sub arrays and then you

calculate and then then you divide them

into further further and further unless

there is no

possible division and then you start

merging them so again this is a

condition or this is a scenario wherein

you are using extra memory of big o of n

now if you talk about simpler examples

let's suppose you are trying to

change the positions of even and odd

numbers right

so let's suppose you have these indexes

right in the array and you have some

values that suppose 10 20

15

20 15

and 10. let's suppose these are the

values right now you want to use or you

want to find out the frequency of these

numbers so you will be using

another array and in that area what you

will be doing let's suppose you have you

are picking up this 10 and you are

storing it in this now you'll be

checking okay if this is already present

pick up the counter and keep track of

how many times this 10 occurred now this

will work only for when you are trying

to search

10 throughout the area i'm taking a name

example right so i'm taking this example

and i'm trying to search 10 and i'm

trying to calculate how many times it

has occurred so you place a 10 in this

array and then what you're doing you

will just

iterate through the array and then keep

a track of this uh how many times this

has occurred and keep incrementing your

counter right so now you're using an

extra space right now even if this

example is not understood let me take

another example let's suppose you're

using a recursion right

now you might be thinking okay

internally you are not using any extra

space but what happens in recursion

every time the recursion is there that

means function calling itself an

activation record is created and a stack

is used internally wherein your main

function will be there and the number of

function calls right the function

calling itself function calling itself

function calling itself will be will be

we will be pushing it on the stack and

once you have returned then we will be

popping it out right so internally you

are using an extra memory and it depends

on from program to program are you are

you using big o of n or using log in

space but internally recursion uses

extra memory so an auxiliary memory or

you can say that extra memory is used

while you are using recursion so that is

why we try to avoid

recursive problems and we

we try to solve our problems using

iteration so which is obviously that we

are not using any auxiliary memory

although it is internally but still

recursion uses extra memory and that

thing is taken into concentration now

you might be thinking okay now should we

use or should we save space or should we

use less time

should we go for time efficient com pro

algorithm or space efficient algorithm

now there is always a trade-off between

space and time

so in some problems they might ask you

to save or to write an efficient

algorithm keeping the time into

consideration that you have to you you

don't have to use extra time but in some

they might say okay you can use extra

space but time should be

efficient or in some cases they say use

as much time as you want but space

should be less

so that is also there so there is always

a trade-off between both of these things

now let's see how we can find the time

and space complexity

of any given code or algorithm

so basically here i am going to give you

some tips and tricks when it comes to

finding the time complexity of any given

code or for that matter even space

complexity for any given code so what

happens in any programming language

there are certain constructs or certain

programming uh you know concepts which

we use like for example conditional

loops

conditional statements then no looping

constructs so nested loops so how does

you know time complexity is found or uh

in this cases and also the space complex

like what is the total space being taken

while executing that particular code no

space when i talk about know how many

variable at a time resides in memory

that decides the space complexity okay

and time complexity is again the total

time taken maybe in terms of n we

calculate if suppose n is a number of

input so if n or two is a number of

inputs so for two input what's the total

time taken

for each code to run or to execute so

we'll assume there are n inputs and for

n given input how many times the you

know the particular code runs that

decides your time complexity okay so i'm

going to talk about few small tips and

tricks about finding space and time

complexity to you

starting from

uh the first aspect that is your

looping constructs okay so if i talk

about loop the very frequently used loop

is your for loop so let's see if you

know int i

is equal to zero and it goes till i uh

you know less than

n

and i plus plus and then there is some

statement here maybe uh x is equal to y

plus z

let's assume that all these you know

variables were declared before in any

programming language for that matter

okay so what will if i tell you that

okay find out the time complexity what

time this complete code is going to take

if n is the input

okay

what you will do is

okay if i assume there is no the number

of input is only one

so the for loop will run only one time

and this complete statement will run

only one time so time taken is only one

unit of time

right and what will be the space taken

the time only this variable uh you know

these two variables will be stored at a

time in the in the

memory

right so no matter you know what is the

input every time you need only two

variables at a time to be stored there

in

memory and when the sum is done that is

discarded and then only there is only

one variable then after that right so

space complexity is constant here

right only one unit of space is taken

because every time no matter how much is

the input every time that same two

variables occupies the space so space

here complexity will be of one

but time complexity will be for one

element this for loop will run only one

time so time complexity will be also one

unit of time it is going to take for two

uh no elements this for loop will run

two times

similarly for n elements this for loop

is going to run n times so this

statement will be executed how many

times n times so we can say that it

takes o of n unit of time

okay big o of n unit of time

it takes to run the code

okay now coming to the another thing is

your nested loops

okay

so guys whenever you find the small so

smaller smaller codes you can fragment

together and find out the overall time

complexity for any larger code so

talking about nested loop so nested loop

how it runs 4 is you know end suppose i

is equal to 0

i less than n

i plus plus and then inside this there

is one more for loop okay

maybe int j of 0 to j less than n

j plus plus

and then this there is a statement may

be same statement i am writing index is

equal to y plus z

and then this closes the bracket

now how many times this code will run

again space complexity is going to be of

one guys because you can see the actual

operation being done is only this and

every time it requires two unit of space

so it's constant throughout the

execution it doesn't depends on the

number of inputs so it is o of 1 the

constant time the constant space

talking about time complexity so you see

here

for each value of i

j runs from 0 to n

so if value of i is 1

or you can say value of i is 0 then this

runs from 0 to n that is n times

a value of i is 1 then also this runs

from 0 to n n times a value of i is 2

then also this runs from 0 to n for n

times similarly so on

okay

it means

if this goes from 0 to n

this will also go from

for each value of i it is going to go

from 0 to n

1 to n because it's less than not less

than equal to

or you can say 0 to n minus 1

right

it means what for i value as 0

this code runs n times

then i value of 1 this code runs n times

i value of n this code will run n into n

times

yes or no like

are you getting my point so this is

mathematical concept here so n into n

that is the time complexity for this

will be o of n square

right

now coming to the third type of a

concept if else loop conditional

statement okay so if says if

and there is some statement over here

okay then it says else and then some

statement over here suppose a time

complexity of this is o of n and time

complexity of this is o of n square

which will be the final time complexity

out of this complete fl slope

final time complexity will be whichever

part

of either if or else whichever part has

less time complexity which is taking

less time to execute if this is taking n

times to execute this thing n square

times to execute definitely n is smaller

n is lesser value than n square

so the overall time complexity for out

of this f else loop will be o of

n

is it clear

right

okay so

this is your uh these are the three

constructs now let's see if there are

sequential statements like definitely in

any given program there is not only just

for loop or just you know or nested for

loop or flow there are other statements

also along with these loops so in that

case how the time complexity or space

complexity is taken care again guys here

i am i'm not told about space complexity

in this fl slope so space complexity

again depends on what you know statement

is being over like at a given point of

time how much is the space being

occupied in memory to execute that

statement

that's does that space allotment depends

on the number of input

then what how it depends on number of

input will be your space complexity

otherwise it always remains constant

fine let's see the fourth aspects where

there are other statements also along

with these looping constructs and

conditional statements in a given

program or a code

so now the fourth condition which i am

going to see here is

that suppose there is a statement you

know x is equal to y plus z

okay then there is a for loop over here

then there is a

maybe no do while loop

so it does something and then while loop

is there

okay

then there is again maybe some statement

uh

sorry some statement here maybe is

a uh is equal to a

plus plus

fine

now

let's see from so what you'll do is

we'll start from the beginning of the

code so first code here takes how much

time is it dependent on the input no

every time it's going to be y plus z

only no matter input is 1 2 3 or

whatever so it is constant time

suppose this for loop whichever whatever

is the for loop over here this takes com

time complexity of o of n

okay then there is this do while loop

which also takes the time complexity of

o of n okay ah then there is this a is

going a plus plus statement which takes

constant time

okay then in this case what will be the

final time complexity

so the final time complexity is going to

be the summation of all that is 1 plus n

plus n plus 1

okay

and this will be your

so constants are always removed because

it doesn't play much role because

constant is going to be always taking

constant time so that's not

that doesn't affect our performance

right of the code so we'll remove those

n and n so

n plus n will be 2 of n right again this

is a constant which will be eliminated

and this will be just n

right so the total time complexity will

be o of n suppose out of this one of the

time complexity would have been of n

square

correct so

the time complexity here suppose this is

so in that case it will be 0 1 plus n

plus n square plus 1 correct so o

constants will be again removed it will

be n square plus n

right

again you see here

no compared to n square n is a smaller

value

right so our main focus should be on the

bigger values because this becomes

negligible in front of this one

so our total time complexity will be o

of n square only

getting it so that's how the time and

space complexity is calculated for any

given code

basically time complexity some tips and

tricks i gave you here which you can use

to calculate uh now simply by just

looking at the code you can make out

what is the no time complexity for that

given code

there are other methods also like master

theorem which is properly used for

finding the time and space complexity

but

that's a time taking procedure it's for

a full you know process or steps that

you have to follow but these tips and

tricks will help you quickly find out or

verify the time and space complexity of

your given code

now let's talk about searching

algorithms and the first searching

algorithm that we are going to talk

about is linear search algorithm

so what is linear search

it helps us to search an element in a

linear data structure now let's talk

about one example wherein we will be

searching some element inside the area

so let's suppose this is an array and

the elements are

10 20 30 40 and 50. now if we're trying

to search an element that is 50 inside

this array how linear search works is

that it checks each and every element

that is to be searched right that is

there in the element array right let's

talk about this example here 50 now 50

will be compared right we'll check

is this 10 equal to 50 no

is this 20 equal to 15 no

is this 50 equal to 30 is this equal to

40 is this equal to 50 yes so here we

were able to

do a linear search right we were

searching for this element inside this

area one by one we compared first with

10 then 20 then 30 and then 40 and

finally then with 50 at the end we were

able to find this element in the array

in a linear fashion now this is what is

termed as

linear search

now let's talk about linear search

algorithm since it is a very

straightforward or you can see a brute

force algorithm

right it's a brute force algorithm of

finding the element in the array so this

is how it works right we have one for

loop wherein we will be

what i trading through all the elements

that is from 0 to n and inside that what

are we doing we are looking for the item

that is that element that we want to

search right let's suppose this is 50

right this 50 will be we will check if

this 50 is equal to the element that is

ar of i right and then if that is the

case if we find out the element

in the entire area we will return its

index right that is index right that i

will we will return this i

now there might be the case as well if

we are at the end of the array and we

have exhausted the last element as well

and we were not able to find this 50

right let's suppose this is 10 20 30 and

40.

now this 50 is not present in the entire

area at that time what we are going to

return is minus 1 so we will say that

okay we will not able to find this

element whenever we are returning this

minus 1 in this area and this minus 1

indicates that we will not able to find

that element

now we shall see how to implement linear

search

in python so linear search will work

with the help of an array here so what

we are doing is we are searching one

single element in throughout an array in

sequential manner so this is how linear

search will work so here if you could

see we have array we have number which

one you have to search for and you have

the starting position variable so in

iterations array will move on and on by

searching from one place to another

place the first place to second second

to third and so on in total we have five

different elements in an array that

means four different places because

array starts from zero zero one two

three four so index is of four and the

elements are of five

so

we have to first take the key search

element and we have to compare that

particular element

to all the elements inside the array

right so if it is not matching the array

is not matching with the number you are

searching it will throw up an error

called element not found if it is found

it will show you index value where it is

which place of an array it is there so

let me quickly run the program for you

so i'm trying to search the element

1 right so the element 1 is in index

position 3 0 1 2 and 3 so x is the

variable which is used in order to find

which number it it will just act as a

key x will act as a key you can change

this and check if you want to search for

it for example it is not at all there in

the array so it will say element not

found if you want to search 2 for

example the answer should be 0 right

let's check

right so index value is 0 it is situated

in the first place of an array if you

want to search for 9 it is the last

place

so it's a 4 right so this is how the

value which you want to search

is always compared with all the elements

sequentially one after the other so for

example nine is compared with two it's

not matching then it will go to the next

one nine is compared with four it is not

matching and zero again compared with

one not matching it will go to the ninth

ninth place where it is situated right

it will compare the elements

sequentially so this is about linear

search in python now let's talk about

the time complexity of linear search

now if you observe carefully let's try

to understand this best case right

so now if you are looking for the

element and let's suppose these are the

elements in the array now let's suppose

in best case what can happen you're

looking for 10 and 10 is the first

element in the array now how many

iterations did you require did it

require to find you the 10

none right the constant time right only

one single unit operation was done and

you were able to find this 10. so this

is the best case time complexity where

the element that you're trying to find

is the first element that you search

right in this case you

you're looking for 10 and 10 is the

first element so this is your best case

now what about the average case and the

worst case now let's suppose average

cases that you were looking for an

element which is at the middle point

right let me just

zero one

two three four now

or you can put another another and

looking for sixty now in this case or

you can just skip it okay

no need to add one more

okay so now you're looking for an

element which is somewhere around

in the middle okay in this case you're

looking for

30 okay so now if you observe you are

only i trading half of the elements that

is 5 by 2 which is nothing but n by 2

since constants doesn't play in the do

not play any role when you're talking

about time complexity that is why

average k still boils down to big o of n

now whatever what happens in worst case

you're looking for an element that is 50

and which is present at the end of the

array or in the worst case you're

looking for something that is not

present in the array that is 60 let's

suppose and in that case you will still

iterate through the entire area and that

is why the worst case time complexity in

that case will be below and because you

are iterating

through the entire array and that

element was not found you are looking

for 60 and that is not present there so

you're right reading through the entire

area that is n

operations are done so that is why it

boils down to big o of n

now let's talk about the space

complexity of linear search

when we are trying to find the element

in the area that is 10 20 30 and 40 and

50. we were not using any extra memory

right we're not using any auxiliary

memory

or extra memory in order to find that

element we were just

looping around these elements one by one

and we were doing it on this particular

on the same array that we were

given right

since we are not using any auxiliary

memory that can be in the form of what a

stack

a linked list or an array or a string or

a queue we are not using these auxiliary

memories because they don't they are not

required right we are searching for an

element in this particular area that

we've given to us that was given to us

right so

the space complexity of

linear search is constant right we will

find we were able to find it in a

constant amount of space okay we are not

using any extra space

now let's try to understand binary

search algorithm

what is binary search

so binary search is one of the searching

techniques right like we saw in linear

search wherein the time complexity of

linear search was before n right we were

iterating through all the elements and

now this is a much more efficient

algorithm as compared to linear search

now again why do we need searching is

the thing that let's suppose if you have

a given set of elements and you want to

search if that element is present in

your array or not

that time

right we can use either linear search or

binary search now binary search is much

more efficient and it is used on a

sorted array or it can be used on an

array wherein some order is maintained

because based on that order we will

divide our array right it is a searching

algorithm which

is

or which follows the divide and conquer

strategy right let's suppose this is our

array and now

since it will be divided in such a way

that we can

neglect one part of it right we will be

dividing and then conquering that means

we will be then searching for our

element now let's suppose we are looking

for something that is now let's take an

example where in this array

is

written or the elements contained in

this array are in such a way that we if

we skip this part or the

left hand side will be skipped or the

right hand sides can be skipped in such

a way that they don't

affect our output so every time in

linear search our search space is

reduced unless and until we find that

element or

the array is exhausted okay so our

search space is reduced to half in every

iteration so this is what a binary

search is we look for an element in such

a way that every time we are neglecting

half portion of the array and let's take

an example when we have this entire area

so first half that means if four

elements eight if there are eight

elements four on this side four on this

side these four will be neglected then

we have two on this side two on this

side these two will be neglected then

one on this side one on this side then

this one will be neglected and tilt

unless and until we find that element or

the entire array is exhausted right so

this is how your binary search works

now let's try to understand binary

search algorithm so first we are going

to understand the iterative approach and

then we are going to understand the

recursive approach so i try to as the

name suggests we are going to use

for loops right we will start with a for

loop and it will

iterate and we will iterate unless until

the beginning is less than

the end right so because we will be

updating our both beginning in some

cases and in some cases we'll update our

end

now what happens now since we know that

in this iterative approach or in this

binary search it doesn't depend whether

we are using iterative approach or

recursive approach the logic will remain

same right so we will be having this

array and it will be in some order so

that we can neglect some part of it it

doesn't have to be sorted always we can

still apply binary search even if the

array is not sorted but still some order

is there so that we can neglect some

part of it because again keeping this

thing in mind that it follows the

paradigm of divide and conquer so now we

have this beginning and end at place and

we

we will always iterate when beginning is

less than end right

so now what happens after that now we

have this array and now what we will be

what we will

do let me take

new pointers so this is your beginning

and this is your end so this is your

beginning and this is your end now you

will be taking a new middle index right

and let's call it m and now let's name

these things 0 1 2 3 4 so you will do

what beginning plus

n divided by 2 so that some part of it

can be neglected right so it will be 2

so your mid is at this position now you

will see okay the element that i'm

looking for is

uh let's suppose is 50

and the element that i am currently at

is 30 so obviously it will be never from

this side there is no chance that we

will be able to find 50 from this side

that is the left hand side right

first we will check okay is this 30

equal to 50 no so this will never be

executed right then we'll check is my

item that is there is this 30

less than or greater than 50 if it is

greater than 50 right

if it is if the element that is

if item that is 50 is greater than 30

right which is in this case

our 50 that is the element that we are

looking for the item item is this point

is greater than 30 so there is no point

that it will be on this side so we will

skip or we will neglect this half

portion of the array so that is why our

new beginning is updated it will be new

it will be middle index plus one that is

middle index was two plus one that is

this will be our new beginning so we

have smartly skipped the half portion of

the array so now let's

drop all of these things and now let's

see what happens in the

next iteration

now we'll keep this thing in mind that

we are not looping or we are not

exceeding this limit that is beginning

should be always

less than

or it should be always less than or

equal to n okay so this this condition

should be maintained and similarly we'll

again

divide our array and then look for the

same things right first we'll look for

the element then we'll skip some part of

it so this is the iterative approach for

binary search right now let's look at

the recursive approach or recursive

algorithm for the same so again

beginning the ground rule will remain

same will always

i trade or we will always recursively

call binary search unless and until this

beginning is less than end done now what

happens we will again find middle index

that is beginning plus and

divided by 2 then we will look for the

element these three steps will remain

same even you if you're using recursive

approaches now what happens in recursive

recursion right we again call

the function again and again that is

what is recursion so in this

in this entire tutorial we will be

covering recursion as well but in the

later past part of the course here you

can get a good intuition or let me give

you a brief intuition about how

recursion works so let's suppose this is

your activation record every time when a

recursion

is there an activation record is called

so let's suppose you have these three

statements

and let's suppose in your algorithm you

have statement p1 p2 and p3

right and at p2 you are calling the

function again right you're calling this

function again so now what happens an

activation record is called he will

check okay is this statement executed

yes so one will be executed is second

executed yes so second is executed but

at second you are calling this function

again so at that time again a new

activation record is created now this

third step is left behind right now this

will be covered when we come back or

return from this function call that we

called here so let's suppose this

function was here now in here you are

returning right this function called

let's suppose this is not less than

beginning uh beginning is not less than

end so this will be some somewhat this

case is relatable right this is similar

to what we are looking for right let's

suppose there is some similar situation

wherein beginning is not less than and

at that time you will be returning from

this right now once you have returned

you will be then calling this function

again but this time around for this and

let's suppose this time around you will

you are calling this one is executed

step one is executed now again this

activation is record is called the

situation report is one and then again

this is called

right this is executed again this two is

called again a new activation record

will be created and these three three

steps the step third will be still left

for execution so now here you return

right then it will go back to this step

right

and then once you are done with this now

there are two

positions or two possible scenarios

where you can return either you are

returning from this function just like

we have executed this condition and we

return right another is that once you

are done with this entire activation

record at that time you will also return

okay so these are two scenarios now you

have executed this there is no step to

be executed it will return now this left

this was left behind this will be

executed now nothing is to be executed

it will go to the caller which was this

and finally it will go to the main

method where it we call this at the

first place this function okay so this

is how an activation record is created a

stack is maintained okay even if uh you

might be thinking we are not using any

extra space but whenever recursion is

there an extra space that is in the form

of stack that stack is maintained so you

need to keep this thing in mind while

you are playing around with space

complexity at the time when you're using

recursion okay so now with that being

said let's clear our screen and let's

see how recursion is called here so

again now recursively what we will doing

if

now we have this mid right and let's

take an example of an array

0 1 2

3 4 10 20 30 40 and 50. so middle index

will be

0 plus 4 divided by 2 that is 2 so this

is our middle index right

so this is 0 this is our beginning and

this is our end right so now we are hit

here right so we again check the 50 that

we are looking this is our item that we

are looking for okay so is 50

and this is our middle index is 30

greater than 50 no it is not in this

case so this will never be executed this

is not executed as well right

now what about this condition the else

part now what we will be doing will be

skipping since this 30 is less than

we'll be skipping this part and we will

focus on middle index plus one which is

nothing but this so this will be our new

beginning and our process will start

moving right so now again then the same

thing will happen unless and until this

condition is

false okay so this is

how your binary search works when you're

using recursion so now let's try to

understand binary search and

let's see its demonstration okay

so we are looking for 20 and this is our

array right 10 11 16 20 and 23. now this

array is sorted right

so we can apply binary research okay

since we can neglect some part of the

array based on some conditions okay so

now our beginning in the first iteration

what is happening our beginning is 0 our

end is 4 and

our middle is this element now what

we're looking for

is 16 equal to 20 no it is not

but

16 is less than 20 so we will skip this

part

in the next iteration what happens we'll

be focusing on these three elements

right that is 2

6 from we will be focusing on this part

rather if we say we'll focus on this

part

right

focus on this part okay so now in the

second iteration what will be happening

our beginning is updated now our new

beginning is this point our end will

remain at its own position now we'll

find the middle index so it will be 4

plus 3 that is 3 that is 7 right and

divided by 2 it is 3.5 right so since

this will be truncated right the

truncation will happen and the integer

that is there the middle index will be

three so this is our middle index right

so you can see middle index is three now

is this element that we're looking for

yes so we'll return the index so we

found our element at index 3 and hence

we return 3 because if you observe

carefully it is returning if the element

is found it is returning the index so

this will be returned okay

so this is how binary search works

after knowing what does binary search

will implement the same in python

quickly switching up to the ide so

the binary search has

four different elements and important

the first one is array the second one is

which is the element to search for which

is stored in x and

low and high why because

every array in order to have the binary

search will be divided into two parts

right it will

go accordingly if the key that means

whatever the element you are searching

is matching the middle element it will

exit the binary search immediately if

not it will try to proceed with the

search of that particular element in

halves of the array like it will divide

arrange sub arrays the right and left

part it will try to

see and search for that element

accordingly as per the

key element is right so mid is equal to

low plus

high minus low by 2 so this is the basic

formula which will be using in order to

split the binary array

in order to have the search

right so

if array of middle that means middle

element is

equal to equal to that means it is equal

to the key element which you are

searching then it will immediately

give you the middle element as the

searched element so if else what happens

if the middle element is lesser than x

what it will do it will go to the right

side of an array if it is greater than x

it will go to the left side of an array

right so it will try to search in half

like sub arrays

here if you could see the array that is

3 4 5 6

7 and

8 and 9 you have all these elements

inside the array what you have to search

is 4 so 4 is the second element

immediately you can see but accordingly

you have to search as per the binary

search rules what it will do it will

first

cut this particular

array into two halves by using this

formula and then it will compare the key

element which you are trying to search

with the

elements which is already present in an

array in order to find so let me quickly

run this

okay it is telling the element which you

are searching is present in index

number one that means it is having the

count of array index not on the element

so 0 1 2 3 and so on so 4 is present in

index value 1 so this is how binary

search will work in python now let's

talk about the time complexity of binary

search now in the best case now what is

the best case now let's take an array

and in that array one two three four and

five these are the elements now the best

case is that

not that if the element like we saw in

linear search that this element when we

are looking to search for this same

element at that time that was the

best case scenario for linear search

right but in this binary search the best

case scenario is when your middle index

is at the at this location and you are

looking for you are searching three

in the entire area so at that time this

will take a constant amount of time and

this is the best case time complexity in

that case okay now in average case what

happens right if you talk about this

algorithm let me just clean out my

screen

so it follows a paradigm of divide and

conquer so let's suppose you have eight

elements first in the array it will be

divided into four because these four or

either it can be on the left side or on

the right side will be neglected and

then we deal about these then we focus

on these things okay these four elements

again it will be divided into two and

two then we will then click two elements

then one and one then again there will

be one of the element can be neglected

so there are one and one so we focus on

this element so the entire operation

will be done or entire searching will be

done in three steps right now if you i

take an example and if i do a log

8 to the base 2 what should be the value

of this

obviously when i do this this can be

written as 2 raised power 3 right and

this can be written as 3 into log 2 to

the base 2 now this is 1 and now you get

the answer as 3

so this 3 and this 3

are equal that means

if i talk about the worst case time

complexity of binary search it will be

somewhere around

log and

as it although as we saw in three steps

we were able to find the element and the

log n that means log 8 is the answer of

that is also 3 so you get the point

right so the worst case type of

complexity of binary search is

log n and same goes for the average case

wherein it will be somewhere around log

n divided by 2 neglecting log n divided

by 2 neglecting the constant terms it

will be again or it boils down though

they go off logging okay

now let's talk about space complexity of

binary search now when you talk about

space complexity right we only think of

auxiliary memories or you can say that

or you can see that what any extra

memory that you guys have used since we

did not use any extra memory that can be

in the form of array or it can be in the

form of stack or it can be in the form

of queue or linked list or even strings

right since we never use these extra

memories in our implementation so the

space complexity of

binary search is big o of one that is

it takes a constant amount of space

what is insertion sort

so the question is that what is sorting

so you might be thinking why do we need

these sorting algorithms

so if i told you that you have

a bunch of students right

you have a bunch of students and they

each have their role number

they are not present in

what in a numerical order or you can say

they are not present in some order i

want that order to be maintained let's

suppose you have one to ten students in

those bunch of students and each having

roll numbers from this range

from one to ten

now some of them are absent and some of

them

are some of the role numbers have left

the school but the roll numbers are not

changed yet

now what i told you i told you please

sort them or arrange them in such a

manner so that i can easily understand

which role number is after which either

in ascending or in descending order

suppose 1 is there 2 is there then 6 is

there then 8 is there then 10 is there

so rest of the rule numbers i can easily

depict ok these are the ones which

either are not there or

are absent

so in order to do so we have these

sorting algorithms

in picture and one of those sorting

algorithms is insertion sort now it is

the simplest easiest and a brute force

sorting algorithm now what do what do

you mean by brute force brute force

means straight forward

right in a naive way it means

straightforward that means you're not

keeping into uh you're not considering

any

efficiency

or you don't cons you don't care about

time complexity or space complexity you

just straight away sort it with the most

simpler and naive approach okay in this

brute force algorithm what happens that

let's suppose let me give an example

right obviously we can sort with the

help of this insertion sort algorithm

you can obviously sort either in

ascending or in descending order right

uh let's take one example we all know

about the card game right wherein you

have a bunch of cards right suppose you

have a single card that is in your hand

right and you have bunch of cards

available on the table now you start

picking those cards one by one obviously

the one that is in your hand is sorted

because if i told you to sort a number

one obviously there is only one element

in the array or anything right in the

linked list i told you to sort it but if

you're having only one element that is

itself sorted right you don't need to

sort that similarly what happens now

this

card is in your hand right it's just

like playing cards right now you have

this one card in your hand and it is

obviously sorted now what you will do in

the next turn

you start picking up one by one from

these set of cards that are available on

the table now let's suppose this is zero

okay

i'm considering these numerical values

so that because so that you can

understand and you can just connect the

dots right so what happens you have the

zero and now you start comparing it now

we are considering the scenario where

you are trying to sort an ascending

order okay

so

now let's try to decrease these things

so that

it's easier for you to understand things

okay

so now you have these two elements right

and now we are considering the case

wherein you are trying to sort in

ascending so you check okay if 0 is less

than one yes it is now you swap them

okay

now you have zero and one now these are

the two cards that are present and both

of these are sorted so now insertion

sort works in such a manner that you

will always have two

parts right

one is the sorted part obviously which

is in your hand and one is the unsorted

part

which is

on the on this deck right so similarly

you can you will start picking uh

elements or you can start picking these

cards one by one and keep sorting them

okay now this is

one simple scenario when you can apply

what insertion sort right this is the

most simpler way one can explain or one

can understand

you this insertion sort algorithm now it

is simple right now you start picking

these elements and you keep sorting them

and the at the end when all of these

elements are exhausted you will get your

sorted array now let's try to understand

insertion sort algorithm so in this

algorithm what happens obviously now we

know that we will have two parts right

one is the sorted part and another is

the unsorted part right so

obviously the one element that is

present in your hand or the element or

the card that is in your hand and

there's only one element there right the

one element in your hand obviously that

is sorted right so

we will not consider that first element

and we will start our iteration from the

second element right now we understand

why we are doing this that we are

starting from 2 to n minus 1 or 2 to n

depending upon the array that we are

starting from either we can start from 0

index or we can start from one index

right

so

we always start from element number two

right and then what we will do we'll

just

store this value inside temporary

variable and then we'll check if that

element is less than the element that we

have in this sorted part

if that is the case then we will shift

their positions right and we will get

both now we will have two elements in

the picture that is 0 and that and both

of these will be sorted in ascending

order and then

what we will do we'll consider the rest

of the cases that is starting from three

to so on to n okay now you might be

thinking okay how does this thing happen

let me take an example and let me show

you how let's consider this array that

we have over here that is index 0 these

are all the indexes that we have and

this is our array that is 23 10 16 11

and 20. so in the first step we are

making

now we are making partitions now this is

sorted part that is the first element

and this is our unsorted part now what

we will do in the first iteration this

is our iteration number one because this

is the case wherein we will start moving

from

second index that is first index if we

consider from zero right

so

we consider it from second element and

so on to n right so now in the first

iteration what we will do we'll compare

these two values okay let me just erase

everything

so that it's easier for you guys so now

we will compare these two now obviously

10 is less than 23 what we will do will

shift their positions now this is your

slotted part and this is your unsorted

part

we will do the same thing

right so in second iteration what we

will do here comes 60 now what we will

do we compare it first with 23 okay we

know now okay 16 is less than 23 so now

what we will do we'll swap their

positions so this is 16 and this is 23

now what will happen now 16 will be

compared with 10 obviously it is not

less than 10 so it will remain as it's

at its own position that is its new

position at index one right

so this is the second iteration and

after second iteration this will be your

sorted part as you can see that i have

bolded this text right holded the

borders of these two

these two elements and bolded the same

for these three elements because this is

the sorted part that we have over here

and this is the unsorted part now what

will happen in the third iteration that

it will check for this number that was

there it is 11 so for 11 what we will do

we'll compare it with what

repeat this thing now we'll take 11 into

consideration and now we'll check it

we'll swap them then 11 is here 23 is

here we'll check them we'll swap them

16 is here 11 is here we check them so

since 10 is

less than 11 so nothing will happen so

in the third iteration what will happen

we will have 10 11 16 and 23 these are

all sorted and we are only left with one

element which is unsorted right

now in the final iteration what will

happen

that 23 now the square d will be at its

original position that is it and rest of

the elements will be sorted now since we

have exhausted all the elements

all the elements have been exhausted and

we at the final step that is in

hydration 4 we will have this area that

is sorted after learning what is

incision sort let's quickly implement

the same in python language so i'm using

google collab whether it is easy for

everybody to access google collab so

need not install anything it's right

available in the online so let's quickly

switch to that google collab ide for

python so here you can find incision

sort the name

for the file in

python extension so with that we already

have this particular program which is

easy for me to explain to you so here

so we are considering a function called

incision sort right so the function is

called whenever the data has been passed

in order to sort the elements inside the

data in ascending order right so in

order to do that we have to write a

proper function accordingly as incision

sort will work

so how does that work you have already

learned about it so in order to

implement you have to use a for loop so

for loop has

a range

so it will be always checking for the

elements inside the array one by one for

comparison with the key element right so

whenever it is finding the key element

it will

which is greater than the key element or

which is lesser than it will swap

accordingly right so we are using while

loop in order to do that same work

so we are stopping from the current

position where it has been found which

is greater or which is smaller

accordingly we'll stop it

right

so then we have the data which has been

given here so the data is present that

is 52178

so what happens in this particular data

is when it passes through this function

every element will be sorted with the

help of incision sort function which we

have written here so first it will

compare the elements and it will try to

sort in ascending order say for example

if you want to do descending order then

you have to change just one single

element that is this key should be

greater than array element that's about

it nothing else no change so after that

incision sort uh is the function is

having the data which is present here so

all these functions will be completed

then we'll be printing the final output

how do you print once the function has

completed sorting immediately it will be

stored in the variable data itself so

that particular data has been printed

after sort elements will be viewed right

so this is just a print statement sorted

array in ascending order so if you're

doing for descending you can make it a

sorted array in descending order so

let's quickly check how this output look

like

so here you have sorted array in

ascending order so that is one two five

seven eight right from smaller to the

higher number so let's quickly make a

small change here so that

it will

give us the descending order let's try

to work on it

right if you could see here

key is greater than array element then

you will be getting the descending order

that is 8 7 5 2 1. so you can change it

likewise

okay i didn't change the printing

statement so i'm just changing

descending order right

run the same

that's been declared so

this is how incision sort will work in

python and the code if you could see it

is very small and quickly it is

eliminating all the variable

initializations we make

anything and everything you just want to

have the function pass the data get it

sorted and the output is done so this is

all about incision sort in python

now let's talk about insertions or time

complexity so in the worst case when all

the elements are in

manner and we need to sort them one by

one so obviously we are talking about

first the outer loop which runs from one

to n and then the inner loop which runs

backwards and in the last first we

consider in the first iteration we only

consider the zeroth element then as we

move along it will be running from end

to

zeroth element right we will be

considering the whole n elements so in

that case the time complexity the worst

case will be order of n squares because

we have two

nested loops that is one is for loop and

inside that for loop we have that we

have that while right so this is the in

the worst case and it happens also in

the average case where some part

or the sorted part is already there and

it is let's suppose we have five four

five six seven eight and then we have

the unsorted part so half of the

elements are sorted and half of the

elements are not sorted so it will be n

square by 2 so we are not considering

the case where we talk about constants

and we are negotiating the constants and

in that case the average time complexity

will be n square right

but the most important thing that

is there in this time complexity is the

best case that means when your elements

that is 5 6 7 8 9 and 10 when the

elements in the array are already sorted

what happens in this case

if you observe the for loop that runs

from 1 to n will be always there so n is

always there the time complexity the

bigger notation

big o of n will be always there but in

this while loop wherein we've been

checking for if j is greater than and

equal to 0 and if ar of j is less than m

right in that case this will never be

executed because this ar of g will

always be

less than will always be greater than 10

why because we are talking about this

element and we are checking if this 6 is

less than 5 no it is not if the 7 is

less than 6 no is it it is not so this

condition will always be false for all

the elements so in nutshell we are just

checking these steps only once

in every iteration so that is for the

reason that the whole time complexity in

the best case will be bigger of n and

not big o of n square in the best case

okay now let's talk about insertions or

space complexity

if you have observed in algorithms and

in implementation we never talked about

any auxiliary memory right we were not

using any extra space either in the form

of array linked list stack queue

or anything right so that is for the

reason the space complexity of

insertion sort is big o of one that is

constant amount of space

now let's talk about insertion sort

analysis wherein we will be analyzing

comparisons number of swaps stable or

unstable in place or outplays

so first let's talk about number of

comparisons required

in this we will talk about two scenarios

wherein we will talk about worst case

and average case

in worst case the

number of comparisons required is n

square by two

now if you talk about average case

scenario it is n square by 4 which is

twice

as much as this right it is 2 times

if we talk about number of swaps that

are required in insertion sort

in again we will talk about two

scenarios average and worst case

in average case it is

n square by eight

and in worst case it is n square by four

these are the number of swaps required

and if you want to check those if these

statements hold or not if these

equations hold or not you can always

take an example wherein you will be

considering both the cases even as well

as odd so take an example and run

through it

now if you talk about stability of

insertion sort it is a stable algorithm

what do you mean by stable so if you

have an area which contains one three

one dash and five

in this area the relative position of

these two ones that is this one and this

one let me change the color and let me

show you the relative positions of this

one and this one will remain

intact what do you mean by this thing

that whenever you are sorting it

you can sort it in two different ways

right this is also sorted and this is

also sorted that means you can either

have one one dash three and five or you

can have one dash one and three and five

this is obviously that this this number

is repeated but this is the first number

this is this occurred here the first

time and here it is the second

occurrence now you want to keep the

relative positions intact right so both

of these are sorted right but if you

talk about stability this is known as

stable and this is unstable okay

now

insertion sort whenever you are trying

to implement insertion sort it is stable

that means the relative positions of

both these ones will be intact okay so

if someone asks you if insertion sort is

stable or not you will say yes why

because the relative positions of the

number that are of the numbers that are

repeated remains intact now what about

this in place or outplays

since we are not using any auxiliary

memory right we didn't use any stack cue

link list or array that is the reason

that whenever you are not using any

extra memory

it is supposed to be in place algorithm

so if an algorithm is sorted within the

array that was there earlier that means

you are not using any extra space that

algorithm is known as in place algorithm

which is evident now in insertion sort

as we are not using any extra memory so

insertion sort is an in place algorithm

now let's look at the example wherein we

will implement

insertion sort if you can see we have

this example over here wherein we have 6

5 3 2 8 10

9 and 11 and we have been given this k

what this key signific signifies that

the maximum

swaps or comparisons

needed for this three

either on the left side or on the right

side right

the number of

positions that it this 3 needs to

get to its original position is 3 so

this is a question that is known as

nearly sorted array or k sorted array we

do not need to sort all the elements in

the array but we are specifically

looking for those elements which are not

at its original position and if we want

to get them to their original position

the maximum comparisons or swaps that we

require is 3 so if you see this 3 the

original position of this 3 is

this

5 that means in the sorted area it will

be here similarly if you talk about this

two the number of swaps that it should

do is one two

and then it will it will be at its

original position or you can say that

one two and three so max it can go to

three positions okay so similarly

it will be the same for all the elements

so at most three okay

and at least it can be that it will have

it doesn't need to move at any location

that it will have its own original

position is like an 11 you see 11 is at

its own position in the original area as

well as in the swapped area so at most

you have three positions selection sort

algorithm

now let's talk about what is selection

sort now before we move to this sorting

algorithm let's try to understand what

is sorting so if you have a bunch of

students and out of those bunch of

students let's suppose some of them have

either left the college or school or

they are absent right now you want to

arrange the remaining students either in

ascending order or in descending order

so for that reason you might require

sorting so this is one of such sorting

algorithm parent

which helps us to sort

elements or number of students it can be

any object right so it is a simple sort

algorithm that revolves around the

comparison so now this is

different from if you talk about what if

you talk about bubble sort

insertion sort and selection sort this

sorting algorithm is

predominantly based on comparison right

the comparisons are done more as

compared to swapping

in each iteration one element gets

placed right if you think about bubble

how it work like a bubble and at the end

you had your element

fixed at its original position which was

at the end when we are trying to sort

our array in the ascending order now in

the same fashion right

in this sorting algorithm

one element that is

that can be either the largest element

or the smallest element so we are going

to put in the case wherein we will be

dealing with the smallest element in

each iteration the smallest element get

its placed fixed in the original array

that means when we sort the array

wherein this element belongs that is the

least element that is on the first index

right so this element

will have its position after one

iteration we will be choosing a minimum

index the sorting algorithm we have one

minimum index and that can be named as

minimum right since we are dealing with

the smallest element so now that minimum

element in the array

is placed at the beginning right

beginning of the array and later on we

will swap we will compare it with all

the elements and find out the minimum

and then swap it with the first index

okay similarly we are going to do for

all the rest of the elements okay

now the selection sort is basically

selecting an element that is the minimum

element in each hydration and placing it

at the appropriate position so that is

the basic logic behind what selection

saw

now let's talk about selection sort

algorithm now in this

our main objective is to find the

minimum index right so let's suppose if

we have one headache

now

in this area there is one minimum index

let's suppose that it is the first it is

at the first index right since we are

keeping in mind right i told you that

when we talked about what is selection

so what at that time i told you that we

can have two cases either you can pick

up the largest element and

fix its position at the end or you can

pick the minimum element that is the

smallest element okay so in this case we

have we will be dealing it with the

smallest element right

now this is our minimum index right this

zeroth index now this outer loop will

work from zero to n minus one now why n

minus one okay

i will tell you why because

um then what we will do the next step is

that we'll have this minimum index right

and it is pointing to z

in this case

and

our iterator that is i will start from

this position then in the nested for

loop that is again this is condition

where we have one for loop and inside

that we have another for loop that is

what you mean what do you mean by nested

for loop now since it's a comparison

algorithm what we are going to do inside

this sorting sorted part or inside this

unsorted part that is there what you can

say the rest of the elements okay so we

have this j iterator which is pointing

to i plus 1 that means we will not

compare it doesn't make sense right if i

and j are at the same position and we

are comparing them it does make sense

right so we have this j placed

at this iterator at this index right one

this j iterator is at in x one now what

we will be doing will be comparing it

because it's a comparison algorithm and

number of swaps are less that means if

there are any elements there will be

n or n minus one swaps okay

so the swapping is reduced as compared

to bubble sort okay so now what happens

we will be comparing them okay and we

will be trying to find the minimum index

let's suppose this is 3 and this is 1.

so since 3 is greater than 1 that means

our minimum index will be updated so our

now our new minimum index is what

and index is the one right this is the

minimum index okay done

now once this comparison is done right

so again we will check

if 4 is less than 1 no if 5 is less than

1 no if 6 is less than 1 no

if 0 is less than 1 yes 0 is less than 1

that means we are again comparing it

right and we are not swapping them we

will wait

once this entire iteration is done so i

will update my minimum index to 1 5

because that is the minimum index then

we have let's suppose we have eight okay

so now once this entire for loop is

exhausted right

now what we will do we will swap this

minimum indexed element with the

this with the

with the minimum index that was earlier

there that is the zeroth index okay now

we'll swap it with the zeroth index okay

so now what happened

this we will get here zero and we will

get here three so only one swapping gets

done so now after first iteration all

the elements will be at its own position

because since we didn't change we need

to swap any elements we swapped only a

single element that has these two

indexes that is fifth and zero okay so

now what we will have zero one four five

six and three and at the end we have

eight okay

and then we will hydrate through again

so now our iterator will be here and our

j will be here and this time around

minimum index will be right earlier it

was zero now since we will not take care

of this or we will not will not think

about this index now because this is

already at its original position the

element is at its appropriate position

that means when we sort the array zero

will be at zeroth index so we will not

will not think about it and it doesn't

matter to us now because it is at its

original position so minimum index will

be now one okay so now let's try to see

an example wherein we get the

better understanding of this algorithm

so if you observe carefully this is our

input right so we have 23 10 16 11 and

20.

now what happens we'll make this our

first step and this is our iteration

number one okay so now what happens in

this we have our minimum index that is

at c

this is our i and this is our g

now we'll compare right is 10 greater

than 23 no it is not so still we have

minimum index as zero

is 10 greater than 60 no

is 10 greater than 11 no okay now this

is the first step okay just a minute

guys so let me erase this so our i will

be here and j will be here and minimum

index is at zero okay

because uh that is the first index okay

so since we are taking into

consideration the smallest element so

now we'll compare is 23 greater than 10

yes what we will do we'll update our

minimum that means this is now index one

now what we will do we'll have our index

updated as 1 and then what we will do we

compare 10 with 16 10 with 11 and 10

with 20. since this is our minimum index

after first iteration now what we will

do we'll swap it with the first index

that is this and this element will be

swapped so that is where we have 10 here

and 280 rest of the elements are

done so this is our first step and our i

was at 0

now our i is at 1 so this is our minimum

index right this is our minimum index in

this case now 11

in this case what is our minimum index

that is doing one right so main is here

and 23. now 23 will be compared it is le

greater than 60 so this will be our main

again 11 will be compared so this is our

main

now 11 will be compared with 20 so this

is not our minimum element now this is

our minimum element and it will be

swapped with 23. so 23 and 11 will be

swept so that is what you see here so 10

11 and 23 is swapped with this so 23

here and 11 here right so 23 will be

here and rest of the elements will be as

it is so this is after iteration number

now what happens in iteration number

three

so we have 0

11

at its original position right now let's

swap back and let's erase this

so now what happens so this is our

minimum index right and now 16 will be

compared with 23 nothing will happen 23

will become

16 will be compared with 20 nothing will

happen so this is our minimum index and

this is the ith index where we will be

swapping it so 16 will be swapped with

itself and rest of the elements will be

as it is so you will see 16 and then 23

as it is and 20 as it is considering

this iteration number one okay so after

iteration number three

so after iteration number three this is

our input array so similarly after third

iteration this thing will happen as 23

is greater than 20 so these elements

will be swapped and in the four

iteration is the required as last

element is already sorted okay so no

fourth iteration is required as the last

element that is there which is already

sorted okay so this is the whole

demonstration of this selection sort

algorithm after learning what is

selection sort let's quickly hop into

the implementation part we are

implementing selection sort in python on

google collab so let's quickly switch to

google collab ide so here as you can see

i have just briefed with the simple

steps which is easy for people to

understand so step one what we are doing

in this particular coding is we are

declaring a variable called min so that

is minimum that is always located in the

location 0 of an array right so that

first particular element in the array is

considered as a minimum element

that particular element is compared with

all the other elements left over in the

array right any element which is found

which is lesser than the minimum element

then we swap the places of

and the values of minimum with the found

element right so we always consider the

array should have the first place should

have the smallest value so this is how

generally selection sort will work

right so after doing this process one

swap in order to continue the iteration

we'll always

put min value plus 1 that means the

variable minimum will be added by 1 that

transfers the

place of 0 to 1 in the index of the

array right so the second element will

be considered as minimum that second

element will be compared with all the

other leftover elements in the array

except the first one which is already

considered as a smallest number so once

it is done the same iteration will be

proceeding until unless all the elements

in the array has been sorted right this

is how selection sort will work so the

same thing is implemented with the help

of python

if you quickly see this particular

program so here selection sort is the

name of the function which is being

given in order to keep it relevant then

you have an array and size of an array

what happens is minimum number that is

minimum variable will be compared with

the other elements of the array with the

help of the for loop every step it will

jump every index it will jump array 0

array 1 array 2 ra 3 up to the elements

here if you could see the data is having

five elements that means the array value

starts from zero

up to four we have right that particular

iterations will be done at the first

part if it is not finding any element

which is minimum then it will consider

the first element itself as a minimum

then what happens we will just

put the minimum value iteration plus 1

that means it is going to the next one

and checking for the

same kinds of in similar way and it is

also considering whether the minimum

element is

smaller than any other element or it is

greater than so accordingly it will try

to

find out and then it will quickly swap

again and continue with the third

element so these things will happen with

the help of this particular function

having two fonts and it will always i

told you compare with the help of if

condition here if you want that in

descending order you should just change

the

value here that is lesser than you have

you can make it as greater than it will

sort it in a descending order as well

right so this particular

step you have to notice so why do we use

this is because in order to

swap the minimum number to the correct

position right so whatever the position

has been found to be the correct it is

formed with the help of this particular

line of code

after that you could find you have a set

of data with five elements including the

minus value as well and it will try to

find the length of the

data what is the length is nothing but

size how many elements are there

accordingly it will sort science is very

important in order to compare between

all the elements it should have an end

value it cannot be infinity right so

immediately let's check out how do we

sort using selection sort

so here you could see

sorted array using selection sort is

done in ascending order starting from

minus 20 12 19 20 to 45 so this is how

the ascending order sorting by using

selection sort is done so let's quickly

have a check for descending order

immediately now

just have to change this if condition it

is greater than you will get descending

order i'm just changing here as well

right

so the change has been made here and

let's quickly run the program

now

right see it is sorting in descending

order that means greatest number first

and the followed by the smaller numbers

right greatest to smaller so this is how

selection sort will work in python now

let's see

the time complexity of selection sort

now if you talk about worst case that is

if the array is unsorted or it is

we are trying to sort an area which is

reversed in nature okay so let's suppose

we are trying to sort they are in

ascending order and we get the

a in ascending order or descending order

okay so that is 10 9 8

7 and 6. so this is the worst case right

and now what happens in this case

every index the minimum index will be

updated for every

element okay so 10 will be compared with

nine so minimum index will change from

zero to one then zero two 3 and so on

okay so find the minimum index that is

this element so this is the worst case

now what happens we have the outer loop

that is working from 0 to n minus 1 and

the inner loop that is working from

z from j plus 1 to the size so in any

case whether we have this

unsorted array that is here

we will still be traversing because n

square times because we have these two

for nested for loops which are working

up to the size of the area

done and same thing happens in the

average case as well whether we have

some elements in the sorted format let's

suppose we have half of the array in

this way and then the rest of the

elements are unsorted still we will not

update our minimum index but rest of the

elements will change for the uh not for

these three but for the rest our minimum

index will keep on updating okay so it

doesn't matter so average case type if

you talk about every time complexity it

will also be n square but what happens

if our array is still sorted right

or if our array that is the array given

is already in sorted format will

there be if we modify our bubble sort we

can get this down to below of n but this

is not the case in selection sort still

we will be comparing in the outer loop

from 0 to n minus 1 or size minus 1 and

in the loop will be again going from j

plus 1 to less than size

without even if we are not going in this

for

in this if condition that is the

comparison condition will not be

executed and the minimum index will be

as it is still we are going through this

for loop okay whether we are not even if

we are not executing this a block okay

it doesn't matter still we are going

the n square time complexity will be

there even in the best case as well okay

so this is all about the time complexity

of selection sort now let's talk about

the space complexity of

selection sort since we are not using

any auxiliary memory so auxiliary memory

can be in the form of arrays linked less

stack hues or even strings since we are

not using any of these extra memories in

order to sort our array so the reason

for that is because we are doing this

within the array that is provided to us

right so the space complexity is

constant that means

one as we are not using any auxiliary

memory now let's talk about selection

sort analysis if you observe carefully

in this array let's take an example

first 10

9

8 7 6

okay let me put a 6 here

so this is our array right and in this

array what we are trying to do we are

trying to

arrange it in an ascending order so now

if you remember the algorithm the outer

loop work from

0 to n minus 1 and then inner loop work

from

that means 0 plus 1 that is let's

suppose if this is an iterator if we use

in outer loop we used i and then in in a

loop we use j and j

work from i plus one to

size that is it right

now and then inside this we used to

compare so now in worst case

every element was compared right j was

compared with i plus one all right our i

was compared with

j plus one so it was compared with this

this this and this

and we

we're selecting the minimum element in

the array the minimum index rather we

were selecting the minimum index in the

entire array so this was working for n

times and this work from big o of n

times right and in worst case

in worst case the number of comparisons

required will be before n square because

we are trying to find the minimum index

in the entire area right and once we

have that minimum index and later on

we'll swap them right

worst case it will go from 0 to n that

means big o of n and the inner loop will

also go from big o of n

that means 0 to n so in worst case since

these are nested for loops so the worst

case will be because n square

and for comparing them we'll always

compare

all the elements and it will be again it

will boil it will boil down to what we

call n square when we talk about number

of comparisons

and what happens when we are trying to

swap them since we have this minimum

index that is there only one swap was

required that was outside this

inner for loop right

so we have this in for loop and here we

were doing the swapping inverse is the

number of slabs that are required is big

o of n

okay in worst case that means we were

swapping only single time and it will be

the case right that in worst case that

all the elements right at the end will

be swapped so we will have at the end

what five six seven eight and nine right

and we will swap them only once in the

entire area that is once for every

element so in worst case it will be pick

off n square

now what about stability if you talk

about stable algorithm it means that if

you have this array let's take an

example it is 10

8 9 and 10 again and then 6. if you talk

about this the sleep stability will boil

down to two things the relative position

of these two elements 10 and 10 dash now

if we sort this it can be six

it will be rather

it will be 6 8 9 10 and 10

dash right

so it will be 10 and 10 but uh just to

separate these two tens we are taking

this we are taking as an example we are

taking this assuming this 10 to be 10

and this tends to be 10 dash and it can

also be that it will be 8 9 and then 10

and 10 dash and 10 so both of these are

sorted right but

if you talk about stability this is a

stable algorithm why because the

relative position of this 10 and this 10

is intact and this is an unstable

algorithm

now when we compare

or when we do the swapping in

selection sort it is not guaranteed that

it will be stable right and

the elements can be

unstable that means we will the

resultant array will be in this format

that 10

may be at first and then we have 10 so

it is not guaranteed that it will be

always stable but yes we can make it

stable by modifying our selection sort

but if we talk about traditional

selection sort it is an unstable

algorithm right

now what about the

in place that means are we using any

extra memory or extra space

no we are not using any extra space

right

extra space can be a link list it can be

an array it can be a stack it can be a

cube right we are not using any of these

extra spaces so that is for the same

reason this selection sort algorithm is

an in place algorithm right because we

are swapping our elements and we are

comparing them within the given array

right we are not using any extra memory

right so for that reason this is an in

place algorithm let's try to reiterate

what we learned so far

so if we talk about number of

comparisons inverse is it can go to big

o of n square in terms of number of

swaps it is

big o of n it is an unstable algorithm

and it is an inplacement

now before we understand what is quake

sort let's try to understand what is

sorting and why do we require sorting so

sorting is a mechanism wherein we will

be

sorting or arranging our data either in

ascending order or in descending order

right so let's suppose you have a

students you have 10 students and all

those students have

roll numbers allocated from 1 to 100 and

you want to know which role numbers are

present and which are absent and which

have left the college or school right so

in that scenario you can easily

implement sorting right and you can

understand when you have that sorting

arrangement in place you can easily

detect which

elements or which

students are absent or not right so

herein you can use sorting so in this

tutorial we are going to understand

quick sort equalism it is one of the

most widely used algorithm it follows a

paradigm of divide and conquer what do

you mean by divide and conquer basically

we will be dividing our array in such a

way that every time we will be dividing

let's suppose this is an array and now

we will be dividing into two

then further we'll divide it into two

then further we will divide it into two

and so on right so

we'll see in the algorithm part how we

can implement this

divide and conquer paradigm and in this

tutorial we will be implementing this

quick sort using recursion we'll see how

we will recursively call those functions

based on some pivot element now in this

recursive call we'll choose a pivot

element let's suppose you have this

array and we're choosing this element as

pivot obviously you can choose any

element as pivot right so it can be

first element it can be uh last element

it can be any random element but once we

have chosen those that pivot now what we

will do

in each iteration right in quick sort

what happens in each iteration this

pivot will have its original position

that means this will be the position in

the original array as well let's suppose

this is our pivot now this pivot will

have its original position after one

iteration after that iteration is over

and all the elements that are less than

this pivot

are on the left hand side and all the

elements that are greater than will be

on the right hand side now

then we will be choosing another pivot

now what are those pivots we'll see in

the algorithm move uh more extensively

what uh how we can choose that pivot now

let's suppose we chosen that we chose

this pivot and this pivot is here and

after the second iteration what happens

this pivot this will be our next pivot

and this will be our next pivot now we

will be having two pivots so this is how

we induce that we are

implementing divide and conquer approach

okay with each step our problem gets

reduced to two which leads to quick

sorting quick sort right or quick

sorting algorithm okay so now we will be

dealing with this sub array and we'll be

dealing with this sub array and now

we'll be implementing the same procedure

on this sub array that means this is the

pivot and this is the pivot right

now let's try to understand the

algorithm of quake sort so now we have

this

first of the method that is there that

is known as quick sort in which we will

be calling this quick sort recursively

again and again but first time around

what happens we will check okay now we

have this array always we will check

beginning should be less than end

because that way we can keep the track

of things that okay this is the part

that is already sorted and this is the

part that is unsorted right and now we

will be checking and after checking that

we will be calling this method we will

see what this method is we will see the

algorithm and we will see how this

partition happens and we will get the

index of the let's suppose we pick this

element as pivot and after partition

what happens this pivot has its original

position at index 3 right and

that will be returned and that will be

contained in this pivot index right and

now what happens now we know that this

is its original position in the original

array wherein we will get the sorted

array this will be its original position

that means this element lets the phone

is eight it will be at index three and

this will have its original position

after each iteration now first time

around what happens this partition is

called next time around what happens

this quick sort algorithm is called

again recursively first time on the

left hand side that means this portion

now in this portion this will be your

pivot

okay you see beginning

is uh we are sending the arguments as

beginning and pivot index minus one that

means we are not including this element

because this has been already sorted we

are not including this element and we

are calling this function on this sub

array again and this time around this

will be our pivot and same thing happens

similarly when we are done on the left

uh with the left hand side now we will

be moving to the right hand side that is

we will be implementing it on pivot

index plus one that means this element

from this element

that is there to the end of the array

and this time around this will be our

pivot okay

now with that being said this is what

happens when we

are implementing quick sort but now what

about this partition method let's see

how that happens

so in partition what happens we will be

setting up the pivot element that is

setting up the element which is our

pivot obviously you can choose any

element but in this tutorial what i am

going to use and

what you should try first

that we should try to pick pivot as the

last element obviously you can pick any

element

and its time complexity depends on which

pivot you will be choosing we'll see

that in the time complexity part okay

now we have set this pivot as the last

element and now what we are doing we are

saying that okay the pivot index this uh

this step refers to what

this is this is the index

from let's suppose this is the pivot

index and what happens this will be our

pivot okay what happens this pivot index

maintains that order okay from this

index from this index everything on the

left hand side is less than the pivot

and everything on the right hand side is

greater than the private so we'll see

when we we will see an example and then

i will show you how this pivot index is

very important okay now what we will do

obviously at start it is at this

position that means we are not we have

no such scenario wherein we have some

elements that are less than pivot and we

have some elements that are greater than

pivot okay

so now let's suppose this is our array

and this is our pivot right and this is

our p index

that is the index period index and it is

minus one right now okay now these two

steps are done now what happens in the

third step now we will iterate from

beginning that is this point and we will

check if any element is less than pivot

if that is the case then what we will do

we increment this

and

swap those elements that is the error

the first element and the

index that is present at that means now

if you see this step now we have

incremented it first right now let's

suppose if any element that is less than

pivot we first increment the pivot index

that means that pivot index will be here

and we will be swapping it with a rr of

i and ar of i is also at this location

so this element will be swap with itself

now you might be thinking okay so why we

are doing this right why we are doing

why we are swapping this with

its own uh with its own position you

won't get the intuition in this step but

in the next step you will definitely get

the intuition now let's suppose this is

the thing that happens in the for loop

now let's try to reiterate this now if

an element is

not less than pivot let's suppose there

was here we had five and here we had

three so it was less than and we

swapped it for yourself now let's

suppose we have this element six and it

is not less than

pivot right and what happens over here

so we will not be we will not execute

this if block right and then we'll have

this arr of i now i will be here now i

will be incrementing and this time

around we have 2 and p index is still

here right now this time around it is

less than 2 right and now what we will

do will increment first the p index it

will be pointing here and then what we

will do will swap

swap these two elements right these two

elements will be swap so now you have

two here and you have six over here

right so you see this is the reason why

we have this pivot index at in place and

why we are swapping them so in the first

step it was

uh it was that it happened

due to the fact that the element was

less than pivot and if the element would

have wouldn't have been less than the

pivot then we have incremented the i

pointer and p index would have remained

on minus one

now finally what happens now when once

the entire iteration is complete and

let's suppose we have eight over here

and we have then ten now once the

iteration is completed now what we will

do we will swap these two elements that

means five and six will be swapped and

we have five here we have six here we

have eight here we have ten here and we

have three here and we have two here so

you see

after one iteration all the elements

that are less than pivot will be on the

left hand side and all the elements that

are greater than will be on the right

hand side

and finally we will uh return

pivot index uh that is p index plus one

that means we will be returning this

index

so that this element is not considered

or will not participate in any further

iterations or any further recursive

calls because you see if you observe

carefully that we we're sending pivot

index minus 1 that is without 5 all the

elements on the left hand side and plus

1 that means without this index all the

elements on the right hand side

okay this is how partition works now you

might be confused a little bit now let's

try to demonstrate this with the help of

example so you see we have an example

over here right we have 5 10

9 6 and 7 these are the elements in the

array and we have this pivot here the

last element we have chosen last element

to be the pivot and after that what we

are doing we have this end pointer and

we have this beginning pointer

also we have that pivot index which will

be somewhere around here right

that pivot index which will be minus one

now this seven will be checked okay is

five less than seven yes five is less

than seven so it will be swapped with

itself and pivot index will be

incremented first and then swap within

itself now pivot index will be here

next time around our a our i pointer

will be here first it will be here and

what it will be incremented now will be

again we will again check okay

is 7

is 7 less than 10 no it has not so our i

will be incremented i will be now here

at this position right

now again it will be checked no again it

will be checked yes so now what happens

seven and six uh the six will be

replaced with

what 10 so you have this six in here

obviously pivot index will be

incremented first and then we have the

six over here and it will be swapped

with 10 so 10 will be here right

done and finally when we are the end

once the entire iteration this is the

step one once the entire iteration is

completed we have 5 six and then seven

will be

the last swapping that we did the last

swap that we did if you observe here

carefully this swap

that we are doing

this is the one that is responsible for

swapping the seven with the pivot index

that is pivot index plus one that is

this location and we have this seven

over here and it will be replaced with

nine so that is why we have nine over

here and ten was here and this is the

array after first

iteration

now you might be thinking okay now this

element is fixed now we will not never

talk about this element because this has

its original position in the sorted

array as well now what we will be

dealing with we will be dealing with

this left part and will be dealing with

this right part

so now what happens in this part right

and what happens in this part

you see now we have new this is our

beginning and this is our pivot because

this is the last element that we will be

picking and this is our end similarly

this is our beginning this will be our

pivot the last element in the in this

sub array and the end will be here now

we'll be again doing the same step and

this time around we'll be checking okay

pivot is less than no nothing will

happen and then we will be we will be

swapping this thing

with itself right and now once this

entire suburb is completed will not go

any further because this time around

beginning is not less than end both

elements are at 0 and 0 is not less than

0 and now if you observe carefully this

is the condition that we were setting at

the start of the

function that is the quick sort function

and we'll be checking we're checking if

beginning is less than end right

so this is the importance of that

similarly the same thing will happen

over from this this side and again

beginning will not be less than index

end part and we will not go any further

so after two iterations our entire array

is sorted

right so this is the step one after step

two our entire heading is sorted after

learning what is quick sort let's

quickly implement the same in python so

here we are using python ide that does

google collab one of the ide mean to say

and then we'll implement that particular

program there so let's quickly hop into

the ide now

so here is the program for quick sort

in python so let's understand how this

program works right the first part we

need partition to be made right any

array in quick sort to be broken into

two halves and we will

start sorting in that particular

different pieces so

partition positioning

will be

done with the help of array low and high

variables so at the right most

always will consider the element of

pivot element right most element of the

array is a pivot element that is the

consideration so in order to do that we

will use p out is equal to a r r of h

right so then pointer for greater

element so whatever the element is

greater in order to compare will be

using this pointer in order to traverse

from all the elements inside an array

keeping one payout element in

consideration with comparing with that

particular element we use this for loop

system right if smaller than element is

present which is uh smaller than p out

we'll use this i is equal to i plus 1

and immediately will swap the element

in the position which is there in i with

j right that will be done with the help

of arr of i and j is equal to j and i

will exchange if you could see here i j

is being changed to j and i so when

exchanging the elements if it is smaller

than the pivot element

then swap p o with i if it's greater

than pure right if

any element which is greater than p out

element wherever the i is pointing to

that element will be swapped between the

element and put right in order to do

that

we will be using this particular

condition

then we will get back to the initial

position where we started the

partitioning right where we broke that

array into two parts the partitioning is

done

there will go back and will try to start

initial position

then the quick sort function will come

right so here

in quick sort again we need three

different elements array low and high

if

low is less than high that is smaller

element than p vote is present it will

all go towards the left side if there is

greater element than period is present

it will go to right side so partitioning

is done accordingly

so this is a recursive call which we

follow for quick sort right we'll be

having again array low

p i minus 1 pi is pot minus 1 so

again for the right of the period we

have a recursive call function which is

declared here once all these things are

done we have to give data in order to

sort something right we are here

presently concentrating on sorting the

array which is given in the ascending

order right so the data set here is

mentioned and it has been assigned as d

right so the set has been assigned as d

9 comma 8 7 2 10 20 and 1 so these are

the elements which we are trying to sort

right we are printing the unsorted array

that means however the input is present

here that is printed as it is unsorted

is array is equal to so and so which is

already there which which we are not

performing

any functions then we have print d that

means immediately it will print

then size is equal to length of d we

will consider in order to print while we

are printing right we have to print

element wise so again we have to print

it

nine first eight next seven next and

then two followed by

up to one

so after that is done we will send this

particular data raw data which is

unsorted data to the function called

quick sort which we have created here

right so that has been sent once that is

sent it will follow all the procedures

which is mentioned here all the

functions will be passed with the data

and then finally we will print sorted

array in ascending order which is uh

sorted using quick sort right so let's

quickly run this program and check out

what is the output

so it will take some time in order to

take the output so let's quickly see

okay so that is what i mentioned

unsorted array is nothing but the array

which has been given by the user

and sorted array is also given after

performing all the functions assigned

for the quick sort so if you could see

it is in ascending order starting from 1

and ending at 20. so this is all about

quick sort in python now let's try to

understand the time complexity of

quicksort algorithm in quicksort

algorithm we have now seen that

partitioning of elements takes place and

we are partitioning all the elements

that means all the n elements if there

are eight elements all the eight

elements will be we iterate through all

the eight elements right so partitioning

them takes n time that is order of n

time and then quick sort problem divides

it into the factor by the factor of two

right every time we are dividing it by

two so the entire

process or the time complexity of quick

sort in best case and in average case

takes order of n time that is big o of

log n

and same thing happens when we are

talking about the average case as well

but why this is n square in worst case

that is the question right so let me

clear it out so the question is that

why this thing happens if you are

picking either the smallest element

in the array or the largest element in

the array as pivot in that case

you are traversing through all the

elements again that means this n is

already there for partitioning them that

means you will be i trading through the

array but the extra n and that means

inside that and you're again

traversing through all the elements and

swapping them because you have picked

your pivot in worst case you can either

pick it as smallest or the largest

element in the array in both these cases

you are you will be swapping all those

elements with itself that this element

will be swapped right this is this is

the largest element right this is let's

suppose this is eight so nothing will

happen right so these are this this is

smallest then it will be swapped with

itself this is smallest this is this

will be swapped with itself this will be

swapped with itself this will be swapped

itself so all the elements will be

swapped and finally this element will

have its original position at the end

right so this thing will happen if you

are picking your pivot as the smallest

element or as the largest element in the

array okay so in this in these two cases

this is not the case you are picking

your pivots as random you are picking

your pivots randomly okay

in nutshell when you are picking your

element that is your pivot element as

smallest are or the largest element in

the array in that case that will be your

worst case time complexity and it will

be big o of n square

now let's talk about the space

complexity of quake sort now you might

be thinking okay we are not using any

extra space right we are not using any

auxiliary memory like in the form of

array stack q link list or anything

right but

for calling this function that is the

quick sort function we are using

recursion right we are calling this weak

sort again and again i do quick sort

calls are there for maintaining the call

stack we require order of n space

that is the time complexity will be big

off and

when we are using this approach and in

the worst case this will be the scenario

that all the elements will be on the

call stack okay so in worst case the

space complexity will be bigger and but

if we modify this approach of of storing

the elements and calling the call stack

and maintaining the call stack we can

reduce it to big o

of log n

now let's try to analyze quick sort

algorithm let's first try to understand

the stability so let's suppose if you

have this array one three one dash and

four

now an algorithm is said to be stable if

both these one and this one

both

these

in the sorted area will maintain their

relative positions now you have this

sorted area right and both one this one

and this one are maintaining their

relative positions which were earlier in

the unsorted area right so if that thing

is maintained right

that thing is maintained the algorithm

is stable as it is not stable obviously

you can have another

way with which this is also sorted but

this is not a stable this is unstable

algorithm and if you are sorting in such

a manner and you have these things

placed

this algorithm is unstable so if you

talk about quick sort algorithm quick

sort algorithm is an unstable algorithm

although we can do

some modifications and we can stabilize

it or we can add we can make this

algorithm as stable but

as of now

if you talk about quicksort algorithm it

is an unstable algorithm what about in

place and outplays since we are not

using any auxiliary memory right we are

not using any extra space explicitly

right in the form of array or linked

list or stack right or even cute we're

not using any extra

memory right so

this algorithm quick sort algorithm

although we are maintaining a call stack

wherein we are you uh maintaining a call

stack and we have a space complexity of

big o of n

but since we are not explicitly

mentioning this these

uh these auxiliary memories this

algorithm is an in place algorithm and

these are the two analysis that can be

done on quick sort

so in nutshell if you talk about quick

sort right

it is unstable algorithm

and it is in place algorithm now we'll

be learning regarding divide and conquer

approach to programming

so every complex program can be divided

into sub programs and solved to make it

more simple and precise enough so let's

quickly see what is divide and conquer

approach

so as the name suggests divide and

conquer any complex program for example

right i am writing complex program which

is having

so many applications in that so what do

we prefer

we prefer

breaking that particular complex program

into the sub problems or sub programs

and solving together right so here in

sub program one we'll be getting one

answer

in sub program two we'll get one more

answer

in sub program three we get another

answer

combining all these answers

we get the final result right so this is

what divide and conquer approach is

right so

why do we use this particular divide and

conquer approach generally

the first thing is the problem solving

becomes easy right for everybody it is

easy to understand and easy to look at

the branching say for example if in this

simple example which i gave you

people can figure out one complex

program was divided into three different

sub programs we got three different

answers combining all these answers

we ended up with the final result so

this is simple and it is less time

consuming because parallely people will

be working say one big project you have

got in order to work with you can divide

amongst

three people right all the three people

simultaneously will work

say for example after two hours you'll

be getting

answer one also answer two also answer

three also then quickly you can just

combine all these answers get the final

result

right so hope this is clear so this is

why we use divide and conquer approach

and it is very easy

then coming up to the applications where

do we apply these approaches in data

structures we'll be applying that

majorly in merge sort

quick sort

by research and many more places

so let me quickly give you a

crisp knowledge

how do we solve this divide and conquer

approach with an example so i'm taking

merge sort let's quickly switch to the

ide and see

how does this particular divide and

conquer approach help us in order to

solve merge sort or solve or sort the

elements inside the array right

what is merge sort if we talk about

merge sort let's try to understand first

sorting so sorting is a mechanism of

giving order to your

values right so let's suppose you have

some values random values 10 30

and then you have 5 to

one and so on right you have these

values and now you want to

maintain some order so in order to

visualize this data let's suppose you

want to see uh the ascending order of it

or the descending order of it that is

what you mean by sorting so let's

suppose you have a class and in that

class you have several role numbers and

some of the roll numbers are not present

and then you want to

sort those roll numbers

in terms of ascending or descending

order that is when you require sorting

so this is the basic intuition behind

sorting trying to give order to some

kind of values or some kind of a data

set right so in this particular tutorial

we are going to talk about merge source

so merge sort is a classical sorting

algorithm in this sorting

every time your problem is divided into

sub problems so that

your problem set is reduced and then you

will be focusing on that sub problem

similarly every time when you are

dividing your sub problems you will keep

on dividing it unless and until there is

only one element left right if you

compare it with simpler sorting

algorithms like bubble is there

insertion is there selection is there

quake is there when you talk about its

time complexity as compared to these

algorithms this is very much efficient

now it follows a paradigm of divide and

conquer what does this mean this means

that first you keep on dividing your sub

problems and then you will conquer those

problems and then you will combine those

things okay so here and we'll see when

you are trying to divide your sub

problems and then when you have your

problem set and those problem sets are

conquered that means those problems are

further

when you talk about in this example

those sub problems are sorted in this

case and then you have conquered them

and then you will combine them that is

your merge phase wherein you will be

combining your problem again and then

for forming

again a single sub problem so every time

you will be dividing that sub problem

you will be conquering it and combining

it so this is how this divide and

conquer paradigm works

so basically

when you're dealing with merge sort you

are focusing on two functions that is

your merge function and your merge sort

function so now let's talk about this

divide that means you're dividing your

sub problems which continues unless and

until there is only one element left

because one element in itself is sorted

right now this is your divide phase what

about conquer basically you are

conquering those individual sets and

then merging those two sub problems into

a single problem and finally you will be

doing it on each step and finally you

have your original array which is sorted

now let's talk about merge sort

algorithm

so

first let's talk about merge sort method

so in this method what we are doing we

are dividing our

array into further subarrays how we are

going to do that we are basically if we

have this array right and this array

let's suppose this contains eight

elements right this is our array and

let's suppose this is our left pointer

and this is our right pointer and now

what we are doing we are dividing it so

we need some kind of

in

iterator wherein we will store the

sum of and we try to calculate the mid

value how would you do it in simple

words we calculate left plus right

divided by 2 that's it right

so we have this division and then we

will divide this part because we are

calling this function again

right on the left hand side so this is

going to call on this side that is we

will be talking about now only three

elements so this is let's suppose

let's take four elements on this side

and four elements on this side so our

mid will be three point five so we'll be

talking about elements from zero to

three so we will be talking about four

elements and then further

these two steps are remain why because

we are implementing this in recursive

fashion so now let's suppose this is our

first function call and you have these

three steps one let's name it one

two and three okay so in the first

function called one two and three so

this is the first function call and in

this we're calling again this is a

second function call and we are calling

again these two remain right and we are

calling again one two and three right so

in this case again we are calling it on

these four elements and it will be

divided into further two elements zero

and one right and in this case again

this is called this will be called on

this

these two elements right here we are

talking about only two elements so this

is the third function called and again

we will be dividing it these two and

three steps are still remaining

so

in the fourth step what we are doing

with only single element right and in

this case we are talking about only this

element right and further we will not be

able to

divide it and in that case our left is

not greater than our left will be

greater than or equal to right and in

this case it will be equal to so we will

return so now it will be returned right

and then whatever was the left over

right now we talk about this single

element the other element that was left

behind we'll talk about that so again

that will be divided into one

right and again this will the second

option just erase it because it looks a

little bit messy

so now what happens

let me just

put it again in red so here we call this

fourth time and this time it return

right

so in this case now we will be on the

second step now again it will be called

on that single element

and again

left is not great will be greater than

or equal to in this case it will be

equal to and then we return so again we

are returning so we have these two

elements one and one

that means not one and one element but

there is only a single element in both

these arrays right

why i'm saying that in these two arrays

will be we will check when we talk about

merge okay we'll see how that is

implemented okay

so now

these these two function calls are done

and then we deal with

merge now before going into the merge

let me show you a demonstration of how

things look

so you have these elements and here you

have how many elements you have five

elements right

and now you're dividing it into three

and two

now this is your first step the second

step will be this

so now will you go ahead and create this

as your third step that means you will

move on to this no because we saw unless

and until left is not there is

no left left

right

we will not go to the right so this is

your second step then this will be your

third step this will be your fourth step

now you will move on to your fifth step

right

and now once you don't have anything on

the left nothing on the right then what

happens will this be your sixth step no

your sixth step will be merge so let's

move on to merge now

so in the merge function if you see the

algorithm for that is simple that you

create two sub arrays that is the one is

your left array and another is your

right sub array now in this you have

obviously in the last case if you have

seen we have a single element here and a

single element here

now once we have deduced out the

length of these arrays what should be

the length of these sub arrays and we

have declared the length or declared

these arrays and then we have

initialized these arrays once these

three steps are done but then what we

are going to do we are going to create

three iterators i j and k and those

iterators deal with i iterator will deal

with the left array j iterator deal with

right array and k with the original

array which helps us to insert the

elements so

once we we have everything in place what

we are going to do the next step is

comparing the values right if this

element that is the element in left

array is less than the element in the

right array we are going to insert that

in the original array so now let's

suppose you have 10 here and 23 here so

10 is less than so we are going to

insert this and we increment the k

pointer and now also our i pointer

pointer will be incremented it was

earlier it was zero and it will go to

one right and

now what happens now our

our i is pointing to one and our length

is also one so now that in that case

when one of the array is exhausted the

next array whichever is the layer

whichever is left right it can be either

the left array or the right array those

elements will be directly inserted in

the original area because we know for

the fact that both of these left as well

as right arrays will be sorted in itself

okay so let's see what is the next step

in the demonstration so

here we had our steps right and this

will be the sixth step wherein we are

going to merge this thing

now will we will this be your seventh

step no your seventh step will not be

this your seventh step will be

here this will be your seventh step now

six step is done now you will be

dividing it and you will be creating all

those arrays now once you have your

right array and there is no right

because this left is already done and

now you had your like right left now

this is also done now your eighth step

will be this

that

you will be merging it this will be your

eighth step then you will be merging it

now will this be your ninth step no you

have your this array that is your left

array in place but what about the right

arrow is this in place no it is not so

now let's try to calculate that

now what will be your ninth step this

left is done this is your ninth step

then what will be your tenth step this

is your tenth step

well now there is no left right now

we'll move on to this right so this is

your 11th step because this is the right

side of it right and now when you don't

have anything on the right now you will

be merging these two steps and this will

be your 12th step which is over here

so this is your 12th step

that means you will be merging these two

and the final sorted array

is this array and it you will get this

array in the 12th step so you see 10 11

16 20 and 30.

now if you observe carefully you have

these individual arrays one and one so

now while you are merging them you are

also sorting them so the left array

is sorted and same thing happens on the

right hand side as well if you see three

and four

these two elements are sorted in this

left array so this is the reason in the

right area right

not the left array so now when you are

merging them you will get again an array

which is sorted in itself you see 10 16

and 23. so if one of the array is

exhausted the next array elements can be

directly inserted in your original array

let me erase this and you see you have

your left array which is sorted and then

you are merging it with the right array

which is also sorted now if one of the

arrays is exhausted the next array

either it can be left array or the right

array the elements from that array can

be directly inserted in the original

array because we know the elements

itself in either of the arrays either

the left or the right are sorted okay so

this is how you execute your merge

function

so here is the program for merge sort in

python so how does this merge sort work

generally one single array will be

broken into two different pieces again

those two different sub arrays will be

broken into sub sub arrays so

after that whatever the answers we get

at the last will be combined together in

order to finish the sorting of that

particular array so we are merging all

the answers which we got from the sub

arrays to make a final result so quickly

let's see what do we do in order to have

a merge sort in python

so first we want an array which has been

passed through this merge sort function

so what happens inside this function

first the length of the

array has been calculated once that is

calculated it has been divided by two so

it gets left and right parts of an array

right

so after sorting uh the array into two

different halves we have merge sorting

left side of an array merge sorting

right side of an array right then we'll

perform the while operation

here with the help of the looping

systems so we'll first try to

check out whether we have the

right array

less than the length of an array of the

left and then again left array it is

less than length of the right array so

we try to

merge and we try to solve the elements

then and there itself so later we'll go

back to the left and right parts of

while loop here we have length of an

array towards the left side we are

checking whether it is

lesser than or greater than and

accordingly we are deciding where we

have to merge the answers what we have

got from the sub arrays right so then we

will always have a printing option of

this particular arrays we will do that

in the last before that in order to

merge all the answers we have got from

all the subarrays we'll be using for

loop here right so all the array answers

will be

submerged and we'll get the final sorted

array which is of uh so many elements

which is there in the uh input given by

the user say for example five different

elements but they're in an array so

after combining all the sub arrays

answers we'll get the five sorted

ascending order

elements in the array by using merge

sorter so let's quickly have a

look at it how does this particular

merge sort will work so uh this is set

of an array with eight different

elements inside that which is not sorted

we have to sort that once this array has

been passed through the merge sorting

function it will perform all the

operations finally it will merge all the

sorted arrays and it will display

in the print list right so

let's quickly run this program and check

out

even though if it is we are mentioning

the words array but we are using list

here in python in order to store it

right

so this is the sorted array which we get

so here we could see we don't have a

sorted array but here it is sorted in

ascending order that is smallest to the

highest so this is all about the merge

sort now let's quickly check out what is

greedy approach in programming right so

greedy approach is nothing but a simple

solution for the problem which will give

you exact correct solution it is a

step-by-step approach it is finding the

answer in step by step way and minimal

time right so efficiency plus minimal

time is equal to greedy approach so that

is what i can let you know

apart from that we have a benefit here

so

we can get a simple solution very quick

manner and we can also trace out very

well so some of the applications of

greedy approach are

prim's spanning tree algorithm travel

salesman problem etc so in order to have

a connect let me quickly give you an

introduction to prim's panning tree

algorithm so what is this all about the

spanning tree algorithm so

generally a tree is one of the kind of

graph which is having vertices and edges

and

mention there is no cycle specially one

vertex has not been joined to another

vertex forming the cycle right so a

spanning tree next word so what is the

spanning tree it is having all the

vertices connected

in a constructed format right

uh when you have a connections of

advertisers

constructively forming a graph

then that particular graph can make

spanning trees it can be multiple

spanning trees say for example

so this is one spanning tree

and you have one more spanning tree

which is

like this

so

connects between the vertices forms a

spanning tree right so next what is

minimal spanning tree

so that means every node to node

connection vertex to vertex connection

will be having certain values say v1 v2

v3 and so on vn right so

reaching a source to destination or

visiting the every node in the tree or

the graph at least once using a minimal

value for the edges given then that

particular tree is known as minimal

spanning tree so whose sum of weights of

edges is minimum so from

the source through the destination if

you calculate the sum of the edges was

always minimum then we

let that particular tree known as

minimal spanning tree so this is a brief

introduction towards prims minimal

spanning tree algorithm so let me

quickly see

with an example let you know

how does this work right now this

particular example is a spanning tree it

is not having

anything

mentioned minimum or maximum we are here

in order to find minimal spanning tree

so what we have to consider we have to

consider any one node and we have to

start traveling from one node to another

node in a minimal possible way

the edges is having values edge value

should be minimum always because we call

it as weight right edge weight should be

minimum when you

add all the

edges you have to get the minimum number

not the highest number so in order to

give a clear picture let me quickly take

one node here so i'm taking node b so

you have to see this is iteration 1

right so node b is taken into

consideration if you could see node b

has two different ways i mean two

different sub nodes it is there so one

we have d one we have c what is the

rules we should have the value h value

as minimum as possible so

11 or 5 minimum 11 is greater 5 is

smaller so i am traveling from b to d

okay

b to d is 5

10

coming to d

what are the different

sub nodes you have or the connections

you have edges you have for d

d has

the connection from that node to c again

d to e if you compare both

d2 is having the value 2 d2c is having

the value 3 we are having the minimum

value in the path d to e the edge is

having

the minimum value so what do you do from

d you are going to e

okay

so with the edge value 2

hope this is clear

so

from e if you take how you can travel

you have

only one single

path to travel from e to c or further

right you don't have any other

probability in order to reach c

right so also you can you can go back

and check so it it forms five again so

without that we can also have the

connections so e to c is having seven

right so when you have 7 uh and if you

add 2 plus 3 it is 5 so think how you

will proceed so from e to d back again

and then c

or e to c so you have to have a minimum

value and the thing is you should not

repeat the nodes again so here there is

no possibility way you have to go to c

with 7 only you can't think the way i

thought you now so it was just a leading

you into a thought that can you go back

add together like 2 plus 3 is 5 right 5

is lesser than 7 how i can go back in

just go to c no you cannot do that right

you should visit once at least once it

is visited you cannot go back

so it is seven done so next from c to a

you have one connection so see today

only one connection so again you are

going

to a with the help of

four so you don't have any other nodes

which is connected to c in order to

think how to reach a right so if you add

all together you will get a minimum

spanning tree say for example 7 plus 4

plus

2

again you will have 5

right so

this is 7 so you have

11 so the answer is 18

right so this is how the minimum

spanning tree will work right prim's

minimum spanning tree

so let's quickly implement this

particular

problem or algorithm into a python

programming code so let's implement and

check out on google collab how does this

prims spanning tree will work

so here is an ide that is google collab

where we have prim's algorithm program

in python

so let's understand how this program

flow works so first we'll be considering

the infinity term so we are mentioning

infinity to

so many nine together in order to have

as many as combinations as possible so

next we are considering the number of

vertices for the graphs so we have five

vertices for the graph so v is always

indicating the vertices of the graph so

number of vertices is five

after that we'll always form an

adjacency matrix of rows versus column

2d that is rows versus columns phi cross

prime matrix will be

present so here i've formed a graph with

adjacency matrix

which is represented what is adjacency

i'll just quickly tell you we are having

zeros in the diagonal and the

parallel elements are same so if you

fold this particular square paper for

example into exact diagonally from

left top corner to right bottom corner

all the elements will match to each

other so this kind of matrix is known as

adjacency matrix so after that what do

we do

we need to have an array in order to

track the vertex which we select so

whatever the vertex we select we have to

have the track of it whether is it

matching whether it is having the

minimal edge how it is doing what it is

doing so in order to track we have to

have an uh vertex uh selected

array where uh it is having um

vertexes which we have selected then

selected will be true else it will be

false whatever you select will be true

first initially and then it will make

the comparisons and accordingly it will

change the values so the empty selected

array will be having five zeros inside

that so after that we should always set

the number of edges to zero it does not

mention how many edges it is there we

have to keep it zero because always

edges will be a vertex minus one we have

uh five vertex and edges will be four so

that is the logic it will work with so

that is in minimal spanning tree

especially so we have to choose

zeroth vertex and make it true always we

have to choose the vertex 0 and we have

to consider that as a true it is an

assumption in order to start the working

after that we have to check how do we

check we have to check the um

complete elements inside the matrix

accordingly row vice

column wise and we have to find the edge

which is having the minimal number

in order to traverse right

so after finishing all these things if

it is not selected if there is no edge

then it will consider the neighboring

vertex so if it is not forming if it is

not getting any weighted uh edge which

is having minimal weight then it will

try to correspondently

see the neighbor elements inside the

matrix right so then

after doing that will be printing the

edge and how it is traversing what is

the minimal value

at the end right so let's quickly print

this particular

output

execute and see how it will work

so here we have edge and weight so at

zero the weight you can you can go from

two to five again from two you can go to

three to one again for three you can go

for four to one and for four you can go

to one to two so these are the traversal

of minimum spanning tree that you can

make in python

now we'll be learning regarding dynamic

programming so dynamic programming is an

approach in order to solve a problem in

data structures so

what does this particular dynamic

programming will do it will give you the

best and the most optimal solution to

the problem

how it will give you it will give you by

recursively working on the problem

comparing the solution one to another

and finding the best and ultimate

solution for you at the end so this is

how dynamic programming will work

it is not letting you on with only one

single solution it will always give you

multiple solution which is comparatively

common and which is most efficient it

will give you amongst that it will

consider to be the best one so

applications of this dynamic programming

so where do we apply this particular

programming approach so matrix chain

multiplication is there and

one famous element that is stubborn of

hanoi so people would have heard about

aware of ni it is a very simple

mathematical problem statements

generally we use dynamic programming in

order to have a best

result out of this particular program so

let's quickly check out what is cover of

hanoi as an example for dynamic

programming so

as i mentioned tower of hanoi is a

mathematical puzzle right so it is

having

pegs and this text in the sense people

who are listening to the first time so

i'm just drawing a picture here so you

are having a stand here and

you have three different

rods stick like things there will be

disc

which is arranged on this uh usually the

children who play uh small children will

be having this particular stack in this

triangle format which is having the

biggest ring upon that there's the

smallest one at the end you will find

the very smallest ring so

like that we have x and diff arrangement

for tower of nine so

there are three different pecs which we

could consider which i wrote here ah

name it as x y and z okay three

different pegs and three different disks

you are only having

pex three and disc 3 here in

tavrophenoid and you can increase this

how much ever you want it is always in

the format n okay you have a famous

formula for towards the phenoid that is

2 to the power -1 so in order to find uh

2 from the source to the destination if

you want to put all the rings without

merging without putting the largest on

the smallest or without repeating or any

other mistakes without breaking the

rules

you can find how many moves you want to

do that say for example uh 2 to the

power of 3 you have 3 different discs n

is always the how many disc you use in

this particular problem so i'm

considering 3 here so 2 to the power of

3 is

8 right so when you minus 1 from that

the answer is 7 so in order to traverse

three this from x to z from source to

destination you need seven different

moves so this is how you will calculate

the moves the movements you have to make

okay moves is nothing but moments you

have to make all the three this in order

to transfer from source to the

destination hope that's clear so

uh next you have to consider uh what are

the different rules you have in order to

solve this game or puzzle or problem

anything so the first thing is only one

this can be removed at a time from a

stand from a peg you can remove only one

disk at a time that is the first rule

the second rule is the larger this

cannot stand on the smaller tests say

for example you have a smaller disk that

is disk one here you can't put a larger

disk on the smaller disk so this is a

a second rule for this particular

problem statement so considering all

this let's see how do we implement tower

of hanai problem let's quickly hop into

the ide now

here we are on the ide so let's quickly

check out what a source named as what is

auxiliary is nothing but temporary which

is used in order uh for to transfer all

the three disks from the source to the

destination you want to have a place

where you can keep all the disks at

least for a iteration or for a moment

right so source is named as x i'm

talking about the pegs right the stands

three different stands you have the

first stand that is source

is

x and the temporary stand that is in the

middle the second one is y that is

auxiliary and the target destination is

z okay so you have all these three peg

arrangements and you are considering

three disks for example okay let's see

how this particular program works in

python

so first we are creating a function

called hanoi okay and you are having

diff

source auxiliary target that is x y and

z

and then you are considering all the

disk we are equating that to one after

that we are printing the moments from

which this one is going to from which

spec to which pick from source to

destination or source to auxiliary or

auxiliary to

uh destination so xyz the

program completely deals with the

combinations of xyz once i show you the

output you will get to know so

you are having a common

formula here

this minus 1 comma source common target

comma auxiliary so this is what we use

generally

again you have one more formula which is

considered so again this minus one

auxiliary first source next and then

target it is very easy to uh remember

and also easy to work with so at the end

what you will do

you will just uh

type

the user input right you have to ask the

user how many disk he or she wants to

enter and how you will shuffle that from

source to the destination how do you

make that disk which is given by the

user travel from the source to the

destination

then we will be calling the function so

disks will be having the name and the

disk itself and then we'll be using x y

z

instead of source auxiliary and target

the objects are created so let's quickly

check on this particular program what

will be the output

right it is asking the

number of disks you want to enter so i'm

writing three for now so i'm giving

enter so these are the different moves

so you could count here you will be

having seven moves for this three discs

i told you the formula 2 to the power n

minus 1 is used in order to calculate

how many moves this particular discs

will make in order to travel from source

to destination or source to target from

x to z right so this is about the towers

of anal implementation so let's quickly

check manually how does this particular

movement will happen in the

ppt again the same outputs which we got

on the google collab has been listed

here so let's quickly see how we can

put that particular output into reality

how does it look

right

so i'll consider

three different pecs

x

y and z okay

they say we have three different discs

d1 will be first d2 then d3 so this is

small this is

larger than that this is the

largest of all the three so this is the

current condition so checking for the

first move what does the first move say

disk one should be moved from peg x to

the peg z so peg x is nothing but source

this is auxiliary this is target or

destination

so i am starting with the first move

so here

it says

though

this should be moved to

x to z

which one the d1 okay

d3 right this will be moved to z so d1

will be here it will be removed right

so the next one

it says

move

disk 2 to x to y

so it is in x this is in y this is in z

what it says move though this 2 to y so

this 2 will come here disc 1 is already

existing there

and this 3 will be here so this is the

current situation when it is at the move

2

when it is at the move 3 how it will

look say for example we are creating the

same three packs here so x y z

fine it says

move disc one from z to y

so

while you do that uh disc two can have

disc one on top but it cannot be vice

versa we cannot place in this format

right

this is breaking rules you can do this

d2 is larger than d1 so it can take d1

on the top

so

xyz is here

so here we are i'm just putting this d1

on the d2 which is already existing and

d3 is as it is so step 3 let us move 3

is done if we go to move 4 what is says

right it will say

move disk 3 from x to z again so z is

empty x y z so currently

we have d1 d2 here it says move d3 which

is there in x to z

so d3 will be here

coming to the fifth move what it says

disk 1 from

y to x

so

according to the

situation

now we have to make this d1 move to x

d2

d3 if you could see here it is getting

settled obviously the next move will be

without thinking logically we can say

without going to this part

d3 is here d2 is here then d2 will be on

this so d2 will be present here d1

remains as it is in the seventh move

what happens

all the pegs that is y is also empty x

is having d1 so this d1 will be shifted

on to this particular stack right

d1 so it is there

now

all the source which was there d1 d2 d3

at the initial position is shifted to

the destination again if you could see

here d1 d2 d3 with the help of seven

moves so this is how average hanoi will

work

we have reached the last part of this

particular video that is summary let's

have a quick recap on the concepts which

we learnt in data structures and

algorithms in python so we started with

data structures introduction then we

learned different data structures that

is array how to create an array what is

an array how to implement in python

programming then followed by queue stack

linked list and concepts methods and

implementation as well

after that we learned regarding tree

data structure so tree data structure

had binary tree binary search tree

and we also learned how to create

traverse and then implement the same in

python

then we had graph data structure so we

learned introduction towards the graph

what is graph and we also implemented

using bfs and dfs algorithm so traversal

was made between two different

approaches breadth first search and

depth first search after that we learned

regarding hashing

so post that we started algorithmic

approaches so

first we started with algorithm analysis

how to find the time and space

complexity for an algorithm

then we started learning searching and

sorting algorithms so linear search

binary search quick sort incision sort

everything were taught

with the implementation in python

programming language then at the last we

learned regarding different programming

approaches we could follow in order to

solve the problem so we started with

divide and conquer followed by greedy

then dynamic approach right so all these

approaches were taught with examples

like merge sort prim's minimum spanning

tree and then we were taught with the

beautiful example of tower of hanoi we

implemented the same in python as well

as we analyzed the output for the same

so

all these concepts were covered in this

particular video hope this was helpful

for you

will meet up in the next video until

then thank you

if you haven't subscribed for our

channel yet i would request you to hit

the subscribe button and turn on

notification bell so that you don't miss

any new updates or video releases from

great learning if you enjoy this video

show us some love and do like this video

knowledge increases by sharing so make

sure you share this video with your

friends and colleagues make sure you

comment on this video any queries or

suggestions i'll be more than happy to

respond to all of them