ABDULLAHIUMAR DEPARTMENTOFMATHEMATI

CS

SUMMARYOFCSC204(
DATASTRUCTURE)

BY

ABDULLAHIUMAR
DEPARTMENTOFMATHEMATI
CS

THECOURSEI
SDI
VIDEDI
NTOTWOPARTS;
THI
SISTHETHEORYOFTHECOURSE
THAT'
SFI
RSTPART,
WHI
LETHESECONDPARTI
NCLUDESTHEFOLLOWI
NG
HEADI
NGS.

 How t
hef
oll
owi
ngl
inearandNon-
li
nearDat
aSt
ruct
uresar
erepr
esent
edor
i
mpl
ement
edAl
soHowel
ement
sar
eaddedorr
emov
ed
 St
ack
 Queue
 Dequeue
 Ar
ray
 Si
ngl
e,Doubl
eandCi
rcul
arl
inkedl
ist
 Tr
ee
 Gr
aph
 Sor
ti
ngandsear
chi
ngal
gor
it
hm
 Conv
ert
ingi
nfi
xtopostf
ixexpr
essi
on
 Ev
aluat
ingpostf
ixexpr
essi
on
 Thei
nor
der
,pr
eor
derandpostor
dert
rav
ersal
oft
het
ree

Ony
ourown,y
oucanr
eadt
hef
ir
stpar
tthat
'st
heor
yoft
hecour
seandunder
standor
memor
izei
twi
thoutanypr
obl
em,whi
let
hesecondpar
tneedbet
terunder
standi
ng
becausei
t'
ssomeki
ndofoper
ati
ons,
algor
it
hmsandcomput
ati
ons

①
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

Whati
sDat
aSt
ruct
ure
Adat
ast
ruct
urei
sawayofor
gani
zi
ngdat
ainacomput
ersot
hati
tcanbeaccessed
andmani
pul
atedef
fi
ci
ent
ly.Somecommonexampl
esofdat
ast
ruct
uresar
ear
ray
s,
l
i
nkedl
i
sts,
stacks,
queues,
trees,
andgr
aphs.Thechoi
ceofdat
ast
ruct
urei
simpor
tant
because i
taf
fect
s how qui
ckl
y and ef
fi
cient
lyt
he dat
a can be accessed and
mani
pul
ated.
Adat
ast
ruct
urei
sacol
l
ect
ionofdat
athati
sor
gani
zedi
nawayt
hatal
l
owsi
ttobe
accessedandmodi
fi
edef
fi
cient
ly.Thet
hreemai
npr
oper
ti
esofadat
ast
ruct
urear
e:
 St
ruct
ure-Thewayt
hedat
aisor
gani
zed
 Oper
ati
ons-Theoper
ati
onst
hatcanbeper
for
medont
hedat
a
 Ef
fi
ciency-Theamountoft
imeandspacer
equi
redt
oper
for
mtheoper
ati
ons
Abst
ractDat
aTy
pe(
ADT)
Anabst
ractdat
aty
pe(
ADT)i
sagener
alconceptt
hatdef
inesadat
ast
ruct
urewi
thout
speci
fyi
ngt
hedet
ail
sofi
tsi
mpl
ement
ati
on.I
not
herwor
ds,i
tdef
inest
heoper
ati
ons
t
hatcan be per
for
med on t
he dat
a st
ruct
ure,butnothow t
hose oper
ati
ons ar
e
i
mpl
ement
ed.AnADTi
sli
keabl
uepr
intf
oradat
ast
ruct
ure,wi
thoutt
hespeci
fi
csof
howi
tisact
ual
l
ybui
l
t.I
tal
l
owsust
ofocusont
heoper
ati
onsandf
unct
ional
i
tyoft
he
dat
ast
ruct
ure,
wit
houtwor
ryi
ngabouthowi
tisi
mpl
ement
ed.
1.Di
ff
erent
iat
eBet
weenLi
nearandNon-
li
nearDat
aSt
ruct
uresandPr
ovi
deExampl
es
ofEach
Li
neardat
ast
ruct
uresar
ethosei
nwhi
cht
hedat
ael
ement
sar
ear
rangedi
nal
i
near
or
der
,meani
ngt
hateachel
ementi
sconnect
edt
othenexti
nsomeway
.Forexampl
e,
anar
rayorl
i
nkedl
i
sti
sal
i
neardat
ast
ruct
ure.Non-
li
neardat
ast
ruct
ures,ont
heot
her
hand,donothav
eal
i
nearr
elat
ionshi
pbet
weent
hedat
ael
ement
s.I
nst
ead,t
heyar
e
ar
rangedi
namor
ecompl
exst
ruct
ure,
li
keat
reeorgr
aph.
Li
neardat
ast
ruct
uresar
ever
yef
fi
cientwheni
tcomest
oaccessi
ngel
ement
sina
sequent
ialor
der
.Howev
er,t
heycanbesl
owerwheni
tcomest
orandom access.Non-
l
i
neardat
ast
ruct
uresar
emor
efl
exi
blewheni
tcomest
oaccessi
ngel
ement
s,butt
hey
canbemor
ecompl
ext
oimpl
ementandmai
ntai
n.
Oneoft
hemai
nadv
ant
agesofl
i
neardat
ast
ruct
uresi
sthatt
heyar
eeasi
ert
osear
ch

②
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

andsor
t.Thi
sisbecauset
heel
ement
sar
est
oredi
nasequent
ialor
der
,whi
chmakesi
t
easyt
ofi
ndt
heel
ementy
ou'
rel
ooki
ngf
or.Non-
li
neardat
ast
ruct
uresar
emor
ecompl
ex
t
osear
chandsor
t,becauset
heel
ement
sar
enotst
oredi
nasequent
ial
order
.
Anot
heradv
ant
ageofl
i
neardat
ast
ruct
uresi
sthatt
heyusel
essmemor
y.Thi
sis
becauset
heel
ement
sar
est
oredi
nasi
ngl
e,cont
iguousmemor
ylocat
ion.Non-
li
near
dat
ast
ruct
ures,
ont
heot
herhand,
canusemor
ememor
ybecauset
heel
ement
sar
enot
st
oredi
nacont
iguousmemor
ylocat
ion.Doest
hatmakesense?
Forl
i
neardat
ast
ruct
ures,
wecanusear
ray
s,l
i
sts,
stacks,
andqueuesasexampl
es.For
non-
li
neardat
ast
ruct
ures,
wecanuset
rees,
graphs,
andhasht
abl
es.
Oper
ati
onsappl
iedonl
ineardat
ast
ruct
ure:
Thef
oll
owi
ngl
i
stofoper
ati
onsappl
i
edonl
i
neardat
ast
ruct
ures
1.Addanel
ement
2.Del
eteanel
ement
3.Tr
aver
se
4.Sor
tthel
i
stofel
ement
s
5.Sear
chf
oradat
ael
ement
Oper
ati
onsappl
iedonnon-
li
neardat
ast
ruct
ures:
Thef
oll
owi
ngl
i
stofoper
ati
onsappl
i
edonnon-
li
neardat
ast
ruct
ures.
1.Addel
ement
s
2.Del
eteel
ement
s
3.Di
spl
ayt
heel
ement
s
4.Sor
tthel
i
stofel
ement
s
5.Sear
chf
oradat
ael
ement
Di
ff
erencebet
weenRecur
sionandI
ter
ati
on:
 Af
unct
ioni
ssai
dtober
ecur
siv
eifi
tcal
l
sit
sel
fagai
nandagai
nwi
thi
nit
sbody
wher
easi
ter
ati
vef
unct
ionsar
eloopbasedi
mper
ati
vef
unct
ions.
 Recur
sionusesst
ackwher
easi
ter
ati
ondoesnotusest
ack.
 Recur
sionusesmor
ememor
ythani
ter
ati
onasi
tsconcepti
sbasedonst
acks.
 Recur
sioni
scompar
ati
vel
ysl
owert
hani
ter
ati
onduet
oov
erheadcondi
ti
onof
mai
ntai
ningst
acks.

③
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

 Recur
sionmakescodesmal
l
erandi
ter
ati
onmakescodel
onger
.
 I
ter
ati
ont
ermi
nat
eswhent
hel
oop-
cont
inuat
ioncondi
ti
onf
ail
swher
easr
ecur
sion
t
ermi
nat
eswhenabasecasei
srecogni
zed.
 Whi
