Data Structures using Python

Shriram K. Vasudevan is Assistant Professor, Dept. of Computer Science& Engineering, Amrita Vishwavidyapeetham, Coimbatore. He holds a Ph.D. in Embedded Systems with over 11 years of industrial and academic experience. He has worked with major multinational companies like Wipro and Aricent Technologies before joining academics.Abhishek S. Nagarajan is a Data scientist in [24]7.ai in Bangalore. His primary job is developing and deploying data-driven machine learning models. Other than models he is also responsible for maintaining business metrics based on client requirements. He also has a basic knowledge on the retargeting and personalization projects for customer acquisition in clients. He proposed a personalization based targeting model for an event called 'ideon' and the same selected for final and has been planned for implementation in leading clients. His areas of interests are Data sciences, Data structures, Internet of Things, Augmented reality and Mas personalization.Karthick Nanmaran is Assistant Professor, Department of CSE, SRM Institute of Science and Technology, Chennai.

• 1. Data Structures-Introduction 1.1 Introduction1.2 What is a Data Structure?1.3 Why Do We Need Data Structures?1.4 How to Study/Prepare Data Structures? Why Does It Appear Difficult?1.5 Different Types of Data Structures1.6 How to Select a Data Structure?1.7 How are Data Structures Implemented?1.8 Real-Life Scenarios for Data Structures1.6 Difference Between Data Structures and Database Management Systems2. Abstract Data Type and Analysis 2.1 Introduction- Abstract Data Type2.2 Complexity2.2.1 Time Complexity2.2.2 Space Complexity2.3 Asymptotic Notations2.3.1 Big-O2.3.2 Big-Omega2.3.3 Big-Theta2.3.4 Small-O2.3.5 Small-Omega2.4 Recursion2.4.1 How does Recursion Work?2.4.2 Inefficient Recursion2.4.3 Tail Call Elimination2.4.4 Analysis of Recursive Functions2.5 Applications of Recursion3. Linear Data Structures 3.1 Arrays-Introduction3.2 Declaration of Arrays3.3 Implementation3.3.1 Insertion3.3.2 Deletion3.3.3 Merging3.3.4 Some More Operations3.3.5 Complexity Analysis3.4 Applications3.5 Python Sequences4. Continuous Memory Based Linear Data Structures 4.1 Introduction4.2 Stack4.2.1 Working-Push Operation4.2.2 Working-Pop Operation4.2.3 Working-Top Operation4.3 Implementation of Stack Using Pointers4.4 Complex Operations4.4.1 Searching4.4.2 Sorting4.4.3 Complexity Analysis4.5 Applications of Stacks4.5.1 Application: Infix-to-Postfix Conversion4.5.2 Application: Evaluation of Prefix Expression4.6 Queues4.7 ingle-Ended Queues4.7.1 Working-Enqueue Operation4.7.2 Working-Dequeue Operation4.7.3 Working-Front Operation4.7.4 Implementation of Single-EndedQueues using Lists4.7.5 Complex Operations4.7.6 Circular Array-based Implementation of Single-ended Queues4.8 Double-Ended Queues4.8.1 Working: Push_Front Operation4.8.2 Working: Push_Back Operation4.8.3 Working: Pop-Front Operation4.8.4 Working: Pop_Back Operation4.8.5 Working: Front Operation4.8.6 Working: Rear Operation4.8.7 Implementation of a Deque4.8.8 Complex Operations4.8.9 Complexity Analysis4.9 Priority Queues4.9.1 Implementation of Priority Queues4.1 Applications of Queues4.10.1 Application: Check if a Given String is a Palindrome5. Pointer-Based Linear Data Structures 5.1 Introduction to Linked Lists5.2 Singly Linked Lists5.2.1 Working-Insert Node Operation5.2.2 Working-Delete Node Operation5.2.3 Working-ValueAt Operation5.2.4 Implementation of Singly Linked Lists5.2.5 Complex Operations-Searching5.2.6 Complex Operations-Sorting5.2.7 Complexity Analysis5.3 Doubly Linked Lists5.3.1 Working-Insert Node Operation5.3.2 Working-Delete Node Operation5.3.3 Working-ValueAt Operation5.3.4 Implementation of Doubly Linked Lists5.3.5 Complexity Analysis5.4 Circular Linked Lists5.4.1 Working-Insert Node Operation5.4.3 Implementation of Circular Linked Lists5.4.4 Complexity Analysis5.5 Applications of Linked Lists6. Pointer Based Hierarchical Data Structures 6.1 Introduction-Non-Linear Data Structures6.2 TREES6.2.1 Definitions6.3 Binary Trees6.3.1 Types of Binary Trees6.4 Implementation of Binary Trees6.4.1 Pointer-based Implementation6.4.2 Array-based Implementation6.4.3 Linked List-based Implementation6.5 Traversal6.5.1 In-order Traversal6.5.2 Pre-order Traversal6.5.3 Post-order Traversal6.5.4 Level-ordered Traversal6.6 Basic Operations6.6.1 Inserting a Node6.6.2 Deleting a Node6.7 Threaded Binary Trees6.8 Applications of Trees7. Search Trees 7.1 Introduction7.2 Binary Search Trees7.2.1 Operation-Search Value7.2.2 Operation-Insert a Node7.2.3 Operation-Delete a Node7.2.4 Implementation of Binary Search Trees7.2.5 Complexity Analysis7.3 Avl Trees7.3.1 Operation-Search Value7.3.2 Operation- Insert a Node7.3.3 Operation-Deleting a Node7.3.4 Implementation of AVL Trees7.3.5 Complexity Analysis7.4 Red-Black Trees7.4.1 Operation-Insertion7.4.2 Operation-Delete a Node7.4.3 Implementation of Red-Black Trees7.4.4 Complexity Analysis7.5 Splay Trees7.5.1 Operation-'Search a Value' or 'Splay a Value'7.5.2 Operation-Insert a Node7.5.3 Operation-Delete a Node7.5.4 Implementation of Splay Trees7.5.5 Complexity Analysis7.6 B-TREES7.6.1 In-order Traversal7.6.2 Operation-Search a Node7.6.3 Operation-Insert a Node7.6.4 Operation-Delete a Node7.6.5 Implementation of B-Trees7.6.6 Complexity Analysis7.7 Applications of Search Trees8. Priority Queues and Heaps 8.1 Introduction-Heap8.2 Binary Heaps8.2.1 Operation-Insertion8.2.2 Operation-Deletion8.2.3 Implementation of Max Heap8.2.4 Complexity Analysis8.3 Leftist Heaps8.3.1 Operation-Merging8.3.2 Operation-Insertion8.3.3 Operation-Deletion8.3.4 Implementation of Leftist Heaps8.3.5 Complexity Analysis8.4 Priority Queues Using Heaps8.5 Applications of Heaps9. Other Non-Linear Data Structures9.1 Introduction-Non-Linear, Non-Hierarchical Data Structures9.2 Trie9.2.1 Insertion of a Key9.2.2 Searching a Key9.2.3 Implementation9.2.4 Complexity Analysis9.2.5 Applications of Trie9.3 Dictionary9.3.1 Inserting a Key and its Value9.3.2 Deleting a Key along with Value9.3.3 Merging Dictionaries9.3.4 Handling Tabular Data9.3.5 Implementation9.3.6 Complexity9.3.7 Applications of Dictionary9.4 Hash Table9.4.1 Linear Probing9.4.2 Chaining the Elements9.4.3 Implementation9.4.4 Complexity9.4.5 Applications of Hash Tables9.5 Sets9.5.1 Operation-Insertion of an Element9.5.2 Operation-Removal of Elements9.5.3 Binary Set Operations9.5.4 Other Utility Functions9.5.5 Implementation9.5.6 Complexity Analysis9.5.7 Applications of Set9.5.8 Variants of Set Data Structure9.5 Counter/Multisets9.5.1 Accessing9.5.2 Binary Operations on Counters10. Memory Management10.1 Introduction-Memory Management10.2 Data Structures in Memory Management10.3 B+ Trees10.3.1 Working10.3 Memory Hierarchy and Caching11. Graphs11.1 Graph-Introduction11.2 Components of a Graph11.4 Graph Representation11.4.1 Linked List Based Representation11.4.2 Matrix Based Representation11.2.3 Pointer Based Representation11.2.4 Performance Comparison of Graph Representation11.3 Types of Graph11.4 Working11.4.1 Insertion of a node11.4.2 Insertion of an edge11.4.3 Deletion of an edge11.4.4 Deletion of a node11.5 Traversal11.5.1 Depth First Search11.5.2 Breadth First Search11.7 Implementation of Graph11.7.1 Adjacency List Based Representation11.7.2 Adjacency Matrix Based Representation11.7.3 Incidence Matrix Based Representation11.8 Complexity Analysis11.9 Topological Sorting11.9.1 Implementation11.9.2 Complexity Analysis11.1 Spanning Tree11.10.1 Kruskal Algorithm11.10.2 Prim's Algorithm11.11 Shortest Distance11.11.1 Dijkstra's Algorithm11.11.2 Floyd-Warshall Algorithm11.12 Graph Connectivity11.12 Applications Of Graph12. Sorting12.1 Introduction to Sorting12.2 Importance of Sorting Algorithms12.3 Exchange Sort12.3.1 Bubble Sort12.4 Selection Sort12.4.1 Straight Selection Sort12.4.2 Heap Sort12.5 Insertion Sort12.5.1 Simple Insertion Sort12.5.2 Shell Sort12.6 Divide and Conquer12.6.1 Merge Sort12.6.2 Quick Sort12.7 Distributed Sort12.7.1 Bucket Sort12.7.2 Counting Sort12.7.3 Radix Sort12.8 Comparison of Sorts13. Searching13.1 Introduction-What is Searching?13.2 Linear Search13.2.1 Working13.2.2 Implementation13.3.3 Complexity Analysis13.3 Binary Search13.3.1 Working13.3.2 Implementation13.3.3 Complexity Analysis13.4 Tree-Based Search13.5 Hashing13.5.1 Working13.5.2 Problem of Collision13.5.4 Implementation13.5.5 Complexity Analysis13.6 Case Studies of Searching TechniquesANNEXURE 1 - Python classes and built in Functions