Learn About Data Structures And Algorithm (DSA) - Part Two

About Article

This article will tell you about the crucial concepts of data structures and algorithms in terms of the understanding list as ADT. This article is the second one in the series “Data Structure and Algorithm (DSA).” You’ll learn more about data structures and algorithms in detail in my coming articles. So stay tuned for the next articles.

Read this article, then feel free to give your feedback.

The topics to be covered are

• Introduction
• What is List
• Abstract Data Type (ADT)
• List as ADT
• Static List
  • Implementation of the static list
• Analysis of Dynamic list
  • Measuring the time complexity
• Result of analysis
• Best implementation of the list after analysis

Prerequisites of this Article

You should be aware of the concepts of Data Structure and its purpose, ways of implementing it, and its classification. Also, you should have knowledge about time complexity and space complexity, and the ways to analyze the algorithm using different asymptotic notations. All the mentioned topics are clearly described in my previous article. Following is the link to my previous article.

Learn About Data Structures And Algorithms (DSA) – Part One

Introduction

As you have learned, if we want to implement any data structure, then first we have to define its Abstract Data Type (ADT), then we have to provide its implementation. We can say that first, we need to make the mathematical and logical model, then to implement it on the data objects. As we see only the abstract view, we can call this abstract data type ADT.

Abstract Data Type (ADT)

The data and operations on which the data structure comprises are called Abstract Data Type (ADT). In ADT, we don’t give any implementation of the data objects and their operations. We can say that ADT provides us with Data Abstraction. ADT focuses on “what a data structure does” rather than on “how a data structure does”. In this article, you’ll learn the list as ADT and then its implementation.

What is a List?

A list is a common real-world entity and a collection of objects of the same data type. First, we define the list as an Abstract Data Type (ADT). So, we are only concerned with the data and operations on the list, not its implementation.

List as ADT

Let's take an example, we want to make a list that can perform the following operations.

• Store a given number of elements of any given data type.
• Read elements by their position in the list.
• Write/Modify elements at any position in a list.

All the above features are about data and operations on the list having a specific data type. So this is an abstract data type because we only focus on “what the list does” rather than the implementation in terms of “how the list does”.

Static List

The list you have seen above is some sort of static list because it is of some fixed size and will not grow automatically when the list is full. Now the question comes what is the implementation of this static list? We know this is the second concept about that data structure, which is its implementation. In other words, you can say you have to do the concrete implementation of this static list in which you can store elements, read elements, and modify elements. Let’s say we implement the above static list ADT as “arrays”.

What is Array?

The array is a sequential-linear data structure that provides us with the implementation of the list, so it means it is also a collection of objects of the same data type. Here, sequential means, the array is a block of one contiguous memory that starts from index 0 to a specific given index size. Let’s implement the array for the above ADT static list.

Hence, you have seen the implementation of the ADT as a static list. Because this list is a static list and now we want to make a list that has more features. So we have to redefine the list with new features. Let’s say, we want to make a list that has the following functionalities.

• An empty list should have a size of 0.
• Enable us to insert an element at any position.
• Enable us to remove elements from any position.
• Enable us to count the total number of elements in the list.
• Read/Modify the element at any particular position in the list.
• Specify the data type of the list.

Now, we need a data structure that implements the above ADT. Let’s say we are taking here the array (sequential-linear data structure) data structure. Let’s say we create an array of some large max size that implements the above ADT.

You can see in the following pictures that, first we create the int array A of some maximum size, then we make a variable named “end” and set it to -1 which is an invalid address showing that the list is empty. Then we insert the value into the list.

Now, we want to insert the value 5 at the specific position in the list, let’s say position/index 2, so we have to shift all the values to higher indices so that the block of position/index 2 becomes empty. Then, we store the value 5 into the index 2. You can see it in the following picture logically,

Now, we want to remove the element from the list, first, the value is deleted then all the values are shifted to fill the empty space. You can see it in the following pictures logically.

The pictures are completely made by myself and very self-explanatory. So if you still have any problem understanding then feel free to ask me the question in the comments section.

If you want to count the total number of elements in the list then, you can use the “count” function and calculate the total number of elements using the “end” variable. See the method below.