l
eusi
ngr
ecur
sionmul
ti
pleact
ivat
ionr
ecor
dsar
ecr
eat
edonst
ackf
oreach
cal
lwher
easi
nit
erat
ionev
ery
thi
ngi
sdonei
noneact
ivat
ionr
ecor
d.
 I
nfi
nit
erecur
sioncancr
asht
hesy
stem wher
easi
nfi
nit
eloopi
ngusesCPUcy
cles
r
epeat
edl
y.
 Recur
sionusessel
ect
ionst
ruct
urewher
easi
ter
ati
onusesr
epet
it
ionst
ruct
ure.
St
ack
Ast
acki
sacont
ainerofobj
ect
sthatar
einser
tedandr
emov
edaccor
dingt
othel
ast
-i
n
f
ir
st-
out(
LIFO)pr
inci
ple.I
nthepushdownst
acksonl
ytwooper
ati
onsar
eal
l
owed:push
t
hei
tem i
ntot
hest
ack,andpopt
hei
tem outoft
hest
ack.Ast
acki
sal
i
mit
edaccess
dat
ast
ruct
ure-el
ement
scanbeaddedandr
emov
edf
rom t
hest
ackonl
yatt
het
op.
Pushaddsani
tem t
othet
opoft
hest
ack,
popr
emov
est
hei
tem f
rom t
het
op.
SomeOper
ati
onsonSt
ack
 Theaddoper
ati
onoft
hest
acki
scal
l
edpushoper
ati
on
 Thedel
eteoper
ati
oni
scal
l
edaspopoper
ati
on.
 Pushoper
ati
ononaf
ull
stackcausesst
ackov
erf
low.
 Popoper
ati
ononanempt
yst
ackcausesst
ackunder
fl
ow.
 SPi
sapoi
nter
,whi
chi
susedt
oaccesst
het
opel
ementoft
hest
ack,
andi
ts-
1if
t
hest
acki
sempt
y.
 I
fyoupushel
ement
sthatar
eaddedatt
het
opoft
hest
ack;
 I
nthesamewaywhenwepopt
heel
ement
s,t
heel
ementatt
het
opoft
hest
ack
i
sdel
eted.
St
ackAppl
icat
ions:
1.St
acki
susedbycompi
l
erst
ocheckf
orbal
anci
ngofpar
ent
heses,br
acket
sand
br
aces.
2.St
acki
susedt
oev
aluat
eapost
fi
xexpr
essi
on.
3.St
acki
susedt
oconv
ertani
nfi
xexpr
essi
oni
ntopost
fi
x/pr
efi
xfor
m.
4.I
nrecur
sion,al
lint
ermedi
atear
gument
sandr
etur
nval
uesar
est
oredont
he

④
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

pr
ocessor
’sst
ack.
5.Dur
ingaf
unct
ioncal
lther
etur
naddr
essandar
gument
sar
epushedont
oast
ack
andonr
etur
ntheyar
epoppedof
f.
6.Dept
hfi
rstsear
chusesast
ackdat
ast
ruct
uret
ofi
ndanel
ementf
rom agr
aph.
I
nfi
xandPost
fi
xExpr
essi
on
AnI
nfi
xExpr
essi
on(
orI
nfi
xNot
ati
on)i
schar
act
eri
zedbyamat
hexpr
essi
onwher
ein
t
heoper
ator
sar
epl
acedbet
weenoper
ands,
(asi
n2+3)
.
Ast
henamei
mpl
i
es,aPost
fi
xExpr
essi
on(
orPost
fi
xNot
ati
on,orRev
ersePol
i
sh
Not
ati
on)i
schar
act
eri
zedbyamat
hexpr
essi
onwher
eint
heoper
ator
sar
epl
acedaf
ter
t
hei
roper
ands(
2+3i
nfi
xbecomes23+post
fi
x).
Somer
ulesandst
epsonHowt
oConv
ertI
nfi
xtoPost
fi
xUsi
ngSt
ack
Oper
ator Sy
mbol Pr
ecedence Associ
ati
vi
ty
Exponent ^ 4 Ri
ghtt
oLef
t
Mul
ti
pli
cat
ion * 3 Lef
ttoRi
ght
Di
vi
si
on / 3 Lef
ttoRi
ght
Addi
ti
on + 2 Lef
ttoRi
ght
Subt
ract
ion - 2 Lef
ttoRi
ght

 I
fthet
okeni
sanoper
and,appendi
ttot
hepost
fi
xexpr
essi
on.Oper
andsal
way
s
appeari
nthesameor
deri
nthepost
fi
xexpr
essi
onast
heydo i
nthei
nfi
x
expr
essi
on.
I
fthet
okeni
sanopeni
ngpar
ent
hesi
s,pushi
ttot
hest
ack.Thi
smar
kst
he
begi
nni
ngofanexpr
essi
ont
hatshoul
dbeev
aluat
edsepar
atel
y.
 I
fthet
okeni
sacl
osi
ngpar
ent
hesi
s,unt
ilanopeni
ngpar
ent
hesi
sisencount
ered
att
het
opoft
hest
ack,popeachoper
atorf
rom t
hest
ackandappendt
othe
post
fi
xexpr
essi
on.Thi
smar
kst
heendoft
heoper
andsandoper
ator
slocat
ed
wi
thi
nthecur
rentsetofpar
ent
heses.
 I
fthet
okeni
sanoper
atorandi
thasgr
eat
erpr
ecedencet
hant
heoper
atoront
he
t
opoft
hest
ack,
pusht
het
okent
othest
ack.
 I
fthet
okeni
sanoper
atorandi
thasl
owerpr
ecedencet
hant
heoper
atoront
he

⑤
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

t
opoft
hest
ack,
unt
ilt
heoper
atoront
opoft
hest
ackhasl
owerpr
ecedencet
han
t
het
oken,orunt
ilt
hest
acki
sempt
y,popeachoper
atorf
rom t
hest
ackand
appendt
hem t
othepost
fi
xexpr
essi
on.Thenpusht
hecur
rentt
okent
othest
ack.
 I
fthet
okeni
sanoper
atorandi
thast
hesamepr
ecedenceast
heoper
atoront
he
t
opoft
hest
ack,andt
heoper
atoront
opoft
hest
acki
slef
t-
to-
ri
ghtassoci
ati
ve,
unt
ilt
heoper
atoront
opoft
hest
ackhasl
owerpr
ecedencet
hant
het
oken,or
unt
ilt
hest
acki
sempt
y,popeachoper
atorf
rom t
hest
ackandappendt
hem t
o
t
hepost
fi
xexpr
essi
on.Thenpusht
hecur
rentt
okent
othest
ack.
 I
fthet
okeni
sanoper
atorandi
thast
hesamepr
ecedenceast
heoper
atoront
he
t
opoft
hest
ack,butt
heoper
atoront
opoft
hest
acki
sri
ght
-t
o-l
eftassoci
ati
ve,
pusht
hecur
rentt
okent
othest
ack.
Fi
nal
l
y,onceal
loft
hei
nfi
xtokenshav
ebeenev
aluat
ed,popanyr
emai
ningoper
ator
s
f
rom t
hest
ack,
onatat
ime,
andappendeachoft
hem t
othepost
fi
xexpr
essi
on
2.WhatI
sThePr
imar
yDi
ff
erenceBet
weenAnAr
rayAndALi
nkedLi
stI
nTheCont
ext
OfDat
aSt
ruct
ures?
Ar
ray
sar
est
oredi
nacont
iguousbl
ockofmemor
y,whi
l
eli
nkedl
i
stsar
emadeupof
nodest
hatar
escat
ter
edt
hroughoutmemor
y.Thi
smeanst
hatar
ray
sar
emuchf
ast
er
t
oaccesst
hanl
i
nkedl
i
sts,butl
i
nkedl
i
stsar
emor
efl
exi
bleandcangr
ow orshr
ink
wi
thoutr
eal
l
ocat
ingmemor
y.Ar
ray
sal
sohav
eaf
ixedsi
ze,whi
l
eli
nkedl
i
stscanbe
r
esi
zeddy
nami
cal
l
y.
Si
ncear
ray
sar
est
oredi
nacont
iguousbl
ockofmemor
y,t
heycanbeaccessedv
ery
qui
ckl
y,becauset
hecomput
erknowsexact
lywher
ein memor
ytof
ind t
hedat
a.
Howev
er,
ify
ouwantt
oaddanewel
ementt
oanar
ray
,youhav
etor
eal
l
ocat
etheent
ir
e
ar
ray
,whi
chcanbet
ime-
consumi
ng.Ont
heot
herhand,
sincel
i
nkedl
i
stsar
enotst
ored
i
nacont
iguousbl
ockofmemor
y,t
heycanbemor
eeasi
l
yresi
zed.Howev
er,because
t
hedat
aisscat
ter
edt
hroughoutmemor
y,i
ttakesl
ongert
oaccesst
heel
ement
s.
Supposey
ou'
rewr
it
ingapr
ogr
am t
hatneedst
okeept
rackofal
argenumberofr
ecor
ds,
l
i
kecust
omeri
nfor
mat
ioni
nadat
abase.I
nthi
scase,al
i
nkedl
i
stmi
ghtbeabet
ter
choi
ce,becausei
twoul
dbeeasi
ert
oaddandr
emov
erecor
dsasneeded.Howev
er,i
f
y
ouwer
ewr
it
ingapr
ogr
am t
hatneededt
osear
cht
hrought
her
ecor
dsv
eryqui
ckl
y,an

