Data Structures Notes | B.Sc. (Information Technology) Semester 3 | Mumbai University | munotes

Contents

Module I Introduction

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: What It Is Before Anybody Has Asked It a Question 9
4. Information: Data With a Question Asked of It 14
5. The Abstract Data Type: The Operations Are the Contract 17
6. Linear Data Structures: One Thing After Another 22
7. Non-Linear Data Structures: Where Branching Pays 26
8. Algorithm Analysis: Why Nobody Measures an Algorithm With a Clock 30
9. Time Complexity: Counting the Basic Operation 36
10. Big O Notation: The Definition, and How to Read It Aloud 40
11. The Growth Rates on This Paper, Ordered and Measured 44
12. Best Case, Average Case and Worst Case 48
13. Space Complexity, and the Trade Against Time 52
14. Choosing the Faster of Two Solutions, on Evidence 56
15. The Array: What It Is, and the One Property Everything Follows From 60
16. Address Arithmetic: Why Indexing Costs the Same Every Time 65
17. Traversing an Array 70
18. Searching an Array by Walking It 74
19. Insertion Into an Array, and the Shifting It Costs 78
20. Inserting at a Stated Position: the Lab Exercise, Complete 83
21. Deletion From an Array, and the Hole It Leaves 88
22. Deleting From a Stated Position: the Lab Exercise, Complete 94
23. What the Array Cannot Do 100
24. The Singly Linked List: the Node, the Link and the Head 104
25. How a Linked List Sits in Memory 109
26. Dynamic Memory: Asking for a Node and Giving It Back 114
27. Creating a Singly Linked List, and the Empty List 120
28. Traversing a Singly Linked List 125
29. Searching a Linked List, and the One Thing It Cannot Do 131
30. Inserting at the Beginning and at the End 137
31. Inserting at a Given Position 143
32. Deleting a Node: the First, the Last and One in the Middle 150
33. Array Against Linked List, Operation by Operation 156
34. The Advantages and Disadvantages of Each, as a Decision 162
35. The Stack: Last In, First Out 167
36. The Stack ADT: Its Operations and Its Two Error States 171
37. push, pop and peek, One at a Time 176
38. Implementing a Stack on an Array 181
39. The Lab Exercise: a Stack on an Array, Complete 187
40. What a Stack Is Actually For 191
41. Infix, Prefix and Postfix: Three Ways to Write One Expression 196
42. Precedence and Associativity, Which Is What the Conversion Uses 202
43. Converting Infix to Postfix With a Stack 207
44. The Lab Exercise: the Conversion, Brackets Included 214
45. Evaluating a Postfix Expression With a Stack 219
46. The Queue: First In, First Out 226
47. enqueue, dequeue and peek 232
48. Implementing a Queue on an Array, and the Drift That Ruins It 238
49. The Circular Queue: the Fix, and the Full-Against-Empty Trap 245
50. The Lab Exercise: a Queue on an Array, Complete 253
51. What a Queue Is For: Waiting in Turn 259
52. A Scheduling Scenario, Worked End to End 264
53. The Lab Exercise: a Customer Service Queue, Simulated 271
54. Stack Against Queue, and the Limit They Share 277
55. What Recursion Is, and the One Question That Makes It Easy 281
56. How a Recursive Call Actually Runs: the Call Stack 286
57. The Base Case: Where a Recursion Stops 292
58. The Recursive Step: Making the Problem Smaller 299
59. Factorial, Traced and Run 305
60. The Fibonacci Sequence, and Why the Obvious Recursion Is Slow 311
61. Recursion Against Iteration: Choosing Between Them 316
62. Module 1 in One Place: Definitions, Distinctions and One-Line Answers 322

Module II Trees

1. The Tree: the Vocabulary Before Anything Else 328
2. The Binary Tree: the Definition, and the Shapes One Can Take 333
3. Representing a Binary Tree With Linked Nodes 339
4. Representing a Binary Tree in an Array, and When That Is Better 344
5. What a Traversal Is, and Why There Are Exactly Three of This Kind 350
6. Inorder Traversal 356
7. Preorder Traversal 360
8. Postorder Traversal 365
9. The Lab Exercise: All Three Traversals on One Tree 370
10. The Binary Search Tree: the One Rule, and Everything It Buys 375
11. Searching a Binary Search Tree 380
12. Inserting Into a Binary Search Tree 386
13. The Lab Exercise: Building a Binary Search Tree From Input 392
14. The Lab Exercise: Searching for a Node 397
15. Deleting From a Binary Search Tree: the Three Cases 402
16. Inorder on a Binary Search Tree Comes Out Sorted, and Why That Matters 411
17. The Cost of a Binary Search Tree, and the Shape That Ruins It 417
18. What Trees Are For: Representing a Hierarchy 422
19. A Hierarchy Worked End to End 427
20. Hashing: Computing Where a Thing Lives Instead of Looking for It 432
21. The Hash Function: What Makes One Good 438
22. The Hash Table: Buckets, Table Size and the Load Factor 444
23. Collisions: Why They Are Certain, Not Unlucky 449
24. Separate Chaining, Built and Measured 454
25. The Lab Exercise: a Hash Table With Separate Chaining 459
26. Storing, Retrieving and Deleting 465
27. What Hashing Is For: the Dictionary 473
28. A Dictionary Worked End to End 479
29. What Sorting Is, and the Four Properties That Tell Two Sorts Apart 488
30. Bubble Sort 495
31. Insertion Sort 504
32. Selection Sort 513
33. The Lab Exercise: the Three Sorts Compared, Counted 521
34. What Searching Is, and What a Search Is Allowed to Assume 529
35. Linear Search 535
36. Binary Search 543
37. Binary Search Needs a Sorted Array, and What That Requirement Really Costs 552
38. The Lab Exercise: Linear Against Binary, Counted 561
39. Choosing a Structure for a Job, and Justifying the Choice 568
40. One Program That Uses Several of These Structures Together 576
41. Module 2 in One Place: Definitions, Distinctions and One-Line Answers 588