Data Structures with Generic Types in C++

Gain insights into array and linked list-based implementations, delve into advanced structures like skiplists and trees, and explore template-based collections for efficient data optimization and retrieval.

Intermediate

96 Lessons

29h

Certificate of Completion

AI-POWERED

Explanations

AI-POWERED

Explanations

This course includes

45 Playgrounds

14 Quizzes

This course includes

45 Playgrounds

14 Quizzes

Course Overview

Data structures and algorithms are essential in computer science since they play a crucial role in efficient information retrieval and processing, dealing with files, storing contacts on phones, social networks and web searches. In this course, you’ll learn about the array-based implementation of various linear data structures, stack, and queues. You’ll also learn about linked list-based implementation. Next, you’ll explore advanced data structures like skiplists and hashing. You’ll learn how to implement ...Show More

What You'll Learn

A thorough understanding of data structures and algorithms

Working knowledge of array-based, linked list-based, and blended implementations

Hands-on experience of C++ interfaces, classes, and templates

Familiarity with complexity analysis of data structures and related algorithms

What You'll Learn

A thorough understanding of data structures and algorithms

Course Content

Overview

Step through key data structures in C++, understanding their interfaces and efficiency.

Introduction

The Need for Efficiency

Interfaces

Mathematical Background

The Model of Computation

Approach and Coverage

Quiz

Discussion

Array-Based Lists

Get started with array-based list implementations, including stacks, queues, deques, and space-efficient arrays.

Array Implementation of Stack

ArrayQueue: An Array-Based Queue

ArrayDeque: Fast Deque Operations Using an Array

DualArrayDeque: Building a Deque from Two Stacks

RootishArrayStack: A Space-Efficient Array Stack

Analysis of RootishArrayStack

Quiz on Array-Based Lists

Discussion on Array-Based Lists

Excercise: Array-Based Lists

Solution: Array-Based Lists

Linked Lists

Examine the structures, operations, and efficiencies of various linked lists for dynamic collections.

SLList: A Singly-Linked List

DLList: A Doubly-Linked List

SEList: A Space-Efficient Linked List

Operations on SEList

Amortized Analysis of Spreading and Gathering

Quiz on Linked Lists

Discussion on Linked Lists

Skiplists

Grasp the fundamentals of skiplists for efficient data manipulation and random-access linked lists.

Introduction to Skiplist

SkiplistSSet: An Efficient SSet

SkiplistList: An Efficient Random-Access List

Analysis of Skiplists

Quiz on Skiplists

Discussion on Skiplists

Exercise: Skiplists

Solution: Skiplists

Hash Tables

Dig deeper into hash table implementations, efficient data retrieval methods, and collision resolution.

ChainedHashTable: Hashing with Chaining

LinearHashTable: Linear Probing

Hash Codes

Quiz on Hash Tables

Discussion on Hash Tables

Excercise: Hash Tables

Solution: Hash Tables

Binary Trees

5 Lessons

Investigate binary trees, their structure, traversals, binary search trees, and design considerations.

Random Binary Search Trees

6 Lessons

Master the steps to build and optimize random binary search trees and Treaps efficiently.

Scapegoat Trees

6 Lessons

Step through Scapegoat Trees' balance maintenance, efficiency analysis, and optimization techniques.

Red-Black Trees

5 Lessons

Discover the logic behind red-black trees, their operations, and their balanced structure.

10.

Heaps

6 Lessons

Break apart Binary Heaps and Meldable Heaps, explore heap variations, and implement `remove(i)`.

11.

Sorting Algorithms

9 Lessons

Enhance your skills in various sorting algorithms, their efficiencies, and practical implementations.

12.

Graphs

8 Lessons

Deepen your knowledge of graphs, their representations, traversal algorithms, and universal sink detection.

13.

Data Structures for Integers

4 Lessons

Follow the process of efficient set implementations for integers with BinaryTrie, XFastTrie, and YFastTrie.

14.

External Memory Searching

6 Lessons

Practice using B-trees for efficient external memory operations and managing dynamic datasets.

15.

Wrap Up

1 Lesson

Step through data structures, algorithms, trees, sorting, graphs, and feedback in C++.

Trusted by 1.4 million developers working at companies

Anthony Walker

@_webarchitect_

Evan Dunbar

ML Engineer

Carlos Matias La Borde

Software Developer

Souvik Kundu

Front-end Developer

Vinay Krishnaiah

Software Developer

Eric Downs

Musician/Entrepeneur

Kenan Eyvazov

DevOps Engineer

Souvik Kundu

Front-end Developer

Eric Downs

Musician/Entrepeneur

Anthony Walker

@_webarchitect_

Evan Dunbar

ML Engineer

Hands-on Learning Powered by AI

See how Educative uses AI to make your learning more immersive than ever before.

Instant Code Feedback

Evaluate and debug your code with the click of a button. Get real-time feedback on test cases, including time and space complexity of your solutions.

AI-Powered Mock Interviews

Put your skills to the test in a simulated interview setting. Receive personalized feedback based on your performance. Available in Premium & Premium Plus plans.

Adaptive Learning

At various checkpoints throughout Educative courses, you will be prompted to take a quick assessment. Receive a condensed curriculum tailored to your strengths and skill gaps.

Explain with AI

Select any text within any Educative course, and get an instant explanation — without ever leaving your browser.

AI Code Mentor

AI Code Mentor helps you quickly identify errors in your code, learn from your mistakes, and nudge you in the right direction — just like a 1:1 tutor!