⑥
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

ar
raymi
ghtbeabet
terchoi
ce.So,
itr
eal
l
ydependsont
hespeci
fi
crequi
rement
sofy
our
pr
ogr
am.
Al
i
nkedl
i
sti
sady
nami
cdat
ast
ruct
urebecausei
tcangr
oworshr
inkasneeded.Thi
sis
i
ncont
rastt
oanar
ray
,whi
chi
sast
ati
cdat
ast
ruct
ure.Anar
rayhasaf
ixedsi
ze,andi
t
can'
tbeeasi
l
yresi
zed.Thef
actt
hatl
i
nkedl
i
stsar
edy
nami
cmakest
hem v
eryusef
ulf
or
appl
i
cat
ionswher
etheamountofdat
aisconst
ant
lychangi
ng.
Sel
f-
ref
erent
ialmeanst
hateachnodei
nal
i
nkedl
i
stcont
ainsapoi
ntert
othenextnode
i
nthel
i
st.So,wheny
ou'
rel
ooki
ngatanodei
nal
i
nkedl
i
st,y
oucanal
way
sfol
l
owt
he
poi
ntert
othenextnodei
nthel
i
st.Thi
sisdi
ff
erentf
rom anar
ray
,wher
eyouhav
eto
accesst
heel
ement
ssequent
ial
l
y,st
art
ingf
rom t
hef
ir
stel
ement
.Thesel
f-
ref
erent
ial
pr
oper
tyofl
i
nkedl
i
stsmakest
hem v
eryusef
ulf
ort
hingsl
i
kel
i
nkedl
i
sts,wher
eyou
needt
obeabl
etomov
efr
eel
ythr
oughoutt
hel
i
st.
Compar
isonbet
weenAr
rayandl
inkedl
ist
Ar
ray Li
nkedl
ist
Si
zeofanar
rayi
sfi
xed Si
zeoft
hel
i
stnotf
ixed
Memor
yisal
l
ocat
edf
rom st
ack Memor
yisal
l
ocat
edf
rom heap
I
tisnecessar
ytospeci
fyt
henumberof I
tisnotnecessar
ytospeci
fyt
henumber
el
ement
sdur
ingdecl
arat
ion(
i.
e.,dur
ing of el
ement
s dur
ing decl
arat
ion (
i.
e.,
compi
l
e). memor
yisal
l
ocat
eddur
ingr
unt
ime)
.
I
toccupi
esl
essmemor
ythanal
i
nkedl
i
st I
toccupi
esmor
ememor
y.
f
ort
hesamenumberofel
ement
s.
I
nser
ti
ng new el
ement
satt
hef
ronti
s I
nser
ti
nganew el
ementatanyposi
ti
on
pot
ent
ial
l
y expensi
ve because exi
sti
ng canbecar
ri
edouteasi
l
y.
el
ement
sneedt
obeshi
ft
edov
ert
omake
r
oom.
Del
eti
nganel
ementf
rom anar
rayi
snot Del
eti
nganel
ementi
spossi
ble.
possi
ble.

⑦
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

Tr
adeof
fsbet
weenl
inkedl
ist
sandar
ray
s
Feat
ure Ar
ray
s Li
nkedl
ist
s
sequent
ial
access ef
fi
cient ef
fi
cient
Random access ef
fi
cient i
nef
fi
cient
Resi
gni
ng i
nef
fi
cient ef
fi
cient
El
ementr
ear
rangi
ng i
nef
fi
cient ef
fi
cient
ov
erhead per none 1or2l
i
nks
el
ement
s

3.Expl
ainTheConceptOfDy
nami
cAr
ray
sAndThei
rAdv
ant
agesOv
erSt
ati
cAr
ray
s.
Pr
ovi
deAnExampl
eOfA Dy
nami
cAr
rayAndDi
scussA Scenar
ioWher
eDy
nami
c
Ar
ray
sAr
ePar
ti
cul
arl
yUsef
ul.
Dy
nami
car
ray
sar
ear
ray
sthatcanber
esi
zedasneeded,whi
l
est
ati
car
ray
shav
ea
f
ixedsi
ze.Thekeyadv
ant
ageofdy
nami
car
ray
sist
hatt
hey
'r
emor
efl
exi
bleand
ef
fi
cient
.Becauseady
nami
car
raycanber
esi
zed,
youdon'
tneedt
oknowt
heexactsi
ze
oft
hear
rayi
nadv
ance.Thi
scanbev
eryusef
uli
nsi
tuat
ionswher
etheamountofdat
a
i
sunknownorconst
ant
lychangi
ng.I
naddi
ti
on,dy
nami
car
ray
scanbemor
eef
fi
cient
becauset
heydon'
twast
espacebyal
l
ocat
ingext
ramemor
ythat
'snotneeded.
Oneoft
hemai
ndr
awbacksi
sthatt
heycanbemor
edi
ff
icul
ttoi
mpl
ementanduset
han
st
ati
car
ray
s.Thi
sisbecausey
ouneedt
okeept
rackoft
hesi
zeoft
hear
rayandr
esi
zei
t
asneeded.I
naddi
ti
on,dy
nami
car
ray
scanbesl
owert
hanst
ati
car
ray
sbecauseoft
he
ext
rawor
krequi
redt
oresi
zet
hem.Howev
er,
inmanycasest
hef
lexi
bil
i
tyandef
fi
ciency
ofdy
nami
car
ray
sout
wei
ght
hedownsi
des.
Onecommonexampl
eofady
nami
car
rayi
sal
i
nkedl
i
st.Al
i
nkedl
i
sti
sadat
ast
ruct
ure
t
hatcont
ainsal
i
stofnodes,
wher
eeachnodecont
ainsadat
ael
ementandapoi
ntert
o
t
henextnodei
nthel
i
st.Becauseal
i
nkedl
i
sti
sdy
nami
c,y
oucanaddorr
emov
enodes
f
rom t
hel
i
stwi
thouthav
ingt
oreal
l
ocat
etheent
ir
ear
ray
.Thi
smakesl
i
nkedl
i
stsv
ery
usef
ulf
ort
hingsl
i
kequeues,
wher
ethesi
zeoft
hequeuecanchangeov
ert
ime.
Oneex
ampl
eisi
nav
ideogame.Supposey
ou'
remaki
ngav
ideogamet
hathasl
otsof
di
ff
erentt
ypesofobj
ect
s,l
i
kemonst
ers,weapons,andpot
ions.I
nthi
scase,y
oucoul
d

⑧
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

