Data Structures using Python

Data Structures using Python provides an introduction to design, analysis, and implementation of data structures using the powerful language Python. This book is designed for a first course on the subject. It is written for the undergraduate engineering students of Computer Science, Information Technology and allied disciplines. The book begins with an overview of the concept, need, nomenclature followed by discussion of Arrays, Stacks, Queues, Double Ended Queues, Linked List - all under a chapter on Linear Data Structures. This is followed by a chapter on Non-linear Data Structures where Heap, Hash Table, Trie, and Disjoint Sets are discussed. Trees, though a non-linear data structure, is discussed as a separate chapter to emphasize upon its importance. The last few chapters of the book discusses Graphs, Searching, and Sorting finally ending with an appendix on Python built-in class functions.

Table of Contents:
1. Data Structures-Introduction 1.1 Introduction 1.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 Structures 1.6 How to Select a Data Structure? 1.7 How are Data Structures Implemented? 1.8 Real-Life Scenarios for Data Structures 1.6 Difference Between Data Structures and Database Management Systems 2. Abstract Data Type and Analysis 2.1 Introduction- Abstract Data Type 2.2 Complexity 2.2.1 Time Complexity 2.2.2 Space Complexity 2.3 Asymptotic Notations 2.3.1 Big-O 2.3.2 Big-Omega 2.3.3 Big-Theta 2.3.4 Small-O 2.3.5 Small-Omega 2.4 Recursion 2.4.1 How does Recursion Work? 2.4.2 Inefficient Recursion 2.4.3 Tail Call Elimination 2.4.4 Analysis of Recursive Functions 2.5 Applications of Recursion 3. Linear Data Structures 3.1 Arrays-Introduction 3.2 Declaration of Arrays 3.3 Implementation 3.3.1 Insertion 3.3.2 Deletion 3.3.3 Merging 3.3.4 Some More Operations 3.3.5 Complexity Analysis 3.4 Applications 3.5 Python Sequences 4. Continuous Memory Based Linear Data Structures 4.1 Introduction 4.2 Stack 4.2.1 Working-Push Operation 4.2.2 Working-Pop Operation 4.2.3 Working-Top Operation 4.3 Implementation of Stack Using Pointers 4.4 Complex Operations 4.4.1 Searching 4.4.2 Sorting 4.4.3 Complexity Analysis 4.5 Applications of Stacks 4.5.1 Application: Infix-to-Postfix Conversion 4.5.2 Application: Evaluation of Prefix Expression 4.6 Queues 4.7 ingle-Ended Queues 4.7.1 Working-Enqueue Operation 4.7.2 Working-Dequeue Operation 4.7.3 Working-Front Operation 4.7.4 Implementation of Single-Ended Queues using Lists 4.7.5 Complex Operations 4.7.6 Circular Array-based Implementation of Single-ended Queues 4.8 Double-Ended Queues 4.8.1 Working: Push_Front Operation 4.8.2 Working: Push_Back Operation 4.8.3 Working: Pop-Front Operation 4.8.4 Working: Pop_Back Operation 4.8.5 Working: Front Operation 4.8.6 Working: Rear Operation 4.8.7 Implementation of a Deque 4.8.8 Complex Operations 4.8.9 Complexity Analysis 4.9 Priority Queues 4.9.1 Implementation of Priority Queues 4.1 Applications of Queues 4.10.1 Application: Check if a Given String is a Palindrome 5. Pointer-Based Linear Data Structures 5.1 Introduction to Linked Lists 5.2 Singly Linked Lists 5.2.1 Working-Insert Node Operation 5.2.2 Working-Delete Node Operation 5.2.3 Working-ValueAt Operation 5.2.4 Implementation of Singly Linked Lists 5.2.5 Complex Operations-Searching 5.2.6 Complex Operations-Sorting 5.2.7 Complexity Analysis 5.3 Doubly Linked Lists 5.3.1 Working-Insert Node Operation 5.3.2 Working-Delete Node Operation 5.3.3 Working-ValueAt Operation 5.3.4 Implementation of Doubly Linked Lists 5.3.5 Complexity Analysis 5.4 Circular Linked Lists 5.4.1 Working-Insert Node Operation 5.4.3 Implementation of Circular Linked Lists 5.4.4 Complexity Analysis 5.5 Applications of Linked Lists 6. Pointer Based Hierarchical Data Structures 6.1 Introduction-Non-Linear Data Structures 6.2 TREES 6.2.1 Definitions 6.3 Binary Trees 6.3.1 Types of Binary Trees 6.4 Implementation of Binary Trees 6.4.1 Pointer-based Implementation 6.4.2 Array-based Implementation 6.4.3 Linked List-based Implementation 6.5 Traversal 6.5.1 In-order Traversal 6.5.2 Pre-order Traversal 6.5.3 Post-order Traversal 6.5.4 Level-ordered Traversal 6.6 Basic Operations 6.6.1 Inserting a Node 6.6.2 Deleting a Node 6.7 Threaded Binary Trees 6.8 Applications of Trees 7. Search Trees 7.1 Introduction 7.2 Binary Search Trees 7.2.1 Operation-Search Value 7.2.2 Operation-Insert a Node 7.2.3 Operation-Delete a Node 7.2.4 Implementation of Binary Search Trees 7.2.5 Complexity Analysis 7.3 Avl Trees 7.3.1 Operation-Search Value 7.3.2 Operation- Insert a Node 7.3.3 Operation-Deleting a Node 7.3.4 Implementation of AVL Trees 7.3.5 Complexity Analysis 7.4 Red-Black Trees 7.4.1 Operation-Insertion 7.4.2 Operation-Delete a Node 7.4.3 Implementation of Red-Black Trees 7.4.4 Complexity Analysis 7.5 Splay Trees 7.5.1 Operation-'Search a Value' or 'Splay a Value' 7.5.2 Operation-Insert a Node 7.5.3 Operation-Delete a Node 7.5.4 Implementation of Splay Trees 7.5.5 Complexity Analysis 7.6 B-TREES 7.6.1 In-order Traversal 7.6.2 Operation-Search a Node 7.6.3 Operation-Insert a Node 7.6.4 Operation-Delete a Node 7.6.5 Implementation of B-Trees 7.6.6 Complexity Analysis 7.7 Applications of Search Trees 8. Priority Queues and Heaps 8.1 Introduction-Heap 8.2 Binary Heaps 8.2.1 Operation-Insertion 8.2.2 Operation-Deletion 8.2.3 Implementation of Max Heap 8.2.4 Complexity Analysis 8.3 Leftist Heaps 8.3.1 Operation-Merging 8.3.2 Operation-Insertion 8.3.3 Operation-Deletion 8.3.4 Implementation of Leftist Heaps 8.3.5 Complexity Analysis 8.4 Priority Queues Using Heaps 8.5 Applications of Heaps 9. Other Non-Linear Data Structures 9.1 Introduction-Non-Linear, Non-Hierarchical Data Structures 9.2 Trie 9.2.1 Insertion of a Key 9.2.2 Searching a Key 9.2.3 Implementation 9.2.4 Complexity Analysis 9.2.5 Applications of Trie 9.3 Dictionary 9.3.1 Inserting a Key and its Value 9.3.2 Deleting a Key along with Value 9.3.3 Merging Dictionaries 9.3.4 Handling Tabular Data 9.3.5 Implementation 9.3.6 Complexity 9.3.7 Applications of Dictionary 9.4 Hash Table 9.4.1 Linear Probing 9.4.2 Chaining the Elements 9.4.3 Implementation 9.4.4 Complexity 9.4.5 Applications of Hash Tables 9.5 Sets 9.5.1 Operation-Insertion of an Element 9.5.2 Operation-Removal of Elements 9.5.3 Binary Set Operations 9.5.4 Other Utility Functions 9.5.5 Implementation 9.5.6 Complexity Analysis 9.5.7 Applications of Set 9.5.8 Variants of Set Data Structure 9.5 Counter/Multisets 9.5.1 Accessing 9.5.2 Binary Operations on Counters 10. Memory Management 10.1 Introduction-Memory Management 10.2 Data Structures in Memory Management 10.3 B+ Trees 10.3.1 Working 10.3 Memory Hierarchy and Caching 11. Graphs 11.1 Graph-Introduction 11.2 Components of a Graph 11.4 Graph Representation 11.4.1 Linked List Based Representation 11.4.2 Matrix Based Representation 11.2.3 Pointer Based Representation 11.2.4 Performance Comparison of Graph Representation 11.3 Types of Graph 11.4 Working 11.4.1 Insertion of a node 11.4.2 Insertion of an edge 11.4.3 Deletion of an edge 11.4.4 Deletion of a node 11.5 Traversal 11.5.1 Depth First Search 11.5.2 Breadth First Search 11.7 Implementation of Graph 11.7.1 Adjacency List Based Representation 11.7.2 Adjacency Matrix Based Representation 11.7.3 Incidence Matrix Based Representation 11.8 Complexity Analysis 11.9 Topological Sorting 11.9.1 Implementation 11.9.2 Complexity Analysis 11.1 Spanning Tree 11.10.1 Kruskal Algorithm 11.10.2 Prim's Algorithm 11.11 Shortest Distance 11.11.1 Dijkstra's Algorithm 11.11.2 Floyd-Warshall Algorithm 11.12 Graph Connectivity 11.12 Applications Of Graph 12. Sorting 12.1 Introduction to Sorting 12.2 Importance of Sorting Algorithms 12.3 Exchange Sort 12.3.1 Bubble Sort 12.4 Selection Sort 12.4.1 Straight Selection Sort 12.4.2 Heap Sort 12.5 Insertion Sort 12.5.1 Simple Insertion Sort 12.5.2 Shell Sort 12.6 Divide and Conquer 12.6.1 Merge Sort 12.6.2 Quick Sort 12.7 Distributed Sort 12.7.1 Bucket Sort 12.7.2 Counting Sort 12.7.3 Radix Sort 12.8 Comparison of Sorts 13. Searching 13.1 Introduction-What is Searching? 13.2 Linear Search 13.2.1 Working 13.2.2 Implementation 13.3.3 Complexity Analysis 13.3 Binary Search 13.3.1 Working 13.3.2 Implementation 13.3.3 Complexity Analysis 13.4 Tree-Based Search 13.5 Hashing 13.5.1 Working 13.5.2 Problem of Collision 13.5.4 Implementation 13.5.5 Complexity Analysis 13.6 Case Studies of Searching Techniques ANNEXURE 1 - Python classes and built in Functions

About the Author :
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.