Introduction to Data Structures and Algorithms in C++
This introductory course will teach you how to implement some fundamental data structures and algorithms in C++ from scratch, with a combination of theoretical introduction using slides, and practical C++ implementation code.
What you'll learn
Knowing some fundamental data structures and algorithms both in theory and from a practical implementation perspective helps you in being a better C++ programmer, gives you a good foundation to understand standard library’s containers and algorithms inner “under the hood” mechanics, and serves as a kind of knowledge that is required in several coding interviews, as well.
In this course, Introduction to Data Structures and Algorithms in C++, you’ll learn how to implement some fundamental data structures and algorithms in C++ from scratch, with a combination of theoretical introduction using slides, and practical C++ implementation code as well.
No prior data structure or algorithm theory knowledge is required. You only need a basic knowledge of C++ language features.
- First, you'll discover how to develop a C++ class to safely use arrays, with automatic memory management using constructor and destructor, and safely accessing array elements with bounds checking.
- Then, you’ll see how to further improve this array class, overloading the insertion operator to offer a simple nice idiomatic printing syntax for arrays, and optimizing the array class with move semantics.
- You’ll also learn how to properly copy arrays, and you’ll see the copy-and-swap idiom in action.
- Then, you’ll learn how to generalize the array class with templates.
- Next, you’ll learn about the Big O notation in a practical intuitive way, and you’ll apply that knowledge to a couple of search algorithms.
- You’ll start learning how to search using the simple linear search, and then you’ll see how to improve searching, using binary search. I’ll first introduce these algorithms using slides, and then you’ll see them in action in concrete C++ demo code.
- Finally, you’ll discover how to implement other common data structures, like the stack with its LIFO policy and push and pop operations, and linked lists, including operations like list node insertion and removal, and searching elements in a linked list.
Moreover, you will be able to use this foundational knowledge to move forward to more advanced C++ data structures and algorithms topics.
Table of contents
- Version Check 0m
- Introduction 3m
- Prerequisites 2m
- Module Overview 2m
- What Is an Array? 6m
- C++ Built-in Arrays and Stack vs. Heap Allocations 3m
- Starting a Basic Array Class Implementation Journey 5m
- Spotting a Bug in the Array Class 5m
- Fixing Memory Leaks with a Destructor 3m
- Accessing Array Elements with Overloaded operator[] 3m
- Granting Read-only Access to Array Elements 1m
- Bounds-checking for Safe Array Element Access 4m
- Array Index Bounds-checking in Action 4m
- Summary 2m
- Introduction 3m
- Conveniently Printing Arrays 7m
- Demo: Printing Arrays with the Overloaded Insertion Operator 2m
- Demo: A Subtle Bug When Copying Arrays 2m
- Analyzing the Subtle Copy Bug: Shallow vs. Deep Copies 5m
- Safely Copying Arrays with a Custom Copy Constructor 2m
- Demo: Custom Array Copy Constructor in Action Fixing the Copy Bug 1m
- Overloading the Assignment Operator 3m
- The Copy-and-swap Idiom 7m
- Optimizing the Array Class with Move Semantics 6m
- Generalizing the Array Class with Templates 5m
- Summary 2m
- Introduction 2m
- A Simple Straightforward Algorithm: Linear Search 2m
- Demo: Implementing Linear Search in C++ 10m
- Smarter Searching with Binary Search 4m
- Demo: Implementing Binary Search in C++ 9m
- Introducing the Big O Notation and Asymptotic Runtime Complexity 8m
- Comparing the Efficiency of Linear Search vs. Binary Search 5m
- Summary 2m