useady
nami
car
rayt
ost
oret
heobj
ect
s,soy
oucanaddorr
emov
eobj
ect
sasneeded
wi
thoutwor
ryi
ngaboutr
unni
ngoutofspace.
4.Descr
ibeTheConceptOfAMul
ti
dimensi
onalAr
rayAndPr
ovi
deAnExampl
eOfA
Two-
dimensi
onalAr
ray
.Di
scuss A Pr
act
icalAppl
icat
ion Wher
e Two-
dimensi
onal
Ar
ray
sAr
eCommonl
yUsed.
Amul
ti
dimensi
onalar
rayi
sanar
rayt
hatcont
ainsmor
ethanonedi
mensi
on.I
not
her
wor
ds,i
t'
sanar
rayofar
ray
s.Forexampl
e,at
wo-
dimensi
onalar
rayi
sanar
rayt
hat
cont
ainsr
owsandcol
umnsofel
ement
s.Eachel
ementi
nthear
raycanbeaccessed
usi
ngt
woi
ndi
ces,
onef
ort
her
owandonef
ort
hecol
umn.
Oneadv
ant
agei
sthatt
heycanmakei
teasi
ert
ovi
sual
i
zeandmani
pul
atecompl
exdat
a
st
ruct
ures.Theycanal
somakei
teasi
ert
oor
gani
zeandaccessdat
a.I
naddi
ti
on,
mul
ti
dimensi
onalar
ray
scanbemor
eef
fi
cientt
hanusi
ngmul
ti
pleone-
dimensi
onal
ar
ray
s.
Forexampl
e,av
ideogamemi
ghtuseamul
ti
dimensi
onalar
rayt
ost
oret
heposi
ti
onsof
al
ltheobj
ect
sint
hegame.Eachobj
ectcoul
dbest
oredasar
owandcol
umnposi
ti
oni
n
t
hear
ray
,al
ongwi
thot
heri
nfor
mat
ionaboutt
heobj
ect
.Int
hisway
,thegamecan
qui
ckl
yandef
fi
cient
lyaccesst
heposi
ti
onofanyobj
ecti
nthegame.
Onecommonappl
i
cat
ionf
ort
wo-
dimensi
onalar
ray
sisdi
git
ali
magepr
ocessi
ng.For
exampl
e,adi
git
ali
magecanber
epr
esent
edasat
wo-
dimensi
onalar
ray
,wi
theach
el
ementi
nthear
rayr
epr
esent
ingapi
xeli
nthei
mage.Usi
ngat
wo-
dimensi
onalar
ray
makesi
teasyt
omani
pul
atet
hei
mage,suchasr
otat
ingi
torappl
yi
ngaf
il
ter
.Inf
act
,
manyi
mageedi
ti
ngsof
twar
epackagesl
i
kePhot
oshopuset
wo-
dimensi
onalar
ray
sto
r
epr
esenti
mages.
Anot
hercommonappl
i
cat
ionoft
wo-
dimensi
onalar
ray
sisi
ndat
avi
sual
i
zat
ion.For
exampl
e,at
wo-
dimensi
onal
arr
aycanbeusedt
ocr
eat
eascat
terpl
ot,
whi
chi
sat
ypeof
gr
apht
hatshowst
her
elat
ionshi
pbet
weent
wov
ari
abl
es.Eachv
ari
abl
eisr
epr
esent
ed
byanaxi
sint
hepl
ot,
andeachdat
apoi
nti
srepr
esent
edbyadotont
hepl
ot.
Anot
herappl
i
cat
ionoft
wo-
dimensi
onal
arr
aysi
sinv
ideogamegr
aphi
cs.Forexampl
e,a
t
wo-
dimensi
onalar
raycanbeusedt
ost
oret
heposi
ti
onsofal
ltheobj
ect
sinav
ideo
game,l
i
keenemi
es,power
-ups,andt
hepl
ayer
.Thegamecant
henuset
hear
rayt
o

⑨
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

cal
cul
atewher
etheobj
ect
sshoul
dbedi
spl
ayedont
hescr
een.Thi
smakesi
teasyt
o
cr
eat
edy
nami
c,f
ast
-pacedgameswi
thl
otsofmov
ingobj
ect
s.
5.Expl
ainTheConceptOfASi
ngl
yLi
nkedLi
stAndADoubl
yLi
nkedLi
st.Descr
ibeThe
Adv
ant
agesAndDi
sadv
ant
agesOfEachTy
pe.Pr
ovi
deAnExampl
eOfA Scenar
io
Wher
eYouWoul
dChooseOneOv
erTheOt
her
.
Asi
ngl
yli
nkedl
i
sti
sal
i
stofnodeswher
eeachnodepoi
ntst
othenextnodei
nthel
i
st.
Thi
smeanst
hatt
henodesar
eli
nkedt
oget
heri
nachai
n,andy
oucanonl
ymov
e
f
orwar
dthr
ought
hel
i
st,st
art
ingf
rom t
hef
ir
stnode.Adoubl
yli
nkedl
i
sti
ssi
mil
ar,but
eachnodeal
sopoi
ntst
othepr
evi
ousnodei
nthel
i
st.Thi
smakesi
tpossi
blet
omov
e
bot
hfor
war
dandbackwar
dthr
ought
hel
i
st.
Asi
ngl
yli
nkedl
i
stonl
yhasonepoi
nterpernode,whi
chpoi
ntst
othenextnodei
nthe
l
i
st.Thi
smeanst
hati
fyouwantt
oaccessaspeci
fi
cnode,y
ouhav
etost
artf
rom t
he
f
ir
stnodeandmov
ethr
ought
hel
i
stunt
ily
our
eacht
henodey
ou'
rel
ooki
ngf
or.Thi
scan
besl
owf
orl
argel
i
sts.Adoubl
yli
nkedl
i
sthast
wopoi
nter
spernode,
whi
chpoi
ntt
othe
nextandpr
evi
ousnodesi
nthel
i
st.Thi
smakesi
tpossi
blet
omov
ebot
hfor
war
dand
backwar
dthr
ought
hel
i
st,
whi
chcanbef
ast
erf
orsomeoper
ati
ons.
Themai
nadv
ant
ageofasi
ngl
yli
nkedl
i
sti
sthati
t'
ssi
mpl
etoi
mpl
ementanddoesn'
t
r
equi
remuchmemor
y.Howev
er,t
hemai
ndi
sadv
ant
agei
sthaty
oucanonl
ymov
e
t
hrought
hel
i
sti
nonedi
rect
ion.Wi
thadoubl
yli
nked l
i
st,y
oucanmov
einbot
h
di
rect
ions,whi
chcanbeusef
ulf
orsomeappl
i
cat
ions.Howev
er,i
t'
smor
ecompl
i
cat
ed
t
oimpl
ementandr
equi
resmor
ememor
y.
Ther
ear
eaf
ewot
heradv
ant
agesofadoubl
yli
nkedl
i
stcompar
edt
oasi
ngl
yli
nkedl
i
st.
Fi
rst
,it
'seasyt
oinser
tanddel
etenodesf
rom adoubl
yli
nkedl
i
stbecausey
oucan
si
mpl
ychanget
hepoi
nter
stot
hepr
evi
ousandnextnodes.Second,
adoubl
yli
nkedl
i
st
canbet
rav
ersedi
nbot
hdi
rect
ionswi
thoutkeepi
ngt
rackoft
hecur
rentposi
ti
oni
nthe
l
i
st,whi
chmakesi
teasyt
ouse.Fi
nal
l
y,adoubl
yli
nkedl
i
sti
smor
eef
fi
cientf
orcer
tai
n
al
gor
it
hms,
suchast
he"
dept
h-f
ir
stsear
ch"al
gor
it
hm.
I
nasi
ngl
yli
nkedl
i
st,i
fanodebecomescor
rupt
ed,i
tcanbedi
ff
icul
ttor
epai
rthel
i
st
becausey
ouhav
etomanual
l
yfi
ndandf
ixt
hebr
okenl
i
nk.Howev
er,i
nadoubl
yli
nked
l
i
st,
youcansi
mpl
yfol
l
owt
hepr
evi
ousandnextpoi
nter
stof
indt
hebr
okenl
i
nkandf
ixi
t.

⑩
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

