Get a month of TabletWise Pro for free! Click here to redeem

Abstract data types Introduction

Share the link to this class


Hello, and welcome to this new series on data structures. In these first few videos, I want to lay the foundation of some core concepts you will need throughout these video tutorials. Let's get started with the basics. So what is a data structure? one definition that I really like is a data structure is a way of organizing data so that it can be used efficiently. And that's all a data structure really is it is a way of organizing data in some fashion so that later on it can be accessed, queried or perhaps even updated quickly and easily.

So why data structures? Well, why are they important? Well, they are essential ingredients in creating fast and powerful algorithms. Another good reason might be that they help us manage and organize our data in a very natural way. And this last point is more of my own making, and it's that it makes code cleaner and easier to understand. As a side note, one of the major distinctions that I have noticed from bad mediocre to excellent programmers is that the ones who really excel are the ones who fundamentally understand how and when to use the appropriate data structure for the task they're trying to finish.

Data structures can make the difference between having an okay product and an outstanding one. It's no wonder that every computer science undergraduate student is required to take a course in data structures. It is strange that before we even begin talking about data structures that we need to talk about the abstraction data structures. What I'm talking about is the concept of an abstract data type. What is an abstracted type and how does it differ from a data structure? Well, the answer is that an abstract data type is an abstraction of a data structure which provides only the interface to which that data structure must adhere to.

The interface does not give any specific details on how a specific dish lecture should be implemented or in what programming language. One particular example I like to give is to suppose that your abstract data type is for a mode of transportation to get from point A to point B. Well, as we both know, there are many modes of transportation to get from one place to another. So which one do you choose some specific modes of transport? And might be walking or biking, perhaps even taking a train and so on these specific modes of transportation would be analogous to the data structures themselves. We want to get from one place to another through some mode of transportation, that was our abstract datatype.

How did we do that? Exactly? Well, that is the data structure. Here are some examples of abstract data types on the left, and some possible underlying implementation on the right hand side. As you can see, a list can be implemented in two ways. You can have a dynamic array or a linked list.

They both provide ways of adding, removing and indexing elements in the list. Next, we have a queue and the map abstract data types, which themselves can be implemented in a variety of ways. Notice that under the implementation for a queue, I put a stack based queue because yes, you can have a queue, which is implemented using only stacks. This may not be the most efficient way of implementing a queue, but it does work and it is possible. The point here is that the abstract idea type only defines how a data structure should behave and what methods it should have, but not the details surrounding how those methods are implemented. That is all for this video.

Thank you for watching, and in the next video, we will be talking about computational complexity and big O notation. See you then

Sign Up