Data Structures in Depth Using C++ A Comprehensive Guide to Data Structure Implementation and Optimization in C++ (Mahmmoud Mahdi) (z-library.sk, 1lib.sk, z-lib.sk)

Data Structures in Depth Using C++

Mahmmoud Mahdi Data Structures in Depth Using C++ A Comprehensive Guide to Data Structure Implementation and Optimization in C++

Mahmmoud Mahdi Zagazig, Egypt ISBN-13(pbk): 979-8-8688-0801-2 ISBN-13(electronic): 979-8-8688-0802-9 https://doi.org/10.1007/979-8-8688-0802-9 © Mahmmoud Mahdi 2025 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Trademarked names, logos, and images may appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, logo, or image we use the names, logos, and images only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Managing Director, Apress Media LLC: Welmoed Spahr Acquisitions Editor: Melissa Duffy Development Editor: James Markham Coordinating Editor: Gryffin Winkler Cover designed by eStudioCalamar Cover image by Mahmmoud Mahdi Distributed to the book trade worldwide by Apress Media, LLC, 1 New York Plaza, New York, NY 10004, U.S.A. Phone 1-800- SPRINGER, fax (201) 348-4505, e-mail orders-ny@springer-sbm.com, or visit www.springeronline.com. Apress Media, LLC is a California LLC and the sole member (owner) is Springer Science + Business Media Finance Inc (SSBM Finance Inc). SSBM Finance Inc is a Delaware corporation. For information on translations, please e-mail booktranslations@springernature.com; for reprint, paperback, or audio rights, please e-mail bookpermissions@springernature.com. Apress titles may be purchased in bulk for academic, corporate, or promotional use. eBook versions and licenses are also available for most titles. For more information, reference our Print and eBook Bulk Sales web page at http://www.apress.com/bulk-sales. Any source code or other supplementary material referenced by the author in this book is available to readers on GitHub (https://github.com/Apress). For more detailed information, please visit https://www.apress.com/gp/services/source-code. If disposing of this product, please recycle the paper.

To my dear father, may God forgive him.

Contents About the Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv About the Technical Reviewer . . . . . . . . . . . . . . . . . . . . . . . . xvii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxv 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Introduction 2 1.1.1 What Are Data Structures and Algorithms? . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Interplay Between Data Structures and Algorithms . . . . . . . . . . . . . . . . . . . . 2 1.1.3 The Significance of Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.4 Selecting the Appropriate Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Types of Data Structures 5 1.3 Fundamentals of Algorithms 6 1.3.1 Distinguishing Programming and Algorithmic Problems . . . . . . . . . . . . . . . . 6 1.3.2 Algorithm Design Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.3 Common Algorithmic Problem Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Analyzing Algorithm Efficiency 8 1.4.1 Understanding Algorithm Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

viii Contents 1.4.2 Evaluating Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.3 Analyzing Time Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.4 Understanding Growth Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.5 Evaluating Algorithm Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4.6 Asymptotic Growth Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 Summary 11 Problems 11 2 Primary Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1 Principles of Software Design 16 2.2 Data Structure Interfaces 16 2.2.1 Benefits of Using Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.2 Interface vs. Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.3 Interface Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Templates 19 2.3.1 Templates and Type Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.2 Template Usage in Practical Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.3 Templates in Interface Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.4 Considerations and Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Core Data Structure and Interfaces 21 2.4.1 List Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.2 Sets Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.5 Advanced Data Structure Interfaces 26 2.5.1 Tree Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.6 Summary 30 Problems 31 3 Arrays and Dynamic Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.1 Arrays and Pointers 34 3.1.1 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.1.2 Pointers to Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.1.3 Stack vs. Heap Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.1.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.1.5 Advantages and Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2 Dynamic Arrays 41 3.2.1 Resizable Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.2.2 Advantages and Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Contents ix 3.2.3 Dynamic Array Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2.4 Resizing Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.3 Optimization 48 3.3.1 An Optimized Copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.2 Optimized Dynamic Array Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.4 Summary 50 Problems 50 4 Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.1 Introduction to Linked Pointers 58 4.1.1 Pointers to Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.1.2 Creating Linked Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.1.3 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.1.4 Why Pointers Matter in Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 A Singly-Linked List (SLList) 63 4.2.1 Anatomy of a Singly-Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2.2 Creating a Singly-Linked List Without Tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.2.3 Creating a Singly-Linked List with a Tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.2.4 Accessing Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2.5 Traversing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.3 A Doubly-Linked List (DLList) 80 4.3.1 Anatomy of a Doubly-Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.3.2 A Circular Doubly-Linked List with Dummy Node . . . . . . . . . . . . . . . . . . . . . 80 4.3.3 Implementing Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.3.4 Insert and Remove . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.3.5 Accessing Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.3.6 Traversing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.4 Performance Analysis 90 4.4.1 Linked Lists vs. Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.4.2 Linked List Performance Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.4.3 Best Practices and Common Use Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.5 Summary 93 Problems 95 5 Stack and Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.1 Stack 100 5.1.1 Introduction to Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.1.2 Array-Based Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