Thi
smakesdoubl
yli
nkedl
i
stsmor
erobustandl
essl
i
kel
ytobecomecor
rupt
ed.
Adoubl
yli
nkedl
i
stusesmor
ememor
ythanasi
ngl
yli
nkedl
i
stbecauseeachnode
needst
ost
oret
wopoi
nter
sinst
eadofj
ustone.Thi
sext
ramemor
yusagecanbea
si
gni
fi
cantdi
sadv
ant
agei
nappl
i
cat
ionswher
ememor
yisl
i
mit
ed.
Oneexampl
eisi
fyou'
rewor
kingwi
thal
argedat
asett
haty
ouonl
yneedt
oaccess
sequent
ial
l
y.I
nthi
scase,
asi
ngl
yli
nkedl
i
stwoul
dbeagoodchoi
cebecausei
t'
ssi
mpl
e
andef
fi
cient
.Howev
er,i
fyouneedt
orandoml
yaccessel
ement
sint
hedat
aset
,a
doubl
yli
nkedl
i
stwoul
dbeabet
terchoi
cebecausei
tmakesi
teasyt
oaccessany
el
ementi
nthel
i
st.
6.Descr
ibeTheConceptOfACi
rcul
arLi
nkedLi
stAndI
tsCommonAppl
icat
ions.What
Adv
ant
agesDoesACi
rcul
arLi
nkedLi
stOf
ferOv
erASt
andar
dSi
ngl
yLi
nkedLi
st?
Aci
rcul
arl
i
nkedl
i
sti
sat
ypeofl
i
nkedl
i
sti
nwhi
cht
hel
astnodepoi
ntsbackt
othef
ir
st
node,cr
eat
ingal
oop.Thi
scanbeusef
uli
nsi
tuat
ionswher
eyouwantt
okeept
rackof
t
hemostr
ecenti
tem i
nthel
i
st,orwheny
ouwantt
oav
oidhav
ingt
oexpl
i
cit
lymanage
t
heendoft
hel
i
st.Commonappl
i
cat
ionsofci
rcul
arl
i
nkedl
i
stsi
ncl
uder
ingbuf
fer
s,
wher
edat
aisconst
ant
lybei
ngaddedandr
emov
edf
rom t
hel
i
sti
naf
ir
st-
in,f
ir
st-
out
(
FIFO)or
der
.Ci
rcul
arl
i
nkedl
i
stscanal
sobeusedi
nqueuesanddeques,wher
eit
ems
ar
eaddedandr
emov
edf
rom bot
hendsoft
hel
i
st.
Oneoft
hemai
nadv
ant
agesofaci
rcul
arl
i
nkedl
i
stov
erast
andar
dsi
ngl
yli
nkedl
i
sti
s
t
hati
tel
i
minat
est
heneedt
okeept
rackoft
heendoft
hel
i
st.Thi
scanbeasi
gni
fi
cant
adv
ant
age i
n si
tuat
ions wher
ethe l
i
sti
s const
ant
lygr
owi
ng and shr
inki
ng,as i
t
el
i
minat
est
heneedt
oupdat
easpeci
al"
tai
l
"poi
nterev
eryt
imeanodei
saddedor
r
emov
edf
rom t
hel
i
st.Ci
rcul
arl
i
nkedl
i
stsal
sot
endt
obemor
eef
fi
cienti
nter
msof
memor
yusage,
ast
heydon'
tneedt
oreser
veext
raspacef
ort
het
ail
poi
nter
.
Anot
heradv
ant
ageofci
rcul
arl
i
nkedl
i
stsi
sthatt
heycanbet
rav
ersedi
nbot
hdi
rect
ions,
wi
thoutt
heneedf
orspeci
al"
head"and"
tai
l
"poi
nter
s.Thi
smakesci
rcul
arl
i
nkedl
i
sts
wel
l
-sui
tedf
orappl
i
cat
ionsl
i
kest
acks,wher
eit
emsar
eaddedandr
emov
edf
rom t
he
sameendoft
hel
i
st,
andf
ori
mpl
ement
ingdoubl
e-endedqueues(
deques)
.
Onecommonappl
i
cat
ionofci
rcul
arl
i
nkedl
i
stsi
singar
bagecol
l
ect
ioni
npr
ogr
ammi
ng
l
anguagesl
i
keJav
aandC#.Gar
bagecol
l
ect
ioni
sapr
ocesst
hatf
reesupmemor
ythat

11
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

i
snol
ongerbei
ngusedbyt
hepr
ogr
am.Thi
sisdonebyt
raci
ngt
hrought
hepr
ogr
am'
s
dat
ast
ruct
ures,l
ooki
ngf
orobj
ect
sthatar
enol
ongerbei
ngr
efer
encedbyanyot
her
obj
ect
s.Ci
rcul
arl
i
nkedl
i
stsar
eof
tenusedt
orepr
esentt
hedat
ast
ruct
urest
hatar
e
bei
ngt
raceddur
inggar
bagecol
l
ect
ion.Thi
sisbecauseci
rcul
arl
i
nkedl
i
stsmakei
teasy
t
otr
aver
set
hel
i
stf
rom anygi
vennode,
whi
chi
sakeyr
equi
rementf
oref
fi
cientgar
bage
col
l
ect
ion.
Anot
hercommonappl
i
cat
ionofci
rcul
arl
i
nkedl
i
stsi
sini
mpl
ement
ingf
il
esy
stems.Fi
l
e
sy
stemsar
eusedt
ost
oreandor
gani
zef
il
esonacomput
er.Theyuseat
ree-
li
ke
st
ruct
uret
orepr
esentt
hehi
erar
chyofdi
rect
ori
esandf
il
es,wi
theachdi
rect
oryorf
il
e
r
epr
esent
edbyanodei
nthet
ree.Ci
rcul
arl
i
nkedl
i
stsar
eof
tenusedt
orepr
esentt
hel
i
st
ofchi
l
drenf
oreachnodei
nthef
il
esy
stem t
ree.Thi
smakesi
teasyt
onav
igat
ethet
ree
andf
indt
hef
il
esanddi
rect
ori
est
hatar
est
oredwi
thi
nit
.
7.Expl
ainTheConceptOfAQueueDat
aSt
ruct
ureAndI
tsKeyPr
oper
ti
es.Pr
ovi
deAn
Exampl
eOfAReal
-wor
ldScenar
ioWher
eAQueueI
sCommonl
yUsed.Descr
ibeTwo
CommonOper
ati
onsOnAQueueAndThei
rSi
gni
fi
cance.
Aqueuei
sadat
ast
ruct
uret
hati
susedt
ost
orei
temsi
naf
ir
st-
in,
fir
st-
out(
FIFO)or
der
.
Thatmeanst
hatt
hei
temst
hatar
eaddedt
othequeuef
ir
star
eal
sot
heonest
hatar
e
r
emov
edf
ir
st.Somecommonr
eal
-wor
ldexampl
esofqueuesi
ncl
udequeuesatbanks,
gr
ocer
yst
ores,andamusementpar
ks.Thet
womostcommonoper
ati
onsonaqueue
ar
e"enqueue"
,whi
chaddsani
tem t
othequeue,
and"
dequeue"
,whi
chr
emov
est
hef
ir
st
i
tem f
rom t
hequeue.
Ther
e'sonemor
ethi
ngt
oconsi
derwheni
tcomest
oqueues,andt
hati
sthewayt
hey
ar
eimpl
ement
ed.Ther
ear
etwomai
nway
stoi
mpl
ementaqueue:wi
thanar
rayorwi
th
al
i
nkedl
i
st.Anar
ray
-basedqueueusesasi
ngl
ear
rayt
ost
oreal
lthei
temsi
nthequeue.
Al
i
nkedl
i
st-
basedqueue,ont
heot
herhand,usesaser
iesofl
i
nkednodest
ost
oret
he
i
tems.Eachnodei
nthel
i
nkedl
i
stcont
ainsapoi
ntert
othenextnodei
nthel
i
st.Bot
hof
t
hesemet
hodshav
ethei
rownadv
ant
agesanddi
sadv
ant
ages.
Theenqueueoper
ati
oni
susedt
oaddani
tem t
otheendoft
hequeue.Whenani
tem i
s
enqueued,i
tisaddedt
othebackoft
hequeueandi
sthel
asti
tem t
ober
emov
ed.The
dequeueoper
ati
on,ont
heot
herhand,r
emov
esandr
etur
nst
hef
ir
sti
tem f
rom t
he

12
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

