DATA STRUCTURES
(R18A0503)
LECTURE NOTES
B.TECH II YEAR – I SEM (R18)
(2019-20)
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
(Autonomous Institution – UGC, Govt. of India)
(Recognized under 2(f) and 12 (B) of UGC ACT 1956)
(Affiliated to JNTUH, Hyderabad, Approved by AICTE - Accredited by NBA & NAAC – ‘A’ Grade - ISO 9001:2015 Certified)
Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad – 500100, Telangana State, India
, II Year B. Tech CSE ‐ I Sem L T/P/D C
3 -/-/- 3
(R18A0503) DATA STRUCTURES
Prerequisites: A course on “Programming for Problem Solving”.
Course Objectives:
To impart the basic concepts of data structures
Exploring basic data structures such as stacks queues and lists.
Introduces a variety of data structures such as hash tables, search trees, heaps,
graphs.
To understand concepts about searching and sorting techniques
UNIT-I
Introduction: Abstract data types, Singly linked list: Definition, operations: Traversing,
Searching, Insertion and deletion, Doubly linked list: Definition, operations: Traversing,
Searching, Insertion and deletion, Circular Linked List: Definition, operations: Traversing,
Searching, Insertion and deletion.
UNIT-II
Stack: Stack ADT, array and linked list implementation, Applications- expression conversion
and evaluation. Queue: Types of Queue: Simple Queue, Circular Queue, Queue ADT- array
and linked list implementation. Priority Queue, heaps.
UNIT-III
Searching: Linear and binary search methods. Sorting: Selection Sort, Bubble Sort, Insertion
Sort, Quick Sort, Merge Sort, Heap Sort. Time Complexities .Graphs: Basic terminology,
representation of graphs, graph traversal methods DFS, BFS.
UNIT IV
Dictionaries: linear list representation, skip list representation, operations - insertion,
deletion and searching. Hash Table Representation: hash functions, collision resolution-
separate chaining, open addressing-linear probing, quadratic probing, double hashing,
rehashing, extendible hashing.
UNIT-V
Binary Search Trees: Various Binary tree representation, definition, BST ADT,
Implementation, Operations- Searching, Insertion and Deletion, Binary tree traversals,
threaded binary trees,
AVL Trees : Definition, Height of an AVL Tree, Operations – Insertion, Deletion and
Searching
B-Trees: B-Tree of order m, height of a B-Tree, insertion, deletion and searching, B+ Tree.
TEXTBOOKS:
1. Data Structures using C++, Special Edition-MRCET, Tata McGraw-Hill Publishers 2017.
2. Data structures, Algorithms and Applications in C++, S.Sahni, University Press (India)
Pvt.Ltd, 2nd edition, Universities Press Orient Longman Pvt. Ltd. Education.
,REFERENCE BOOKS:
1. Data structures and Algorithms in C++, Michael T.Goodrich, R.Tamassia and .Mount,
Wiley student edition, John Wiley and Sons.
2. Data structures and Algorithm Analysis in C++, Mark Allen Weiss, Pearson Education. Ltd.,
Second Edition
OUTCOMES:
At the end of the course the students are able to:
Ability to select the data structures that efficiently model the information in a
problem.
Ability to assess efficiency trade-offs among different data structure
implementations or combinations.
Implement and know the application of algorithms for sorting .
Design programs using a variety of data structures, including hash tables, binary
and general tree structures, search trees, AVL-trees, heaps and graphs.
, INDEX
UNIT NO TOPIC PAGE NO
Introduction 01
Singly linked list 02
I
Doubly linked list 14
Circular Linked List 28
Stack ADT 34
Array implementation 35
linked list implementation 38
Queue ADT 42
II Array implementation 43
linked list implementation 45
Circular Queue 47
Priority Queue 52
Heaps 53
Searching: Linear Search 67
Binary search 70
Sorting: Bubble Sort 74
Selection Sort 75
Insertion Sort 77
Quick Sort 78
III
Merge Sort 82
Heap Sort 84
Time Complexities 86
Graphs: Basic terminology 87
Representation of graphs 89
Graph traversal methods 91
Dictionaries: linear list representation 94
Skip list representation 98
IV Hash Table Representation 102
Rehashing, 109
Extendible hashing 111
Binary Search Trees: Basics 115
Binary tree traversals 119
Binary Search Tree 121
V
AVL Trees 126
B-Trees 138
B+ Tree 147
(R18A0503)
LECTURE NOTES
B.TECH II YEAR – I SEM (R18)
(2019-20)
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
(Autonomous Institution – UGC, Govt. of India)
(Recognized under 2(f) and 12 (B) of UGC ACT 1956)
(Affiliated to JNTUH, Hyderabad, Approved by AICTE - Accredited by NBA & NAAC – ‘A’ Grade - ISO 9001:2015 Certified)
Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad – 500100, Telangana State, India
, II Year B. Tech CSE ‐ I Sem L T/P/D C
3 -/-/- 3
(R18A0503) DATA STRUCTURES
Prerequisites: A course on “Programming for Problem Solving”.
Course Objectives:
To impart the basic concepts of data structures
Exploring basic data structures such as stacks queues and lists.
Introduces a variety of data structures such as hash tables, search trees, heaps,
graphs.
To understand concepts about searching and sorting techniques
UNIT-I
Introduction: Abstract data types, Singly linked list: Definition, operations: Traversing,
Searching, Insertion and deletion, Doubly linked list: Definition, operations: Traversing,
Searching, Insertion and deletion, Circular Linked List: Definition, operations: Traversing,
Searching, Insertion and deletion.
UNIT-II
Stack: Stack ADT, array and linked list implementation, Applications- expression conversion
and evaluation. Queue: Types of Queue: Simple Queue, Circular Queue, Queue ADT- array
and linked list implementation. Priority Queue, heaps.
UNIT-III
Searching: Linear and binary search methods. Sorting: Selection Sort, Bubble Sort, Insertion
Sort, Quick Sort, Merge Sort, Heap Sort. Time Complexities .Graphs: Basic terminology,
representation of graphs, graph traversal methods DFS, BFS.
UNIT IV
Dictionaries: linear list representation, skip list representation, operations - insertion,
deletion and searching. Hash Table Representation: hash functions, collision resolution-
separate chaining, open addressing-linear probing, quadratic probing, double hashing,
rehashing, extendible hashing.
UNIT-V
Binary Search Trees: Various Binary tree representation, definition, BST ADT,
Implementation, Operations- Searching, Insertion and Deletion, Binary tree traversals,
threaded binary trees,
AVL Trees : Definition, Height of an AVL Tree, Operations – Insertion, Deletion and
Searching
B-Trees: B-Tree of order m, height of a B-Tree, insertion, deletion and searching, B+ Tree.
TEXTBOOKS:
1. Data Structures using C++, Special Edition-MRCET, Tata McGraw-Hill Publishers 2017.
2. Data structures, Algorithms and Applications in C++, S.Sahni, University Press (India)
Pvt.Ltd, 2nd edition, Universities Press Orient Longman Pvt. Ltd. Education.
,REFERENCE BOOKS:
1. Data structures and Algorithms in C++, Michael T.Goodrich, R.Tamassia and .Mount,
Wiley student edition, John Wiley and Sons.
2. Data structures and Algorithm Analysis in C++, Mark Allen Weiss, Pearson Education. Ltd.,
Second Edition
OUTCOMES:
At the end of the course the students are able to:
Ability to select the data structures that efficiently model the information in a
problem.
Ability to assess efficiency trade-offs among different data structure
implementations or combinations.
Implement and know the application of algorithms for sorting .
Design programs using a variety of data structures, including hash tables, binary
and general tree structures, search trees, AVL-trees, heaps and graphs.
, INDEX
UNIT NO TOPIC PAGE NO
Introduction 01
Singly linked list 02
I
Doubly linked list 14
Circular Linked List 28
Stack ADT 34
Array implementation 35
linked list implementation 38
Queue ADT 42
II Array implementation 43
linked list implementation 45
Circular Queue 47
Priority Queue 52
Heaps 53
Searching: Linear Search 67
Binary search 70
Sorting: Bubble Sort 74
Selection Sort 75
Insertion Sort 77
Quick Sort 78
III
Merge Sort 82
Heap Sort 84
Time Complexities 86
Graphs: Basic terminology 87
Representation of graphs 89
Graph traversal methods 91
Dictionaries: linear list representation 94
Skip list representation 98
IV Hash Table Representation 102
Rehashing, 109
Extendible hashing 111
Binary Search Trees: Basics 115
Binary tree traversals 119
Binary Search Tree 121
V
AVL Trees 126
B-Trees 138
B+ Tree 147