Hence, you have seen how this array implements the previous ADT. As you know, we have created this list which is of some large size. Now the question comes: what will happen when the list is full while there is still some data to be stored?

So the answer to this question is: “When the implemented array is full, create a new larger array of double the size of the previous array. Then copy the elements of the previous array into the new array.”

So, this is the strategy to be followed when the array is filled up. However, the problem with this strategy is, this strategy is costly in terms of time and space. Let’s go towards the analysis of this list.

Analysis of list

As we know, the data structure is a way to store and organize data. But we also have to maintain the efficiency of the program/algorithm. In the case of this list, we have to analyze the cost of operations performed on this list.

Measuring the Time Complexity

Let’s analyze the cost of time for operations performed on the previously created array. You’ll see the analysis in terms of the following cases.

• Accessing the element
• Inserting the element
• Removing the element

Accessing the element

If we want to access the element of a specific position/index, then it takes some constant time because it is an array. So, its time complexity in terms of Big-Oh notation is O(1).

Inserting the element

If we want to insert an element at the end of the array, then this insertion also takes constant time. So, time complexity in terms of Big-Oh notation will be O(1). This is the case when the array is not full.

But if you want to insert the element at a particular position in the array, then we have to make shifts, as you have seen in the above pictures. The worst case will be if you want to insert an element in the start of the array at the index 0, so we have to shift all the elements toward higher indices. So, cost in terms of time is proportional to the length of the array having n size T n, so time complexity in terms of Big-Oh notation will become O(n), which shows linear time complexity.

The third case is, what happens when you are inserting an element in the array and the array is already full? So we know we have to make a new array of double the size of the previous array and copy the elements from the previous array into the new array. So the procedure of creating a new array and copying all the elements is costly in terms of time. So for this strategy, the cost in terms of time is proportional to the length of the array having n size T n, so time complexity in terms of Big-Oh notation will become O(n), which shows linear time complexity.

Removing the element

If we want to remove an element at the end of the array, then this removal of the element takes constant time. So, time complexity in terms of Big-Oh notation will be O(1).

But if you want to remove an element at a particular position in the array, then we have to make shifts, as you have seen in the above pictures. The worst case will be, if you want to remove an element at the start of the array means at the index 0, so we have to shift all the elements towards lower indices. So, cost in terms of time is proportional to the length of the array having n size T n, so time complexity in terms of Big-Oh notation will become O(n), which shows linear time complexity.

Result of analysis

To understand the result I have created a table to show the costs of time for each operation for the described ADT.

You can deduct the result from the above table like the following.

• We can access any element in constant time. So it is a good thing.
• Insertion and deletion of the element are costly.
• The addition of an element when the array is full is also time costly.

The problem is space complexity

We also have one problem here about this array implementation: it makes our memory useless. When we want to insert the element in the array, and we encounter the filled array, then we create a new array of double the size of the previous array. But we didn’t fill the whole array and all the rest of the memory is wasted. So, it is costly in terms of space complexity.

Best implementation

As we analyze this array implementation, we see that it is costly in terms of both memory and time. So now we need a data structure that implements our previous ADT efficiently. We need to have a data structure that grows its size automatically when the list is full. So, we can say that we want to create a dynamic list. So all these features can be implemented by a data structure named “Linked List”. Linked List is a data structure that implements our ADT and behaves efficiently in terms of memory and time. You’ll learn the introduction and implementation of Linked List in coming articles. So stay tuned!

Summary

In this article, you have learned what the data structure is and its implementation, including ADT. You also learned the implementation of different ADTs. Then you have learned the analysis of different operations run on the array in terms of time and space complexity. Then, you have seen the best implementation of the described ADT. So stay tuned for coming articles.

I hope this article has helped you understand the basic concepts of data structures and the implementation of an array data structure for an ADT. Stay tuned for my next articles because this article is the second one in the series of “Learn about Data Structures and Algorithm (DSA),” and you’ll learn more about data structure in the coming articles. If you have any queries, please feel free to contact me in the comments section. Also, to provide feedback, whether positive or negative. It will help me to make my articles better and increase my enthusiasm to share my knowledge.