queue.Thesi
gni
fi
canceoft
heseoper
ati
onsi
sthatt
heyensur
ethatt
hei
temsi
nthe
queuear
epr
ocessedi
nthecor
rector
der
.Enqueuei
ngensur
est
hatnewi
temsar
eadded
t
otheendoft
hequeue,whi
l
edequeuei
ngensur
est
hati
temsar
eremov
edf
rom t
he
f
rontoft
hequeue.
I
naddi
ti
ont
o enqueuei
ng and dequeuei
ng i
tems,t
her
ear
eaf
ew ot
heri
mpor
tant
oper
ati
onst
hatcanbeper
for
medonaqueue.Oneoft
hesei
s"peeki
ng"
,whi
chal
l
ows
y
out
olookatt
hef
ir
sti
tem i
nthequeuewi
thoutr
emov
ingi
t.Anot
heroper
ati
oni
s
"
isEmpt
y",whi
ch checks whet
hert
he queue i
s empt
y.Fi
nal
l
y,t
her
eist
he "
size"
oper
ati
on,whi
chr
etur
nst
henumberofi
temsi
nthequeue.Theseoper
ati
onsar
eal
l
i
mpor
tantf
ordi
ff
erentt
ypesofappl
i
cat
ions.
8.Di
scussTheConceptOfA Pr
ior
it
yQueueAndI
tsAppl
icat
ions.Expl
ainHow A
Pr
ior
it
yQueueDi
ff
ersFr
om ARegul
arQueue,AndPr
ovi
deAnExampl
eOfAPr
act
ical
UseCaseForAPr
ior
it
yQueue.
Apr
ior
it
yqueuei
saspeci
alt
ypeofqueuet
hator
gani
zesi
temsbasedont
hei
rpr
ior
it
y.
Thehi
ghestpr
ior
it
yit
emsar
eal
way
satt
hef
rontoft
hequeueandar
epr
ocessedf
ir
st.
Thi
sisdi
ff
erentf
rom ar
egul
arqueue,
wher
eit
emsar
epr
ocessedi
ntheor
dert
heywer
e
added.Pr
ior
it
yqueues ar
e of
ten used i
n schedul
i
ng al
gor
it
hms,wher
etasks ar
e
assi
gneddi
ff
erentpr
ior
it
iesbasedont
hei
rimpor
tance.Forexampl
e,ahospi
talmi
ght
useapr
ior
it
yqueuet
oschedul
eappoi
ntment
sforpat
ient
s,wi
thhi
gherpr
ior
it
ygi
vent
o
pat
ient
swi
thmor
eur
gentmedi
cal
needs.
Onepr
act
icalexampl
eofapr
ior
it
yqueuei
sinj
obschedul
i
ng.Forexampl
e,acompany
mi
ghthav
eal
i
stoft
askst
hatneedt
obecompl
eted,wi
theacht
askhav
ingapr
ior
it
y
basedoni
tsur
gencyandi
mpor
tance.Apr
ior
it
yqueuecoul
dbeusedt
oensur
ethatt
he
mosti
mpor
tantt
asksar
ecompl
etedf
ir
st.Anot
herexampl
eisi
nnet
wor
krout
ing,
wher
e
packet
sofdat
aar
esentt
hroughanet
wor
kandhav
edi
ff
erentpr
ior
it
iesbasedont
hei
r
t
ypeanddest
inat
ion.Byusi
ngapr
ior
it
yqueue,t
henet
wor
kcanmakesur
ethatt
he
mosti
mpor
tantpacket
sar
edel
i
ver
edf
ir
st.
Ar
egul
arqueuei
saf
ir
st-
in,f
ir
st-
out(
FIFO)dat
ast
ruct
ure,meani
ngt
hatt
hei
temsar
e
pr
ocessedi
ntheor
dert
heywer
eadded.Apr
ior
it
yqueue,ont
heot
herhand,i
sadat
a
st
ruct
urewher
ethei
temsar
epr
ocessedbasedont
hei
rpr
ior
it
y,r
athert
hant
heor
der

13
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

t
heywer
e added.An exampl
e ofa pr
act
icaluse case f
ora pr
ior
it
yqueue i
sin
schedul
i
ngj
obsonaser
ver
.Forexampl
e,l
et'
ssayy
ouhav
easer
vert
hatneedst
o
pr
ocessbot
hhi
gh-
pri
ori
tyandl
ow-
pri
ori
tyj
obs.Wi
thapr
ior
it
yqueue,
youcanmakesur
e
t
hatt
hehi
gh-
pri
ori
tyj
obsar
epr
ocessedf
ir
st.
DEQUE(
Doubl
eEndedQueue)
:
A doubl
e-ended queue (
dequeue,of
ten abbr
evi
ated t
o deque,pr
onounced deck)
gener
ali
zesaqueue,f
orwhi
chel
ement
scanbeaddedt
oorr
emov
edf
rom ei
thert
he
f
ront(
head)orback(
tai
l
).I
tisal
soof
tencal
l
edahead-
tai
lli
nkedl
i
st.Li
keanor
dinar
y
queue,adoubl
e-endedqueuei
sadat
ast
ruct
urei
tsuppor
tst
hef
oll
owi
ngoper
ati
ons:
enq_
front
,enq_
back,deq_
front
,deq_
back,andempt
y.Dequeuecanbebehav
eli
kea
st
ackbyusi
ngonl
yenq_
frontanddeq_
front,andbehav
esl
i
keaqueuebyusi
ngonl
y
enq_
frontanddeq_
rear
.
9.Expl
ainTheConceptOfABi
nar
yTr
eeAndI
tsBasi
cPr
oper
ti
es.Pr
ovi
deAnExampl
e
OfABi
nar
yTr
eeAndDi
scussTwoCommonTr
aver
salMet
hodsUsedToExpl
oreThe
El
ement
sWi
thi
nABi
nar
yTr
ee.
Abi
nar
ytr
eei
sadat
ast
ruct
uret
hatst
oresdat
ainahi
erar
chi
cal
,tr
ee-
li
kest
ruct
ure.
Eachnodei
nthet
reehasatmostt
wochi
l
dnodes.Thebasi
cpr
oper
ti
esofabi
nar
ytr
ee
i
ncl
udet
her
oot
,whi
chi
sthet
opmostnode,
andt
hel
eav
es,
whi
char
ethenodeswi
thno
chi
l
dren.Ther
ear
etwocommonway
stot
rav
erseabi
nar
ytr
ee:i
n-or
dert
rav
ersaland
pr
e-or
dert
rav
ersal
.In-
ordert
rav
ersalv
isi
tst
hel
eftchi
l
d,t
hent
her
oot
,thent
her
ight
chi
l
d.Pr
e-or
dert
rav
ersal
visi
tst
her
oot
,thent
hel
eftchi
l
d,t
hent
her
ightchi
l
d.
Onepr
oper
tyi
scal
l
edt
he"
hei
ght
"oft
het
ree,whi
chi
sthenumberofnodesf
rom t
he
r
oott
othedeepestl
eafnode.Anot
herpr
oper
tyi
scal
l
edt
he"
bal
ance"oft
het
ree,
whi
ch
i
sameasur
eofhow "
symmet
ri
cal
"thet
reei
s.Abal
ancedt
reei
sonewher
eal
lthe
br
ancheshav
eroughl
ythesamedept
h.Anunbal
ancedt
reecancauseper
for
mance
i
ssues,
soi
t'
simpor
tantt
okeept
het
reebal
anced.
Twomostcommont
rav
ersalmet
hodsf
orabi
nar
ytr
eear
ein-
orderandpr
e-or
der
t
rav
ersal
.In-
ordert
rav
ersalv
isi
tst
hel
eftchi
l
d,t
hent
her
oot
,thent
her
ightchi
l
d,andi
t
r
etur
nst
henodesi
nsor
tedor
der
.Pr
e-or
dert
rav
ersalv
isi
tst
her
oot
,thent
hel
eftchi
l
d,
t
hent
her
ightchi
l
d,andi
tret
urnst
henodesi
ntheor
dert
heywer
eaddedt
othet
ree.

14
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

