Data Structures and Abstract Data Types


Course Overview

The course is part of this learning path

Data Structures and Abstract Data Types
2h 28m

In this course, we will explore the fundamental concepts of abstract data types (ADTs) and data structures. Then, we'll discuss specific ADTs and common implementations. We'll first learn some basic terminology and then learn about array-based implementations, as well as a new approach using a data structure called the linked chain. We will put all that into practice through some demo projects, including a link-based queue and a stack that uses a linked list.

Intended Audience

  • Beginner coders, new to C++
  • Developers looking to upskill by adding C++ to their CV
  • College students and anyone studying C++


To get the most out of this course, you should have a basic understanding of the fundamentals of C++.


In this lecture, we're going to discuss the concepts of ADTs, or abstract data types, and data structures. It's important to note that the Standard Library in C++ offers us many different data structures that we can use. But it's also important as well as fundamental part of essentially any formal computer science or software engineering education to be able to build your own data structures. But first, we have to do a little bit of review. Before discussing abstract data types, we should review what a data type is. As you've learned throughout the course, the data type is simply the type of data that, for example, a variable or constant represents.

An Abstract Data Type, or ADT for short, is a description and abstraction representing what a particular entity is supposed to do; that is, its behaviors or operations that it provides and what it should know; that is, what data it should maintain. But the big difference between a plain old data type and an abstract data type is that, unlike an ADT, a data type is an actual implementation. It's an actual type that is provided or written by a developer. So, that's what ADT's are. They're abstract in the sense that they tell us what an entity does, but not how it does it. The data type fills in the how part. A data structure is also concrete. In fact, when you implement a data structure, it will also be a data type. However, a data structure is more specific. A data structure is a collection of elements. The simplest data structure in C++ is something you've worked with before: the Built-in Array.

Built-in Arrays can maintain multiple elements; that is, a collection of elements. Therefore, arrays are data structures. Data structures can be used to build more complex data structures and systems. So, the array data structure is often used as the underlying data structure or backing data structure for more complex data structures. In fact, arrays are one of the most popular underlying data structures. The other being linked chains, which we'll cover a bit later in the section. Whenever you take a course or section of a course or read a book that focuses on data structures, typically the ADTs that you'll deal with will be, not surprisingly, the ADTs for different data structures; that is, collections rather than just ADTs for non-collections. So, the ADT's tell us what a particular entity is supposed to do, again, but not how it does what it's supposed to do. The data structure itself fills in the missing information.

Before moving on, I'd like you to describe the difference between an ADT and a data structure as best you can in your own words. You don't have to memorize any formal definitions right now. So, pause the video and come back when you're done or if you need some help. How did that go for you? Were you able to remember the difference between ADTs and data structures? An ADT or abstract data type specifies the responsibilities of an entity; that is, what that entity is supposed to do and know. A data structure, on the other hand, is a collection of elements, and it fills in the details of how the responsibilities, typically specified by an ADT, are fulfilled. So, the data structure is a particular implementation of an ADT. In the next lecture, we'll discuss two fundamental data structures that we can use to build more complex data structures later on. I'll see you there.

About the Author
Learning Paths

John has a Ph.D. in Computer Science and is a professional software engineer and consultant, as well as a computer science university professor and department chair.

Covered Topics