x Contents 5.1.3 Linked List Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.2 Queue (Single-Ended Queue) 103 5.2.1 Introduction to Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.2.2 Array-Based Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.2.3 Linked List Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.3 Deque (Double-Ended Queue) 114 5.3.1 Introduction to Deque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.3.2 Array-Based Deque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.3.3 Linked List Deque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.4 Performance Analysis 121 5.4.1 Stack Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.4.2 Queue Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.4.3 Deque Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.4.4 Choosing the Right Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.5 Summary 122 Problems 122 6 Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.1 Hashing Introduction 130 6.1.1 Array vs. Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.1.2 Introducing Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.1.3 Applications of Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.1.4 Usage Example: Management and Analysis of Access Logs . . . . . . . . . 131 6.2 Hash Functions 133 6.2.1 Use of Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.2.2 Multiplicative Hash Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.2.3 Generating Hash Codes for Various Data Types . . . . . . . . . . . . . . . . . . . . 135 6.2.4 Collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 6.3 Hash Table Techniques 140 6.3.1 Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6.3.2 Open Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.3.3 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.4 Hash Table Implementation 147 6.4.1 Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6.4.2 Linear Probing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 6.4.3 Hash Table Performance Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 6.5 Summary 159 Problems 159

Contents xi 7 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 7.1 Binary Trees 166 7.1.1 Introduction to Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 7.1.2 Properties of Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 7.1.3 Types of Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 7.1.4 Representation of Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 7.1.5 Computing Size, Height, and Depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 7.1.6 Destroying a Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 7.1.7 Binary Tree Traversal Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 7.1.8 Implementation of Traversal Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 7.1.9 Traversing Binary Trees – Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 7.1.10 Comparison of Tree Traversal Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 7.2 Binary Search Trees (BSTs) 179 7.2.1 Introduction to Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 7.2.2 Properties of Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 7.2.3 Basic Operations in BST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 7.2.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 7.2.5 Class Implementation of BST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 7.2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 7.3 Balanced Binary Trees 187 7.3.1 Unbalanced Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 7.3.2 Self-Balancing Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 7.4 AVL Trees 190 7.4.1 Introduction to AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 7.4.2 AVL Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 7.4.3 Balanced and Unbalanced AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 7.4.4 Rotations in AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 7.4.5 Implementation of AVL Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 7.4.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 7.5 Summary 201 Problems 203 8 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 8.1 Introduction to Graphs 208 8.1.1 What Is a Graph? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 8.1.2 Graph Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 8.1.3 Types of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 8.1.4 Examples and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 8.1.5 Difference Between Graph and Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