Post
-or
dert
rav
ersali
sanot
herl
esscommonmet
hodt
hatv
isi
tst
hel
eftchi
l
d,t
hent
he
r
ightchi
l
d,t
hent
her
oot
.
10.Descr
ibeTheConceptOfA Bi
nar
ySear
chTr
ee(
Bst
)AndI
tsKeyPr
oper
ti
es.
Pr
ovi
deAnExampl
eOfABi
nar
ySear
chTr
ee.
Abi
nar
ysear
cht
ree(
BST)i
sabi
nar
ytr
eet
hati
susedt
ost
oredat
ainsuchawayt
hat
al
l
owsf
orf
astr
etr
iev
aloft
hedat
a.Thekeypr
oper
ti
esofaBSTi
ncl
ude:
Eachnodehasav
alue,andt
hev
aluesi
nthel
eftsubt
reear
elesst
hant
her
ootnode'
s
v
alue,
andt
hev
aluesi
nther
ightsubt
reear
egr
eat
ert
hant
her
ootnode'
sval
ue.
Ther
eisoneandonl
yonepat
hfr
om t
her
oott
oanynodei
nthet
ree.
TheBSTi
sbal
anced,meani
ngt
hatt
hehei
ght
sofi
tsl
eftandr
ightsubt
reesdi
ff
erbyat
mostone.
11.Expl
aint
heConceptofaBal
ancedBi
nar
yTr
ee,andWhyi
sitI
mpor
tanti
nDat
a
St
ruct
ures?
Abal
ancedbi
nar
ytr
eei
sabi
nar
ytr
eet
hathasaspeci
alpr
oper
tycal
l
ed"
hei
ghtbal
ance"
.
Thi
spr
oper
tyst
atest
hatt
hehei
ghtoft
hel
eftsubt
reeandt
her
ightsubt
reeofanynode
i
nthet
reeshoul
ddi
ff
erbyatmostone.Thi
spr
oper
tyi
simpor
tantbecausei
tal
l
ows
bi
nar
ytr
eest
obeusedi
nanumberofal
gor
it
hms,i
ncl
udi
ngsear
chi
ng,sor
ti
ng,and
heaps.Whenabi
nar
ytr
eei
snotbal
anced,t
heseal
gor
it
hmscanbecomemuchsl
ower
.
Soi
t'
simpor
tantt
omai
ntai
nbal
ancewheni
nser
ti
nganddel
eti
ngi
temsf
rom abi
nar
y
t
ree.
12.Expl
ainTheConceptOfABi
nar
yTr
eeTr
aver
salAndPr
ovi
deExampl
esOfThe
Thr
eePr
imar
yTr
aver
salMet
hods:I
n-or
der
,Pr
e-or
der
,AndPost
-or
der
.Descr
ibeThe
Or
derI
nWhi
chNodesAr
eVi
sit
edAndThei
rSi
gni
fi
canceI
nTr
eePr
ocessi
ng.
I
n-or
dert
rav
ersal
visi
tst
hel
eftsubt
ree,
thent
her
ootnode,
thent
her
ightsubt
ree.
Pr
e-or
dert
rav
ersal
visi
tst
her
ootnode,
thent
hel
eftsubt
ree,
thent
her
ightsubt
ree.
Post
-or
dert
rav
ersal
visi
tst
hel
eftsubt
ree,
thent
her
ightsubt
ree,
thent
her
ootnode.
Thesemet
hodsar
eof
tenusedi
nal
gor
it
hmst
hatpr
ocesst
henodesofabi
nar
ytr
eei
na
cer
tai
nor
der
.Forexampl
e,i
n-or
dert
rav
ersalcanbeusedt
opr
intt
heel
ement
sofa
bi
nar
ytr
ee.
Tosummar
ize,
eachoft
het
hreet
rav
ersalmet
hodsv
isi
tst
henodesofabi
nar
ytr
eei
na

15
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

di
ff
erentor
der
.Thei
n-or
dert
rav
ersalv
isi
tst
henodesi
ntheor
derofl
eft
,root
,ri
ght
.The
pr
e-or
dert
rav
ersalv
isi
tst
henodesi
ntheor
derofr
oot
,lef
t,r
ight
.Fi
nal
l
y,t
hepost
-or
der
t
rav
ersalv
isi
tst
henodesi
ntheor
derofl
eft
,ri
ght
,root
.Eachoft
heseor
der
scanbe
usef
uli
ndi
ff
erentsi
tuat
ions,
dependi
ngont
heal
gor
it
hm bei
ngused.
Eachoft
heset
rav
ersalmet
hodsi
susedt
opr
ocesst
henodesofabi
nar
ytr
eei
na
speci
fi
cway
.In-
ordert
rav
ersali
susedt
opr
ocesst
henodesi
nal
evel
-or
derf
ashi
on,
wher
eal
lthenodesatagi
venl
evelar
epr
ocessedbef
oremov
ingont
othenextl
evel
.
Pr
e-or
dert
rav
ersali
susedt
opr
ocesst
henodesi
nadept
h-f
ir
stf
ashi
on,wher
ethe
nodesatt
hedeepestl
evelar
epr
ocessedf
ir
st.Post
-or
dert
rav
ersali
susedt
opr
ocess
t
henodesi
nabr
eadt
h-f
ir
stf
ashi
on,wher
ethenodesatt
hewi
destl
evelar
epr
ocessed
f
ir
st.Eachoft
hesemet
hodsi
susef
uli
ndi
ff
erentsi
tuat
ions.
15.Expl
ainTheConceptOfA Gr
aphDat
aSt
ruct
ureAndI
tsPr
imar
yComponent
s.
Pr
ovi
deAnExampl
eOfA Real
-wor
ldScenar
ioWher
eA Gr
aphI
sCommonl
yUsed.
Descr
ibeTheKeyOper
ati
onsAndAl
gor
it
hmsAppl
iedToGr
aphs.
Agr
aphi
sadat
ast
ruct
uret
hatconsi
stsofasetofnodesandasetofedgest
hat
connectt
he nodes.The nodescan r
epr
esentany
thi
ng,such aspeopl
e,ci
ti
es,or
document
s.The edges can r
epr
esentr
elat
ionshi
ps bet
ween t
he nodes,such as
f
ri
endshi
p,t
rav
el,orl
i
nks.A r
eal
-wor
ld exampl
eofagr
aph i
sthesoci
alnet
wor
k
Facebook.Thenodesi
nthi
sgr
aphar
euser
s,andt
heedgesar
efr
iendshi
psbet
ween
user
s.Keyoper
ati
onsongr
aphsi
ncl
udet
rav
ersal
,fi
ndi
ngt
heshor
testpat
hbet
ween
t
wonodes,
andf
indi
ngconnect
edcomponent
s.
Oneoft
hemosti
mpor
tantal
gor
it
hmsi
sDi
j
kst
ra'
sal
gor
it
hm,whi
chi
susedt
ofi
ndt
he
shor
testpat
h bet
ween t
wo nodes i
n a gr
aph.Thi
s al
gor
it
hm i
s used i
n many
appl
i
cat
ions,suchasmappi
ng and r
out
epl
anni
ng.Anot
heri
mpor
tantal
gor
it
hm i
s
br
eadt
h-f
ir
stsear
ch,whi
chi
susedt
osear
chal
lthenodesi
nagr
aph.Thi
sal
gor
it
hm i
s
usedi
nmanyappl
i
cat
ions,suchassear
chi
ngf
orf
il
esonacomput
erorf
indi
ngal
lthe
r
eachabl
enodesi
nanet
wor
k.

16
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

