Data Structures Notes | B.Sc. (Computer Science) Semester 3 | Mumbai University | munotes

Contents

Module I Abstract Data Type, Linked Structures, Stacks and Queues

1. What a Data Structure Is, and Why the One You Pick Decides Whether the Program Works 1
2. How This Paper Is Examined, and How to Read This Book 5
3. Data and Its Types: What a Type Actually Settles 8
4. The Primitive Types, and Where They Stop 11
5. Linear and Non-Linear, Static and Dynamic: The Map of the Subject 14
6. Choosing a Structure: The Three Questions to Ask of Any of Them 17
7. The Abstract Data Type: A Promise, and a Hidden Representation 20
8. Why Hiding the Representation Is the Whole Point 23
9. Writing an ADT of Your Own 26
10. Judging an ADT: Complete, Minimal, and Honest About Cost 29
11. The Array: What It Really Is in Memory 32
12. Where the Array Stops: Insertion, Deletion and Growth 35
13. The Linked List: The Node, the Chain and the Head 38
14. The Linked List ADT, and Building an Empty One 41
15. Traversing a Singly Linked List 44
16. Searching a Singly Linked List 47
17. Prepending a Node 50
18. Appending a Node, and Why It Costs More 53
19. Removing a Node 56
20. Inserting and Deleting at Any Position 59
21. What a Singly Linked List Is Good and Bad At 62
22. The Array Against the Linked List, Measured 65
23. A Polynomial as a Linked List 68
24. Adding Two Polynomials 71
25. Multiplying Polynomials, and What the Representation Costs 74
26. The Doubly Linked List: The Second Link 77
27. Insertion and Deletion With Two Links 80
28. Traversing Both Ways, and the Applications That Need It 84
29. What the Second Link Costs and What It Buys 87
30. The Stack: One End, and Why That Is Enough 90
31. The Stack ADT: Push, Pop, and the Errors 93
32. A Stack on an Array, With Peek 96
33. A Stack on Links 99
34. What a Stack Is Good and Bad At 102
35. Balanced Delimiters, and Why a Counter Is Not Enough 105
36. Infix, Prefix and Postfix 108
37. Infix to Postfix With a Stack 111
38. Evaluating a Postfix Expression 114
39. Prefix: Converting to It, and Evaluating It 118
40. The Queue: Two Ends 122
41. The Queue ADT 125
42. A Queue on an Array, and the Drift That Ruins It 128
43. A Queue on Links 131
44. The Circular Queue: Wrap-Around 134
45. Full or Empty: Telling Them Apart 137
46. What a Queue Is Good and Bad At 140
47. The Deque: Open at Both Ends 143
48. Job Scheduling With a Queue 146
49. Module 1 in One Sitting 149

Module II Trees, Priority Queues and Heaps, Graphs and Hashing

1. From a Line to a Tree: Why Linear Structures Run Out 153
2. The Tree ADT: The Words, Said Exactly 156
3. Height, Depth, Level and Size, and the Relations Between Them 159
4. What a Tree Buys, and What It Costs 162
5. The Binary Tree 165
6. Binary Tree Properties, Proved 168
7. Full, Complete and Perfect, and Why the Difference Matters 171
8. Implementing a Binary Tree With Links 174
9. The Array Representation of a Binary Tree 177
10. Inorder Traversal 180
11. Preorder and Postorder Traversal 183
12. Level Order Traversal, and the Queue It Needs 186
13. Iterative Traversal, and the Stack It Needs 189
14. Rebuilding a Tree From Two Traversals 192
15. The Binary Search Tree: The Invariant 196
16. Searching a Binary Search Tree 199
17. Inserting Into a Binary Search Tree 202
18. Deleting From a Binary Search Tree: The Three Cases 205
19. Why a Binary Search Tree Degenerates 209
20. What Balance Means 212
21. Threaded Binary Trees 216
22. The AVL Tree and the Balance Factor 220
23. The Four Rotations 223
24. Insertion Into an AVL Tree 227
25. Deletion From an AVL Tree 231
26. Huffman Coding: The Problem 235
27. Building the Huffman Tree 238
28. Why the Huffman Code Is Prefix-Free, and What It Saves 241
29. The Priority Queue: When First In Is the Wrong Rule 246
30. The Priority Queue ADT 249
31. Three Ways to Build One, and What Each Costs 252
32. The Heap: Shape and Order 255
33. The Array That Holds a Heap 259
34. Min-Heap and Max-Heap 263
35. Heapify: Sifting Up and Sifting Down 266
36. Building a Heap, and Why It Is Linear 270
37. Where Priority Queues Are Used 275
38. What a Graph Is 279
39. The Vocabulary of Graphs 282
40. The Graph ADT 285
41. The Adjacency Matrix 288
42. The Adjacency List 291
43. Which Representation: The Costs, Measured 294
44. Inserting and Deleting Vertices and Edges 299
45. Breadth First Search 305
46. Depth First Search 310
47. Connectivity and Connected Components 315
48. The Shortest Path in an Unweighted Graph 320
49. Dijkstra's Algorithm 324
50. The Idea of Hashing: A Key Turned Into an Address 331
51. The Hash Table ADT 337
52. Hash Functions 342
53. What Makes a Hash Function Good 351
54. Collisions Are Certain, Not Unlucky 358
55. Chaining 365
56. Linear Probing 371
57. Quadratic Probing and Double Hashing 380
58. Load Factor and Rehashing 388
59. What Hashing Buys and What It Gives Up 395
60. Where Hashing Is Used, and Where It Must Not Be 400
61. Choosing the Right Structure: The Whole Paper on One Page 406
62. Module 2 in One Sitting 411