xii Contents 8.2 Graph Representations 212 8.2.1 Basic Graph Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 8.2.2 Abstract Interface for Graph Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 8.2.3 Adjacency Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 8.2.4 Adjacency List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 8.2.5 Other Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 8.2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 8.3 Graph Traversals and Advanced Operations 236 8.3.1 Depth-First Traversal (DFS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 8.3.2 Breadth-First Traversal (BFS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 8.3.3 Advanced Graph Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 8.3.4 Graph Traversal Class Updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 8.4 Performance Considerations 243 8.4.1 Time Complexity of Graph Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 8.4.2 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 8.4.3 Choosing the Right Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 8.5 Summary 244 Problems 246 9 Specialized Data Structures and Techniques . . . . . . 249 9.1 Introduction 250 9.2 Heaps 250 9.2.1 Introduction to Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 9.2.2 Binary Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 9.2.3 Optimizing Binary Heap Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 9.2.4 Customizing Binary Heaps with HeapType . . . . . . . . . . . . . . . . . . . . . . . . . 264 9.3 Priority Queues 267 9.3.1 Introduction to Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 9.3.2 Implementing a Priority Queue with a Heap . . . . . . . . . . . . . . . . . . . . . . . 267 9.3.3 Priority Queue Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 9.3.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 9.4 Maps 272 9.4.1 Introduction to Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 9.4.2 Key-Value Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 9.4.3 Map Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 9.4.4 Implementing a Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 9.5 A Space-Efficient Linked List 279 9.5.1 Structure of a Space-Efficient Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

Contents xiii 9.5.2 Node Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 9.5.3 Implementation of Space-Efficient Linked List . . . . . . . . . . . . . . . . . . . . . . 282 9.5.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 9.5.5 Advantages and Trade-Offs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 9.6 Skip Lists 294 9.6.1 Introduction to Skip Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 9.6.2 Skip List Structure and Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 9.6.3 Node Structure Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 9.6.4 Skip List Class Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 9.6.5 Implementing Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 9.6.6 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 9.7 Summary 306 Problems 307 10 Applications and Real-World Examples . . . . . . . . . . . . 311 10.1 Task Scheduling System 312 10.1.1 Solution and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 10.1.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 10.1.3 Method Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 10.1.4 Example Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 10.1.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 10.1.6 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 10.2 Social Network Friend Recommendations 324 10.2.1 Solution and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 10.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 10.2.3 Method Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 10.2.4 Example Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 10.2.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 10.2.6 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 10.3 Library Management System 338 10.3.1 Solution and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 10.3.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 10.3.3 Method Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 10.3.4 Example Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 10.3.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 10.3.6 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352

xiv Contents 10.4 Summary 352 10.5 Book Summary 352 Problems 353 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

About the Author Mahmmoud A. Mahdi, Ph.D., is a seasoned computer science professional with exten- sive experience in academia, research, and software development since 2005. His expertise spans machine learning, natural language processing, and programming, with a strong em- phasis on C++. Over the course of his career, he has developed enterprise-grade solutions, led pioneering projects in big data analytics and Arabic natural language processing, and designed a custom compiler for robotic simulation that serves as both a technical innova- tion and an educational tool. He has a profound focus on algorithm design and analysis, tackling complex compu- tational challenges with innovative solutions. His research interests, published in leading journals and conferences, reflect his dedication to advancing the fields of computational research and scalable systems. As an experienced educator, Dr. Mahdi has designed and delivered courses on data structures, algorithms, machine learning, and software testing, emphasizing the practical application of theoretical concepts. His book, Data Structures in Depth Using C++, re- flects his decades of teaching, research, and hands-on experience, providing readers with a seamless integration of foundational knowledge and real-world insights. Beyond his academic and research endeavors, Dr. Mahdi is dedicated to fostering innovation, collaboration, and excellence in programming and software development. He continues to inspire the next generation of technologists, equipping them to bridge the gap between theory and practice and drive progress in the field of computer science.

About the Technical Reviewer Wael Said received his M.Sc. degree in Computer Science from Helwan University in 2004 and his Ph.D. degree in Computer Science in 2011 from Technical University Darmstadt. He is As- sociate Professor in the Department of Computer Science, Fac- ulty of Computers and Informatics, at Zagazig University and currently is Assistant Professor in the Department of Computer Science, College of Computer Science and Engineering, Taibah University, Saudi Arabia. His research interests are in the areas of machine and deep learning, text and data mining, data analy- sis and data science, cloud and mobile computing, information and database security, as well as cryptography and cryptanaly- sis.

Acknowledgments The journey of writing this book has been a rewarding and enlightening experience, and it would not have been possible without the support and encouragement of many individuals who contributed in various ways. I would like to express my deepest gratitude to my family for their unconditional love, patience, and support. Your encouragement has been my greatest motivation throughout this process, and I am forever grateful for your belief in me. A special thanks to Dr. Wael Said, whose insightful reviews and constructive feedback greatly enriched the quality of this book. Your expertise and guidance were invaluable in refining the content and ensuring its accuracy. A special acknowledgment goes to my outstanding student, Fatma Omara, whose metic- ulous revisions and thoughtful suggestions greatly improved the clarity and coherence of the material. I am also deeply thankful toMenna Jaheen for her creative contributions to the book’s visual appeal, particularly her work on the engaging cartoon graphics. I would also like to extend my heartfelt appreciation to the team at Apress. Managing Director, Wel- moed Spahr, Acquisitions Editor, Melissa Duffy, Development Editor, James Markham, and Coordinating Editor, Gryffin Winkler, your professionalism, dedication, and attention to detail were instrumental in bringing this book to life. I am deeply thankful for your guidance and support throughout the publishing process. Finally, I wish to thank you, the reader, for choosing this book. I hope it serves as a valuable resource on your journey to mastering data structures and algorithms in C++. Your enthusiasm for learning inspires the creation of works like this, and I am honored to be a part of your educational journey. Thank you all for your support.

Introduction Welcome to Data Structures in Depth Using C++, a comprehensive guide designed to help you master the fundamental and advanced concepts of data structures and algorithms. This book is your gateway to understanding how to efficiently organize, manage, and manipu- late data to solve complex computational problems. Whether you are a student, educator, or professional, this book will equip you with the knowledge and skills to implement and op- timize data structures using C++, one of the most powerful and widely used programming languages in the software industry. The content below already serves as the introduction, addressing what the book is about, its target audience, the structure, and learning outcomes. It includes: Who This Book Is For Structure of the Book Learning Outcomes Who This Book Is For This book is intended for students, educators, and professionals alike who wish to deepen their understanding of data structures and algorithms using C++. Whether you’re a begin- ner looking to get started with the basics or an experienced developer aiming to refine your skills, this book offers something valuable for every reader. The content is particularly suited for those preparing for technical interviews, academic examinations, or looking to enhance their problem-solving abilities in software development.

xxii Introduction Structure of the Book The book is structured to take the reader on a journey from the basic concepts to the more advanced topics in data structures. Each chapter follows a structured approach: • Introduction: Each chapter begins with an overview of the data structure, including its definition, characteristics, and common use cases. • Implementation: This section provides a step-by-step guide to implementing the data structure using C++. The code examples are thoroughly explained, ensuring that readers understand every line of code. • Performance Analysis and Optimization: This section analyzes the efficiency of the data structures and explores techniques to optimize their performance. • Exercises: To reinforce learning, each chapter concludes with a set of exercises, ranging from basic to challenging, designed to test the reader’s understanding and encourage further exploration. The chapters are organized as follows: • Chapter 1: Introduction – Covers the fundamentals of data structures and algo- rithms, their significance, and the interplay between them • Chapter 2: Primary Building Blocks – Discusses the principles of software design, data structure interfaces, and the use of templates • Chapter 3: Arrays and Dynamic Arrays – Focuses on array structures, including static and dynamic arrays, their implementation, and optimization techniques • Chapter 4: Linked List – Explores singly- and doubly-linked lists, their memory management, and performance analysis • Chapter 5: Stack and Queue – Introduces stack and queue structures, including array-based and linked list implementations, and their performance considerations • Chapter 6: Hash Tables – Discusses hashing techniques, hash functions, and hash table implementation strategies • Chapter 7: Trees – Delves into binary trees, binary search trees, and AVL trees, covering their properties, operations, and performance analysis • Chapter 8: Graphs – Covers graph theory, graph representations, and advanced operations like traversals and graph algorithms • Chapter 9: Specialized Data Structures and Techniques – Introduces advanced data structures like heaps, skip lists, and space-efficient linked lists • Chapter 10: Applications and Real-World Examples – Provides case studies and real-world examples that demonstrate the application of data structures in practical scenarios, such as task scheduling, social network analysis, and library management systems By reading this book, you will: • Gain a deep understanding of data structures and their implementation in C++ • Learn how to optimize data handling and storage for efficient software performance • Develop the ability to solve complex programming problems using appropriate data structures • Understand best practices in data structure design and performance analysis

Introduction xxiii How to Use This Book Each chapter includes detailed explanations, code snippets, and exercises to reinforce learn- ing. The code examples are designed to be run in a standard C++ development environment, and the exercises at the end of each chapter provide opportunities to test your understand- ing. Whether you are reading sequentially or jumping to specific topics, this book aims to provide both theoretical insights and practical skills. Use the exercises to practice and the case studies to see how these data structures are applied in real-world scenarios. Final Remarks Data Structures in Depth Using C++ is more than a textbook; it is a practical guide de- signed to help you transition from understanding basic concepts to mastering advanced data structures. The book encourages experimentation with code, exploration of exercises, and deeper engagement with C++ programming. By the end, you will have built a strong foundation in data structures, preparing you for advanced studies or professional develop- ment in computer science. Enjoy your journey into the world of data structures with C++!

Acronyms ADT Abstract Data Type API Application Programming Interface ASCII American Standard Code for Information Interchange AVL Adelson-Velsky and Landis BFS Breadth-First Search BST Binary Search Tree DLList Doubly-Linked List DFS Depth-First Search FIFO First In, First Out GUI Graphical User Interface IDE Integrated Development Environment LIFO Last In, First Out LR Left Rotation LRR Left-Right Rotation OOP Object-Oriented Programming RLR Right-Left Rotation RR Right Rotation SEList Space-Efficient List SLList Singly-Linked List UML Unified Modeling Language