13.Expl
ainTheConceptOfADi
rect
edGr
aphAndAnUndi
rect
edGr
aph.Pr
ovi
deAn
Exampl
eOfEachTy
peOfGr
aphAndDi
scussTheKeyDi
ff
erencesBet
weenThem.
Adi
rect
edgr
aphi
sagr
aphi
nwhi
cht
heedgesar
edi
rect
ed,
orone-
way
.Thi
smeanst
hat
t
heedgeshav
east
art
ing poi
ntand anendi
ng poi
nt,and t
heedgescanonl
ybe
t
rav
ersedi
nonedi
rect
ion.Anexampl
eofadi
rect
edgr
aphi
sar
oadmap,wher
ethe
edgesr
epr
esentt
her
oadsandt
henodesr
epr
esentt
heci
ti
es.Anundi
rect
edgr
aph,on
t
heot
herhand,i
sagr
aphi
nwhi
cht
heedgesar
enotdi
rect
ed.Thi
smeanst
hatt
he
edgeshav
enost
art
ingpoi
ntorendi
ngpoi
nt,andt
heedgescanbet
rav
ersedi
nbot
h
di
rect
ions.
I
naddi
ti
ont
othedi
ff
erencei
nedgedi
rect
ional
i
ty,t
her
ear
eaf
ewot
herkeydi
ff
erences
bet
weendi
rect
edandundi
rect
edgr
aphs.Fi
rst
,di
rect
edgr
aphscanhav
ecy
cles,whi
l
e
undi
rect
edgr
aphscannot
.Second,di
rect
edgr
aphscanhav
emul
ti
pleedgesbet
ween
t
hesamet
wonodes,whi
l
eundi
rect
edgr
aphscannot
.Fi
nal
l
y,di
rect
edgr
aphscanhav
e
sel
f-
loops,whi
char
eedgest
hatst
artandendatt
hesamenode,whi
l
eundi
rect
ed
gr
aphscannothav
esel
f-
loops.
Agr
eatexampl
eofadi
rect
edgr
aphi
stheWor
ldWi
deWeb.I
nthi
sgr
aph,
eachwebpage
i
sanode,andeachhy
per
li
nki
sanedge.Theedgesar
edi
rect
ed,si
nceeachhy
per
li
nk
poi
ntsi
nonedi
rect
ionf
rom t
hesour
cepaget
othedest
inat
ionpage.Ont
heot
herhand,
anexampl
eofanundi
rect
edgr
aphi
samapoft
heLondonUnder
ground.I
nthi
sgr
aph,
eachst
ati
oni
sanode,andeachl
i
nei
sanedge.Theedgesar
eundi
rect
ed,si
nceeach
l
i
neconnect
stwost
ati
onsi
nbot
hdi
rect
ions.
14.Descr
ibeTheConceptOfAWei
ght
edGr
aphAndI
tsCommonAppl
icat
ions.Expl
ain
How Wei
ght
sAr
eAssoci
ated Wi
th EdgesI
n A Wei
ght
ed Gr
aph,And Pr
ovi
deAn
Exampl
eOfAPr
act
icalUseCaseForAWei
ght
edGr
aph.
I
nawei
ght
edgr
aph,
thewei
ght
sar
eassoci
atedwi
tht
heedgesi
naf
ewdi
ff
erentway
s.
Themostcommonwayi
stouset
hedi
stancebet
weent
wonodesast
hewei
ght
.
Anot
hercommonwayi
stouset
hecostoft
rav
eli
ngbet
weent
wonodes,suchast
he
costofaf
li
ghtbet
weent
woai
rpor
ts.Yetanot
herwayi
stouset
het
imer
equi
redt
o
t
rav
elbet
weent
wonodes,
suchast
hedr
ivi
ngt
imebet
weent
woci
ti
es.Wei
ght
edgr
aphs
ar
eusedi
nmanydi
ff
erentappl
i
cat
ions,
incl
udi
ngr
out
epl
anni
ng,
air
li
neschedul
i
ng,
and

17
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

l
ogi
sti
csopt
imi
zat
ion.
Onecommonusecasei
sinr
ide-
shar
ingappsl
i
keUberorLy
ft.Theseappsusea
wei
ght
ed gr
apht
ofi
nd t
hef
ast
estr
out
efr
om t
her
ider
'scur
rentl
ocat
iont
othei
r
dest
inat
ion.Thenodesi
nthegr
aphar
ethel
ocat
ions,andt
heedgesar
ether
oads
bet
weent
hel
ocat
ions.Thewei
ghtofeachedgei
stheest
imat
edt
rav
elt
imebet
ween
t
het
wol
ocat
ions.Theappt
henf
indst
heshor
testpat
hthr
ought
hegr
aph,whi
chi
sthe
f
ast
estr
out
efr
om t
her
ider
'scur
rentl
ocat
iont
othei
rdest
inat
ion.
The ai
rl
ine i
ndust
ryal
so uses wei
ght
ed gr
aphs t
o opt
imi
ze f
li
ghtschedul
es.For
exampl
e,ai
rl
inesneedt
odet
ermi
net
hemostef
fi
cientr
out
esf
ort
hei
rfl
i
ght
s,whi
ch
t
akesi
ntoaccountf
act
orsl
i
kedi
stance,speed,andai
rpor
tcapaci
ty.Todot
his,t
hey
cr
eat
eawei
ght
edgr
aphwher
ethenodesar
eai
rpor
tsandt
heedgesar
ethef
li
ght
s
bet
weent
hem.Thewei
ght
soft
heedgesar
ethef
li
ghtt
imes,
andt
heai
rl
ine'
sgoali
sto
f
indt
heshor
testpat
hthr
ought
hegr
apht
hatv
isi
tsal
lther
equi
redai
rpor
ts.
16.Di
ff
erent
iat
eBet
weenWei
ght
edAndUnwei
ght
edGr
aph.
Anunwei
ght
edgr
aphi
sagr
aphi
nwhi
cht
heedgeshav
enowei
ght
sassoci
atedwi
th
t
hem.Forexampl
e,an unwei
ght
ed soci
alnet
wor
k gr
aph woul
d hav
e edges t
hat
r
epr
esentf
ri
endshi
ps,butt
heedgeswoul
dnothav
eanywei
ght
sthati
ndi
cat
ethe
st
rengt
hoft
hef
ri
endshi
ps.Awei
ght
edgr
aph,ont
heot
herhand,i
sagr
aphi
nwhi
ch
each edgehasanumer
icalwei
ghtassoci
ated wi
thi
t.Thewei
ght
scan r
epr
esent
any
thi
ng,
suchast
hedi
stancebet
weent
woci
ti
esort
hest
rengt
hofaf
ri
endshi
p.
17.Expl
ainTheConceptOfMemor
yRepr
esent
ati
onOfABi
nar
yTr
eeUsi
ngAnAr
ray
.
Pr
ovi
deASt
ep-
by-
stepExampl
eToI
ll
ust
rat
eHowABi
nar
yTr
eeWi
thTheVal
ues1,2,
3,
4,5,
6,7Woul
dBeSt
oredI
nAnAr
ray
.
I
ncomput
ersci
ence,abi
nar
ytr
eecanber
epr
esent
edi
nmemor
yusi
nganar
ray
.Todo
t
his,t
hear
rayi
sdi
vi
dedi
ntot
hreesect
ions:t
her
ootsect
ion,t
hel
eftsect
ion,andt
he
r
ightsect
ion.Ther
ootsect
ionst
orest
her
ootnodeoft
het
ree.Thel
eftsect
ionst
ores
t
hel
eftsubt
ree,
andt
her
ightsect
ionst
orest
her
ightsubt
ree.Eachsect
ionoft
hear
ray
i
sthesamesi
ze,
andeachel
ementi
nthear
rayst
oresar
efer
encet
oanodei
nthet
ree.
Thi
swayofr
epr
esent
ingabi
nar
ytr
eei
nmemor
yiscal
l
edan"
arr
ay-
basedbi
nar
ytr
ee"
.

18
 ABDULLAHIUMAR DEPARTMENTOFMATHEMATI
CS

Let
'sst
artwi
thanempt
yar
rayt
hatwi
l
lrepr
esentourbi
nar
ytr
ee:
[
empt
yar
ray
]
Next
,we'
l
laddt
her
ootnode(
1)t
othear
ray
,li
ket
his:
[
1]
Now,
we'
l
laddt
hel
eftchi
l
doft
her
ootnode(
2)t
othear
ray
:
[
1,2]
Then,
we'
l
laddt
her
ightchi
l
doft
her
ootnode(
3)t
othear
ray
:
[
1,2,
3]
Next
,we'
l
laddt
hel
eftchi
l
dofnode2(
4)t
othear
ray
:
[
1,2,
3,4]
Keepgoi
ng?We'
l
laddt
her
ightchi
l
dofnode3(
5)t
othear
ray
:
[
1,2,
3,4,
5]
Now,
we'
l
laddt
hel
eftchi
l
dofnode4(
6)t
othear
ray
:
[
1,2,
3,4,
5,6]
Fi
nal
l
y,we'
l
laddt
her
ightchi
l
dofnode5(
7)t
othear
ray
:
[
1,2,
3,4,
5,6,
7]
Andt
hat
'showourbi
nar
ytr
eei
srepr
esent
edi
nthear
ray
!Toaccessanynodei
nthet
ree,
wecansi
mpl
ylookupi
tsposi
ti
on

19