Table of Contents
Preface xv
Acknowledgments xvii
Chapter 1 Introduction to Data Structures 1
1.1 Introduction 1
1.2 Types of Data Structures 2
1.2.1 Linear and Non-Linear Data Structures 2
1.2.2 Static and Dynamic Data Structures 3
1.2.3 Homogeneous and Non-Homogeneous Data Structures 3
1.2.4 Primitive and Non-Primitive Data Structures 3
1.2.5 Arrays/Lists 5
1.2.6 Stacks 5
1.2.7 Queues 5
1.2.8 Linked Lists 6
1.2.9 Trees 7
1.2.10 Graphs 8
1.3 Operations on Data Structures 9
1.4 Algorithms 10
1.4.1 Developing an Algorithm 10
1.5 Approaches for Designing an Algorithm 11
1.6 Analyzing an Algorithm 12
1.6.1 Time-Space Trade-Off 13
1.7 Abstract Data Types 14
1.8 Big O Notation 14
1.9 Summary 15
1.10 Exercises 17
1.11 Multiple Choice Questions 17
Chapter 2 Introduction to Python 21
2.1 Introduction 21
2.2 Python and Its Characteristics 22
2.3 Python Overview 23
2.4 Tools For Python 24
2.5 Easy_install and pip 24
2.6 Quotations and Comments in Python 24
2.7 Compiling the Python Program 25
2.8 Object-Oriented Programming 26
2.9 Character Set Used in Python 28
2.10 Python Tokens 28
2.11 Data Types in Python 31
2.12 Structure of a Python Program 32
2.13 Operators in Python 34
2.14 Decision Control Statements 38
2.15 Looping Statements 40
2.16 Loop Control Statements 43
2.17 Methods 45
2.18 Summary 50
2.19 Exercises 51
2.19.1 Theory Questions 51
2.19.2 Programming Projects 52
2.19.3 Multiple Choice Questions 53
Chapter 3 Arrays/Lists 55
3.1 Introduction 55
3.2 Definition of an Array 55
3.3 Array/List Declaration 56
3.4 Array/List Initialization 57
3.5 Calculating the Address of Array Elements 57
3.6 Operations on Arrays/lists 58
3.7 2-D Arrays/Two-Dimensional Arrays 61
3.8 Declaration of Two-Dimensional Arrays/Lists 62
3.9 Operations on 2-D Arrays/Lists 64
3.10 Multidimensional Arrays/N-Dimensional Arrays 67
3.11 Calculating the Address of 3-D Arrays 67
3.12 Arrays and Their Applications 69
3.13 Sparse Matrices 69
3.14 Types of Sparse Matrices 70
3.15 Representation of Sparse Matrices 71
3.16 Summary 72
3.17 Exercises 74
3.17.1 Theory Questions 74
3.17.2 Programming Questions 74
3.17.3 Multiple Choice Questions 75
Chapter 4 Linked Lists 77
4.1 Introduction 77
4.2 Definition of a Linked List 77
4.3 Memory Allocation in a Linked List 79
4.4 Types of Linked Lists 80
4.4.1 Singly Linked List 80
4.4.2 Operations on a Singly Linked List 80
4.4.3 Circular Linked Lists 93
4.4.4 Operations on a Circular Linked List 93
4.4.5 Doubly Linked List 101
4.4.6 Operations on a Doubly linked List 101
4.5 Header Linked Lists 113
4.6 Applications of Linked Lists 114
4.7 Polynomial Representation 114
4.8 Summary 115
4.9 Exercises 115
4.9.1 Theory Questions 115
4.9.2 Programming Questions 116
4.9.3 Multiple Choice Questions 116
Chapter 5 Queues 119
5.1 Introduction 119
5.2 Definition of a Queue 119
5.3 Implementation of a Queue 120
5.3.1 Implementation of Queues Using Arrays 120
5.3.2 Implementation of Queues Using linked Lists 120
5.4 Operations on Queues 125
5.4.1 Insertion 125
5.4.2 Deletion 126
5.5 Types-of Queues 129
5.5.1 Circular Queue 129
5.5.2 Priority Queue 135
5.5.3 De-queues (Double-Ended Queues) 142
5.6 Applications of Queues 146
5.7 Summary 146
5.8 Exercises 146
5.8.1 Theory Questions 147
5.8.2 Programming Questions 147
5.8.3 Multiple Choice Questions 148
Chapter 6 Searching and Soiling 151
6.1 Introduction to Searching 151
6.2 Linear Search or Sequential Search 151
6.2.1 Drawbacks of a Linear Search 154
6.3 Binary Search 155
6.3.1 Binary Search Algorithm 155
6.3.2 Complexity of a Binary Search Algorithm 158
6.3.3 Drawbacks of a Binary Search 158
6.4 Interpolation Search 159
6.4.1 The Interpolation Search Algorithm 160
6.4.2 Complexity of the Interpolation Search Algorithm 162
6.5 Introduction to Sorting 163
6.5.1 Types of Sorting Methods 164
6.6 External Sorting 184
6.7 Summary 184
6.8 Exercises 185
6.8.1 Theory Questions 185
6.8.2 Programming Questions 186
6.8.3 Multiple Choice Questions 186
Chapter 7 Stacks 189
7.1 Introduction 189
7.2 Definition of a Stack 189
7.3 Overflow and Underflow in Stacks 190
7.4 Operations on Stacks 191
7.5 Implementation of a Stack 196
7.5.1 Implementation of Stacks Using Arrays 196
7.5.2 Implementation of Stacks Using Linked Lists 196
7.6 Applications of Stacks 201
7.6.1 Polish and Reverse Polish Notations 201
7.6.2 Conversion from the Infix Expression to the Postfix Expression 202
7.6.3 Conversion from an Infix Expression to a Prefix Expression 208
7.6.4 Evaluation of a Postfix Expression 212
7.6.5 Evaluation of a Prefix Expression 216
7.6.6 Parenthesis Balancing 220
7.7 Summary 222
7.8 Exercises 223
7.8.1 Theory Questions 223
7.8.2 Programming Questions 224
7.8.3 Multiple Choice Questions 225
Chapter 8 Trees 227
8.1 Introduction 227
8.2 Definitions 228
8.3 Binary Tree 230
8.3.1 Types of Binary Trees 231
8.3.2 Memory Representation of Binary Trees 232
8.4 Binary Search Tree 234
8.4.1 Operations on Binary Search Trees 235
8.4.2 Binary Tree Traversal Methods 248
8.4.3 Creating a Binary Tree Using Traversal Methods 253
8.5 AVL Trees 256
8.5.1 Need for Height-Balanced Trees 257
8.5.2 Operations on an AVL Tree 258
8.6 Summary 268
8.7 Exercises 269
8.7.1 Theory Questions 269
8.7.2 Programming Questions 271
8.7.3 Multiple Choice Questions 272
Chapter 9 Multi-Way Search Trees 275
9.1 Introduction 275
9.2 B-Trees 276
9.3 Operations on a B-Tree 277
9.3.1 Insertion in a B-Tree 277
9.3.2 Deletion in a B-Tree 279
9.4 Application of a B-Tree 285
9.5 B+ Trees 285
9.6 Summary 286
9.7 Exercises 287
9.7.1 Review Questions 287
9.7.2 Multiple Choice Questions 287
Chapter 10 Hashing 289
10.1 Introduction 289
10.1.1 Difference between Hashing and Direct Addressing 291
10.1.2 Hash Tables 291
10.1.3 Hash Functions 292
10.1.4 Collision 295
10.1.5 Collision Resolution Techniques 295
10.2 Summary 317
10.3 Exercises 318
10.3.1 Review Questions 318
10.3.2 Multiple Choice Questions 319
Chapter 11 Files 321
11.1 Introduction 321
11.2 Terminology 321
11.3 File Operations 322
11.4 File Classification 323
11.5 C vs. C++ vs. Java vs. Python File Handling 323
11.6 File Organization 324
11.7 Sequence File Organization 325
11.8 Indexed Sequence File Organization 326
11.9 Relative File Organization 327
11.10 Inverted File Organization 328
11.11 Summary 329
11.12 Exercises 330
11.12.1 Review Questions 330
11.12.2 Multiple Choice Questions 331
Chapter 12 Graphs 333
12.1 Introduction 333
12.2 Definitions 335
12.3 Graph Representation 339
12.3.1 Adjacency Matrix Representation 339
12.3.2 Adjacency List Representation 342
12.4 Graph Traversal Techniques 344
12.4.1 Breadth-First Search 344
12.4.2 Depth-First Search 353
12.5 Topological Sort 353
12.6 Minimum Spanning Tree 356
12.6.1 Prim's Algorithm 356
12.6.2 Kruskal's Algorithm 359
12.7 Summary 362
12.8 Exercises 363
12.8.1 Theory Questions 363
12.8.2 Programming Questions 364
12.8.3 Multiple Choice Questions 365
Appendix: Answers to Multiple Choice Questions 367
Index 369
