LECTURE NOTES O v. v.
N
DATA STRUCTURES v.
Year : 2017v.-v.2018
Coursev.Code : ACS102
Regulations : R16
Semester : Iv.B.Techv.IIv.Semester
Branch : CSEv./v.ITv./v.ECEv./v.EEE
Preparedv.byv.
Ms.v.Bv.Padmaja
Associatev.Professor
INSTITUTE OF AERONAUTICAL ENGINEERING
v. v. v.
(Autonomous)v.Dundig
al,v.Hyderabadv.-v.500v.043
, DATAv.STRUCTURES
IIv.Semester:v.CSEv./v.ECEv./v.EEEv./v.IT
Coursev.Code Category Hoursv./v.Week Credits Maximumv.Marks
L T P C CIA SEE Total
ACS002 Foundation
3 1 - 4 30 70 100
Contactv.Classes:v.45 Tutorialv.Classes:v.15 Practicalv.Classes:v.Nil Totalv.Classes:v . 60
COURSEv.OBJECTIVES:
Thev.coursev.shouldv.enablev.thev.studentsv.to:
I. Learnv.thev.basicv.techniquesv.ofv.algorithmv.analysis.
II. Demonstratev.severalv.searchingv.andv.sortingv.algorithms.
III. Implementv.linearv.andv.non-linearv.datav.structures.
IV. Demonstratev.variousv.treev.andv.graphv.traversalv.algorithms.
V. Analyzev.andv.choosev.appropriatev.datav.structurev.tov.solvev.problemsv.inv.realv.world.
UNITv.-v.1 INTRODUCTIONv.TOv.DATAv.STRUCTURES,v.SEARCHINGv.ANDv.SORTING
Basicv . concepts:v . Introductionv . tov . datav . structures,v . classificationv . ofv . datav . structures,v . operati
onsv . onv.datav . structures,v . v . abstractv . v . datav . v . type,v . v . algorithms,v . v . differentv . v . approachesv . v
. tov . v . designv . v . anv.algorithm,v . recursivev . algorithms;v . Searchingv . techniques:v . Linearv . search,v . bi
naryv . searchv . andv . Fibonacci
search;v.Sortingv.techniques:v.Bubblev.sort,v.selectionv.sort,v.insertionv.sort,v.quickv.sort,v.mergev.sort,v.an
dv.comparisonv.ofv.sortingv.algorithms.
UNITv.-v.2 LINEARv.DATAv.STRUCTURES
Stacks:v . Primitivev . operations,v . implementationv . ofv . stacksv . usingv . Arrays,v . applicationsv . ofv . sta
cksv.arithmeticv.expressionv . conversionv . andv . evaluation;v . Queues:v . Primitivev . operations;v . I
mplementationv.ofv . v . queuesv . v . usingv . Array,v . applicationsv . ofv . linearv . queue,v . circularv . que
uev . andv . doublev . endedv . queue
(DEQUE).
UNITv.-v.3 LINKEDv.LISTS
Linkedv.lists:v.Introduction,v.singlyv.linkedv.list,v.representationv.ofv.av.linkedv.listv.inv.memory,v.operation
sv.onv.av.Singlev . linkedv . list;v . Applicationsv . ofv . linkedv . lists:v . Polynomialv . representationv .
andv . sparsev . matrixv.manipulation.
Typesv . ofv . linkedv . lists:v . Circularv . linkedv . lists,v . doublyv . linkedv . lists;v . Linkedv . listv . repr
esentationv . andv.operationsv.ofv.Stack,v.linkedv.listv.representationv.andv.operationsv.ofv.queue.
UNITv.-v.4 NONv.LINEARv.DATAv.STRUCTURES
Treesv.:v.Basicv.concept,v.binaryv.tree,v.binaryv.treev.representation,v.arrayv.andv.linkedv.representations,v.b
inaryv.treev . traversal,v . binaryv . searchv . tree,v . treev . variants,v . applicationv . ofv . trees;v . Graphs:v . Basicv
. concept,v . graph
terminology,v.graphv.implementation,v.graphv.traversals,v.Applicationv.ofv.graphs,v.Priorityv.Queue.
UNITv.-v.5 BINARYv.TREESv.ANDv.HASHING
Binaryv . searchv . trees:v . Binaryv . searchv . trees,v . propertiesv . andv . operations;v . Balancedv
. searchv . trees:
AVLv . trees;v.Introductionv . tov . Mv.-
v.Wayv . searchv . trees,v . Bv . trees;v . Hashingv . andv . collision:v.Introduction,v.hashv . tables,v . hashv.fu
nctions,v.collisions,v.applicationsv.ofv.hashing.
LISTv.OFv.REFERENCEv.BOOKS:
,1. Yv.Danielv.Liang,v.―Introductionv.tov.Programmingv.usingv.Python‖,v.Pearson.
2. Benjaminv.Baka,v.Davidv.Julian,v.―Pythonv.Datav.Structuresv.andv.Algorithms‖,v.Packtv.Publishers,201
7.
3. Rancev.D.v.Necaise,v.―Datav.Structuresv.andv.Algorithmsv.usingv.Python‖,v.Wileyv.Studentv.Edition.
4. Martinv.Jones,v.―Pythonv.forv.Completev.Beginners‖,v.2015.
5. Zedv.A.v.Shaw,v.―Learnv.Pythonv.thev.Hardv.Way:v.av.veryv.simplev.introductionv.tov.thev.terri
fyinglyv.beautifulv.worldv.ofv.computersv.andv.code‖,v.3e,v.Addison-Wesley,v.2014.
6. Hemantv.Jain,v.―Problemv.Solvingv.inv.Datav.Structuresv.andv.Algorithmsv.usingv.Python:v.program
mingv.interviewv.guide‖,v.2016.
WEBv.REFERENCES:
1. https://docs.python.org/3/tutorial/datastructures.html
2. http://interactivepython.org/runestone/static/pythonds/index.html
3. http://www.tutorialspoint.com/data_structures_algorithms
4. http://www.geeksforgeeks.org/data-structures/
5. http://www.studytonight.com/data-structures/
6. http://www.coursera.org/specializations/data-structures-algorithms
, UNITv.–
I INTRODUCTIONv.TOv.DATAv.STRUCTURES,v.
v. v.
SEARCHINGv.ANDv.SORTING
Basicv.Concepts:v.Introductionv.tov.Datav.Structures:
Av.datav.structurev.isv.av.wayv.ofv.storingv.datav.inv.av.computerv.sov.thatv.itv.canv.bev.usedv.efficientlyv.andv.it
v.willv.allowv.thev.mostv.efficientv.algorithmv.tov.bev.used.v.Thev.choicev.ofv.thev.datav.structurev.beginsv.fro
mv.thev.choicev.ofv.anv.abstractv.datav.typev.(ADT).v.Av.well-
designedv.datav.structurev.allowsv.av.varietyv.ofv.criticalv.operationsv.tov.bev.performed,v.usingv.asv.fewv.reso
urces,v.bothv.executionv.timev.andv.memoryv.space,v.asv.possible.v.Datav.structurev.introductionv.refersv.tov.
av.schemev.forv.organizingv.data,v.orv.inv.otherv.wordsv.itv.isv.anv.arrangementv.ofv.datav.inv.computer'sv.me
moryv.inv.suchv.av.wayv.thatv.itv.couldv.makev.thev.datav.quicklyv.availablev.tov.thev.processorv.forv.requiredv.
calculations.
Av.datav.structurev.shouldv.bev.seenv.asv.av.logicalv.conceptv.thatv.mustv.addressv.twov.fundamentalv.concerns.
1. First,v.howv.thev.datav.willv.bev.stored,v.and
2. Second,v.whatv.operationsv.willv.bev.performedv.onv.it.
Asv.datav.structurev.isv.av.schemev.forv.datav.organizationv.sov.thev.functionalv.definitionv.ofv.av.datav.structur
ev.shouldv.bev.independentv.ofv.itsv.implementation.v.Thev.functionalv.definitionv.ofv.av.datav.structurev.isv.k
nownv.asv.ADTv.(Abstractv.Datav.Type)v.whichv.isv.independentv.ofv.implementation.v.Thev.wayv.inv.which
v.thev.datav.isv.organizedv.affectsv.thev.performancev.ofv.av.programv.forv.differentv.tasks.v.Computerv.progra
mmersv.decidev.whichv.datav.structuresv.tov.usev.basedv.onv.thev.naturev.ofv.thev.datav.andv.thev.processesv.th
atv.needv.tov.bev.performedv.onv.thatv . data.v.Somev.ofv.thev.morev.commonlyv.usedv.datav.structuresv.includ
ev.lists,v.arrays,v.stacks,v.queues,v.heaps,v.trees,v.andv.graphs.
Classificationv.ofv.Datav.Structures:
Datav.structuresv.canv.bev.classifiedv.as
Simplev.datav.structure
Compoundv.datav.structure
Linearv.datav.structure
Nonv.linearv.datav.structure
[Figv.1.1v.Classificationv.ofv.Datav.Structures]
1
N
DATA STRUCTURES v.
Year : 2017v.-v.2018
Coursev.Code : ACS102
Regulations : R16
Semester : Iv.B.Techv.IIv.Semester
Branch : CSEv./v.ITv./v.ECEv./v.EEE
Preparedv.byv.
Ms.v.Bv.Padmaja
Associatev.Professor
INSTITUTE OF AERONAUTICAL ENGINEERING
v. v. v.
(Autonomous)v.Dundig
al,v.Hyderabadv.-v.500v.043
, DATAv.STRUCTURES
IIv.Semester:v.CSEv./v.ECEv./v.EEEv./v.IT
Coursev.Code Category Hoursv./v.Week Credits Maximumv.Marks
L T P C CIA SEE Total
ACS002 Foundation
3 1 - 4 30 70 100
Contactv.Classes:v.45 Tutorialv.Classes:v.15 Practicalv.Classes:v.Nil Totalv.Classes:v . 60
COURSEv.OBJECTIVES:
Thev.coursev.shouldv.enablev.thev.studentsv.to:
I. Learnv.thev.basicv.techniquesv.ofv.algorithmv.analysis.
II. Demonstratev.severalv.searchingv.andv.sortingv.algorithms.
III. Implementv.linearv.andv.non-linearv.datav.structures.
IV. Demonstratev.variousv.treev.andv.graphv.traversalv.algorithms.
V. Analyzev.andv.choosev.appropriatev.datav.structurev.tov.solvev.problemsv.inv.realv.world.
UNITv.-v.1 INTRODUCTIONv.TOv.DATAv.STRUCTURES,v.SEARCHINGv.ANDv.SORTING
Basicv . concepts:v . Introductionv . tov . datav . structures,v . classificationv . ofv . datav . structures,v . operati
onsv . onv.datav . structures,v . v . abstractv . v . datav . v . type,v . v . algorithms,v . v . differentv . v . approachesv . v
. tov . v . designv . v . anv.algorithm,v . recursivev . algorithms;v . Searchingv . techniques:v . Linearv . search,v . bi
naryv . searchv . andv . Fibonacci
search;v.Sortingv.techniques:v.Bubblev.sort,v.selectionv.sort,v.insertionv.sort,v.quickv.sort,v.mergev.sort,v.an
dv.comparisonv.ofv.sortingv.algorithms.
UNITv.-v.2 LINEARv.DATAv.STRUCTURES
Stacks:v . Primitivev . operations,v . implementationv . ofv . stacksv . usingv . Arrays,v . applicationsv . ofv . sta
cksv.arithmeticv.expressionv . conversionv . andv . evaluation;v . Queues:v . Primitivev . operations;v . I
mplementationv.ofv . v . queuesv . v . usingv . Array,v . applicationsv . ofv . linearv . queue,v . circularv . que
uev . andv . doublev . endedv . queue
(DEQUE).
UNITv.-v.3 LINKEDv.LISTS
Linkedv.lists:v.Introduction,v.singlyv.linkedv.list,v.representationv.ofv.av.linkedv.listv.inv.memory,v.operation
sv.onv.av.Singlev . linkedv . list;v . Applicationsv . ofv . linkedv . lists:v . Polynomialv . representationv .
andv . sparsev . matrixv.manipulation.
Typesv . ofv . linkedv . lists:v . Circularv . linkedv . lists,v . doublyv . linkedv . lists;v . Linkedv . listv . repr
esentationv . andv.operationsv.ofv.Stack,v.linkedv.listv.representationv.andv.operationsv.ofv.queue.
UNITv.-v.4 NONv.LINEARv.DATAv.STRUCTURES
Treesv.:v.Basicv.concept,v.binaryv.tree,v.binaryv.treev.representation,v.arrayv.andv.linkedv.representations,v.b
inaryv.treev . traversal,v . binaryv . searchv . tree,v . treev . variants,v . applicationv . ofv . trees;v . Graphs:v . Basicv
. concept,v . graph
terminology,v.graphv.implementation,v.graphv.traversals,v.Applicationv.ofv.graphs,v.Priorityv.Queue.
UNITv.-v.5 BINARYv.TREESv.ANDv.HASHING
Binaryv . searchv . trees:v . Binaryv . searchv . trees,v . propertiesv . andv . operations;v . Balancedv
. searchv . trees:
AVLv . trees;v.Introductionv . tov . Mv.-
v.Wayv . searchv . trees,v . Bv . trees;v . Hashingv . andv . collision:v.Introduction,v.hashv . tables,v . hashv.fu
nctions,v.collisions,v.applicationsv.ofv.hashing.
LISTv.OFv.REFERENCEv.BOOKS:
,1. Yv.Danielv.Liang,v.―Introductionv.tov.Programmingv.usingv.Python‖,v.Pearson.
2. Benjaminv.Baka,v.Davidv.Julian,v.―Pythonv.Datav.Structuresv.andv.Algorithms‖,v.Packtv.Publishers,201
7.
3. Rancev.D.v.Necaise,v.―Datav.Structuresv.andv.Algorithmsv.usingv.Python‖,v.Wileyv.Studentv.Edition.
4. Martinv.Jones,v.―Pythonv.forv.Completev.Beginners‖,v.2015.
5. Zedv.A.v.Shaw,v.―Learnv.Pythonv.thev.Hardv.Way:v.av.veryv.simplev.introductionv.tov.thev.terri
fyinglyv.beautifulv.worldv.ofv.computersv.andv.code‖,v.3e,v.Addison-Wesley,v.2014.
6. Hemantv.Jain,v.―Problemv.Solvingv.inv.Datav.Structuresv.andv.Algorithmsv.usingv.Python:v.program
mingv.interviewv.guide‖,v.2016.
WEBv.REFERENCES:
1. https://docs.python.org/3/tutorial/datastructures.html
2. http://interactivepython.org/runestone/static/pythonds/index.html
3. http://www.tutorialspoint.com/data_structures_algorithms
4. http://www.geeksforgeeks.org/data-structures/
5. http://www.studytonight.com/data-structures/
6. http://www.coursera.org/specializations/data-structures-algorithms
, UNITv.–
I INTRODUCTIONv.TOv.DATAv.STRUCTURES,v.
v. v.
SEARCHINGv.ANDv.SORTING
Basicv.Concepts:v.Introductionv.tov.Datav.Structures:
Av.datav.structurev.isv.av.wayv.ofv.storingv.datav.inv.av.computerv.sov.thatv.itv.canv.bev.usedv.efficientlyv.andv.it
v.willv.allowv.thev.mostv.efficientv.algorithmv.tov.bev.used.v.Thev.choicev.ofv.thev.datav.structurev.beginsv.fro
mv.thev.choicev.ofv.anv.abstractv.datav.typev.(ADT).v.Av.well-
designedv.datav.structurev.allowsv.av.varietyv.ofv.criticalv.operationsv.tov.bev.performed,v.usingv.asv.fewv.reso
urces,v.bothv.executionv.timev.andv.memoryv.space,v.asv.possible.v.Datav.structurev.introductionv.refersv.tov.
av.schemev.forv.organizingv.data,v.orv.inv.otherv.wordsv.itv.isv.anv.arrangementv.ofv.datav.inv.computer'sv.me
moryv.inv.suchv.av.wayv.thatv.itv.couldv.makev.thev.datav.quicklyv.availablev.tov.thev.processorv.forv.requiredv.
calculations.
Av.datav.structurev.shouldv.bev.seenv.asv.av.logicalv.conceptv.thatv.mustv.addressv.twov.fundamentalv.concerns.
1. First,v.howv.thev.datav.willv.bev.stored,v.and
2. Second,v.whatv.operationsv.willv.bev.performedv.onv.it.
Asv.datav.structurev.isv.av.schemev.forv.datav.organizationv.sov.thev.functionalv.definitionv.ofv.av.datav.structur
ev.shouldv.bev.independentv.ofv.itsv.implementation.v.Thev.functionalv.definitionv.ofv.av.datav.structurev.isv.k
nownv.asv.ADTv.(Abstractv.Datav.Type)v.whichv.isv.independentv.ofv.implementation.v.Thev.wayv.inv.which
v.thev.datav.isv.organizedv.affectsv.thev.performancev.ofv.av.programv.forv.differentv.tasks.v.Computerv.progra
mmersv.decidev.whichv.datav.structuresv.tov.usev.basedv.onv.thev.naturev.ofv.thev.datav.andv.thev.processesv.th
atv.needv.tov.bev.performedv.onv.thatv . data.v.Somev.ofv.thev.morev.commonlyv.usedv.datav.structuresv.includ
ev.lists,v.arrays,v.stacks,v.queues,v.heaps,v.trees,v.andv.graphs.
Classificationv.ofv.Datav.Structures:
Datav.structuresv.canv.bev.classifiedv.as
Simplev.datav.structure
Compoundv.datav.structure
Linearv.datav.structure
Nonv.linearv.datav.structure
[Figv.1.1v.Classificationv.ofv.Datav.Structures]
1
