1.0 Data Structures – Quick Start

Let’s continue our talk about data structures. In the last post, I have mentioned the problems that require using data structures and the basic concept behind the magic of them. We agreed that we have , at least, to know when to use the different data structures and the most suitable one for every situation. As developers, we are going to discuss the implementation issues of data structures, here. As mentioned, all implementation codes will be written in C++.

First, let’s agree on some basic concepts and terminologies.

Data Abstraction:

Data Abstraction is the term we use to describe the separation between how we use data, and how they are implemented. In other words, it’s about how the application access to data, and how data are organized in memory. In the above figure, we can see that this boy is exchanging a book with a book store. Actually he don’t know how books are organized into the library, because that lady is serving him and making what the boy asks her to do. (e.g. boy: please, I want to return back this book in its correct place on the shelf. lady: OK, I will do the task). This is exactly what we are going to do. We (as the lady) will manage memory locations (book shelves) to organize variables (books). We will do so for any other boy (application) that needs to deals with books (variables in memory locations). The above situation is EXACTLY what we are going to discuss. For sure, we will do the implementation and give the users some functions to call if they need to access memory.

Data Encapsulation:

If you are coming for an Object-Oriented programming language, this concept is not strange for you. But in case you are not comfortable with OOP, I will make a summary review now. OOP stands on three main concepts: Encapsulation, Inheritance and Polymorphism. The fist term is what we mention here. It means that you secure access to your data through specific gates (which are functions). This implies what we call Information Hiding. For simplicity, it means that no one can edit data (add, delete, modify) without your permission. This is implemented through private data members:

class Test {
    private: 
           int x;
           string y;
           :
           :
    public:
           //list here all your functions that control
           //access to these data.    
}

Now, our task is how to choose what data types to use, and how to design the public functions to meet the specifications.

The main data structure, that we all used, is the array. We know that an array is a collection of elements from the same type that are stored sequentially in memory. We can add and update elements using indices (e.g. arr[0], arr[1],..arr[i]). We can remove elements from the array by giving them in-valid values or null (if you are using pointers for handling the array). But, why do we say that the array is a data structure?! Simply, apply the above rules. We can access them (adding, updating, deleting …). We don’t know how the language specification implement them deep inside. However, we can notice that array faces some problems that relates to its nature of random access. That is, we can access any element in the array and change its value. And more, we can get errors by referencing an element that is outside the array boundaries!. But, It’s still a data structure :).

So, How am I going to present a data structures ?. I will follow a simple steps.

I will write the data structure specification, and give it to the utility programmer (which is also me). and then test what the utility programmer with a test driver written by a tester (which is also  me :D).

For now, we have revisited the basic concepts and terminologies we will use. I don’t want to flood the posts with information. So, I will follow the rule in my posts (specifications, design, test) for every data structure we will discuss. You can start searching about, Lists, Sorting them, Stacks, Queues and Trees. Just Stay Tuned for the upcoming posts.

Questions are very welcomed and your feedback is very important to me :).

4 thoughts on “1.0 Data Structures – Quick Start

leave your feedback

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s